/* * Copyright (c) 2000, 2006, 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.provider.certpath; import java.util.ArrayList;import java.util.Collections;import java.util.Iterator;import java.util.List; /** * An AdjacencyList is used to store the history of certification paths * attempted in constructing a path from an initiator to a target. The * AdjacencyList is initialized with a <code>List</code> of * <code>List</code>s, where each sub-<code>List</code> contains objects of * type <code>Vertex</code>. A <code>Vertex</code> describes one possible or * actual step in the chain building process, and the associated * <code>Certificate</code>. Specifically, a <code>Vertex</code> object * contains a <code>Certificate</code> and an index value referencing the * next sub-list in the process. If the index value is -1 then this * <code>Vertex</code> doesn't continue the attempted build path. * <p> * Example: * <p> * Attempted Paths:<ul> * <li>C1->C2->C3 * <li>C1->C4->C5 * <li>C1->C4->C6 * <li>C1->C4->C7 * <li>C1->C8->C9 * <li>C1->C10->C11 * </ul> * <p> * AdjacencyList structure:<ul> * <li>AL[0] = C1,1 * <li>AL[1] = C2,2 =>C4,3 =>C8,4 =>C10,5 * <li>AL[2] = C3,-1 * <li>AL[3] = C5,-1 =>C6,-1 =>C7,-1 * <li>AL[4] = C9,-1 * <li>AL[5] = C11,-1 * </ul> * <p> * The iterator method returns objects of type <code>BuildStep</code>, not * objects of type <code>Vertex</code>. * A <code>BuildStep</code> contains a <code>Vertex</code> and a result code, * accessable via getResult method. There are five result values. * <code>POSSIBLE</code> denotes that the current step represents a * <code>Certificate</code> that the builder is considering at this point in * the build. <code>FOLLOW</code> denotes a <code>Certificate</code> (one of * those noted as <code>POSSIBLE</code>) that the builder is using to try * extending the chain. <code>BACK</code> represents that a * <code>FOLLOW</code> was incorrect, and is being removed from the chain. * There is exactly one <code>FOLLOW</code> for each <code>BACK</code>. The * values <code>SUCCEED</code> and <code>FAIL</code> mean that we've come to * the end of the build process, and there will not be any more entries in * the list. * <p> * @see sun.security.provider.certpath.BuildStep * @see sun.security.provider.certpath.Vertex * <p> * @author seth proctor * @since 1.4 */public class AdjacencyList { // the actual set of steps the AdjacencyList represents private ArrayList<BuildStep> mStepList; // the original list, just for the toString method private List<List<Vertex>> mOrigList; /** * Constructs a new <code>AdjacencyList</code> based on the specified * <code>List</code>. See the example above. * * @param list a <code>List</code> of <code>List</code>s of * <code>Vertex</code> objects */ public AdjacencyList(List<List<Vertex>> list) { mStepList = new ArrayList<BuildStep>(); mOrigList = list; buildList(list, 0, null); } /** * Gets an <code>Iterator</code> to iterate over the set of * <code>BuildStep</code>s in build-order. Any attempts to change * the list through the remove method will fail. * * @return an <code>Iterator</code> over the <code>BuildStep</code>s */ public Iterator<BuildStep> iterator() { return Collections.unmodifiableList(mStepList).iterator(); } /** * Recursive, private method which actually builds the step list from * the given adjacency list. <code>Follow</code> is the parent BuildStep * that we followed to get here, and if it's null, it means that we're * at the start. */ private boolean buildList(List<List<Vertex>> theList, int index, BuildStep follow) { // Each time this method is called, we're examining a new list // from the global list. So, we have to start by getting the list // that contains the set of Vertexes we're considering. List<Vertex> l = theList.get(index); try { // we're interested in the case where all indexes are -1... boolean allNegOne = true; // ...and in the case where every entry has a Throwable boolean allXcps = true; for (Vertex v : l) { if (v.getIndex() != -1) { // count an empty list the same as an index of -1...this // is to patch a bug somewhere in the builder if (theList.get(v.getIndex()).size() != 0) allNegOne = false; } else if (v.getThrowable() == null) allXcps = false; // every entry, regardless of the final use for it, is always // entered as a possible step before we take any actions mStepList.add(new BuildStep(v, BuildStep.POSSIBLE)); } if (allNegOne) { // There are two cases that we could be looking at here. We // may need to back up, or the build may have succeeded at // this point. This is based on whether or not any // exceptions were found in the list. if (allXcps) { // we need to go back...see if this is the last one if (follow == null) mStepList.add(new BuildStep(null, BuildStep.FAIL)); else mStepList.add(new BuildStep(follow.getVertex(), BuildStep.BACK)); return false; } else { // we succeeded...now the only question is which is the // successful step? If there's only one entry without // a throwable, then that's the successful step. Otherwise, // we'll have to make some guesses... List<Vertex> possibles = new ArrayList<Vertex>(); for (Vertex v : l) { if (v.getThrowable() == null) possibles.add(v); } if (possibles.size() == 1) { // real easy...we've found the final Vertex mStepList.add(new BuildStep(possibles.get(0), BuildStep.SUCCEED)); } else { // ok...at this point, there is more than one Cert // which might be the succeed step...how do we know // which it is? I'm going to assume that our builder // algorithm is good enough to know which is the // correct one, and put it first...but a FIXME goes // here anyway, and we should be comparing to the // target/initiator Cert... mStepList.add(new BuildStep(possibles.get(0), BuildStep.SUCCEED)); } return true; } } else { // There's at least one thing that we can try before we give // up and go back. Run through the list now, and enter a new // BuildStep for each path that we try to follow. If none of // the paths we try produce a successful end, we're going to // have to back out ourselves. boolean success = false; for (Vertex v : l) { // Note that we'll only find a SUCCEED case when we're // looking at the last possible path, so we don't need to // consider success in the while loop if (v.getIndex() != -1) { if (theList.get(v.getIndex()).size() != 0) { // If the entry we're looking at doesn't have an // index of -1, and doesn't lead to an empty list, // then it's something we follow! BuildStep bs = new BuildStep(v, BuildStep.FOLLOW); mStepList.add(bs); success = buildList(theList, v.getIndex(), bs); } } } if (success) { // We're already finished! return true; } else { // We failed, and we've exhausted all the paths that we // could take. The only choice is to back ourselves out. if (follow == null) mStepList.add(new BuildStep(null, BuildStep.FAIL)); else mStepList.add(new BuildStep(follow.getVertex(), BuildStep.BACK)); return false; } } } catch (Exception e) {} // we'll never get here, but you know java... return false; } /** * Prints out a string representation of this AdjacencyList. * * @return String representation */ public String toString() { String out = "[\n"; int i = 0; for (List<Vertex> l : mOrigList) { out = out + "LinkedList[" + i++ + "]:\n"; for (Vertex step : l) { try { out = out + step.toString(); out = out + "\n"; } catch (Exception e) { out = out + "No Such Element\n"; } } } out = out + "]\n"; return out; }}
/*
* Copyright (c) 2000, 2006, 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.provider.certpath;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
/**
* An AdjacencyList is used to store the history of certification paths
* attempted in constructing a path from an initiator to a target. The
* AdjacencyList is initialized with a <code>List</code> of
* <code>List</code>s, where each sub-<code>List</code> contains objects of
* type <code>Vertex</code>. A <code>Vertex</code> describes one possible or
* actual step in the chain building process, and the associated
* <code>Certificate</code>. Specifically, a <code>Vertex</code> object
* contains a <code>Certificate</code> and an index value referencing the
* next sub-list in the process. If the index value is -1 then this
* <code>Vertex</code> doesn't continue the attempted build path.
* <p>
* Example:
* <p>
* Attempted Paths:<ul>
* <li>C1->C2->C3
* <li>C1->C4->C5
* <li>C1->C4->C6
* <li>C1->C4->C7
* <li>C1->C8->C9
* <li>C1->C10->C11
* </ul>
* <p>
* AdjacencyList structure:<ul>
* <li>AL[0] = C1,1
* <li>AL[1] = C2,2 =>C4,3 =>C8,4 =>C10,5
* <li>AL[2] = C3,-1
* <li>AL[3] = C5,-1 =>C6,-1 =>C7,-1
* <li>AL[4] = C9,-1
* <li>AL[5] = C11,-1
* </ul>
* <p>
* The iterator method returns objects of type <code>BuildStep</code>, not
* objects of type <code>Vertex</code>.
* A <code>BuildStep</code> contains a <code>Vertex</code> and a result code,
* accessable via getResult method. There are five result values.
* <code>POSSIBLE</code> denotes that the current step represents a
* <code>Certificate</code> that the builder is considering at this point in
* the build. <code>FOLLOW</code> denotes a <code>Certificate</code> (one of
* those noted as <code>POSSIBLE</code>) that the builder is using to try
* extending the chain. <code>BACK</code> represents that a
* <code>FOLLOW</code> was incorrect, and is being removed from the chain.
* There is exactly one <code>FOLLOW</code> for each <code>BACK</code>. The
* values <code>SUCCEED</code> and <code>FAIL</code> mean that we've come to
* the end of the build process, and there will not be any more entries in
* the list.
* <p>
* @see sun.security.provider.certpath.BuildStep
* @see sun.security.provider.certpath.Vertex
* <p>
* @author seth proctor
* @since 1.4
*/
public class AdjacencyList {
// the actual set of steps the AdjacencyList represents
private ArrayList<BuildStep> mStepList;
// the original list, just for the toString method
private List<List<Vertex>> mOrigList;
/**
* Constructs a new <code>AdjacencyList</code> based on the specified
* <code>List</code>. See the example above.
*
* @param list a <code>List</code> of <code>List</code>s of
* <code>Vertex</code> objects
*/
public AdjacencyList(List<List<Vertex>> list) {
mStepList = new ArrayList<BuildStep>();
mOrigList = list;
buildList(list, 0, null);
}
/**
* Gets an <code>Iterator</code> to iterate over the set of
* <code>BuildStep</code>s in build-order. Any attempts to change
* the list through the remove method will fail.
*
* @return an <code>Iterator</code> over the <code>BuildStep</code>s
*/
public Iterator<BuildStep> iterator() {
return Collections.unmodifiableList(mStepList).iterator();
}
/**
* Recursive, private method which actually builds the step list from
* the given adjacency list. <code>Follow</code> is the parent BuildStep
* that we followed to get here, and if it's null, it means that we're
* at the start.
*/
private boolean buildList(List<List<Vertex>> theList, int index,
BuildStep follow) {
// Each time this method is called, we're examining a new list
// from the global list. So, we have to start by getting the list
// that contains the set of Vertexes we're considering.
List<Vertex> l = theList.get(index);
try {
// we're interested in the case where all indexes are -1...
boolean allNegOne = true;
// ...and in the case where every entry has a Throwable
boolean allXcps = true;
for (Vertex v : l) {
if (v.getIndex() != -1) {
// count an empty list the same as an index of -1...this
// is to patch a bug somewhere in the builder
if (theList.get(v.getIndex()).size() != 0)
allNegOne = false;
}
else
if (v.getThrowable() == null)
allXcps = false;
// every entry, regardless of the final use for it, is always
// entered as a possible step before we take any actions
mStepList.add(new BuildStep(v, BuildStep.POSSIBLE));
}
if (allNegOne) {
// There are two cases that we could be looking at here. We
// may need to back up, or the build may have succeeded at
// this point. This is based on whether or not any
// exceptions were found in the list.
if (allXcps) {
// we need to go back...see if this is the last one
if (follow == null)
mStepList.add(new BuildStep(null, BuildStep.FAIL));
else
mStepList.add(new BuildStep(follow.getVertex(),
BuildStep.BACK));
return false;
} else {
// we succeeded...now the only question is which is the
// successful step? If there's only one entry without
// a throwable, then that's the successful step. Otherwise,
// we'll have to make some guesses...
List<Vertex> possibles = new ArrayList<Vertex>();
for (Vertex v : l) {
if (v.getThrowable() == null)
possibles.add(v);
}
if (possibles.size() == 1) {
// real easy...we've found the final Vertex
mStepList.add(new BuildStep(possibles.get(0),
BuildStep.SUCCEED));
} else {
// ok...at this point, there is more than one Cert
// which might be the succeed step...how do we know
// which it is? I'm going to assume that our builder
// algorithm is good enough to know which is the
// correct one, and put it first...but a FIXME goes
// here anyway, and we should be comparing to the
// target/initiator Cert...
mStepList.add(new BuildStep(possibles.get(0),
BuildStep.SUCCEED));
}
return true;
}
} else {
// There's at least one thing that we can try before we give
// up and go back. Run through the list now, and enter a new
// BuildStep for each path that we try to follow. If none of
// the paths we try produce a successful end, we're going to
// have to back out ourselves.
boolean success = false;
for (Vertex v : l) {
// Note that we'll only find a SUCCEED case when we're
// looking at the last possible path, so we don't need to
// consider success in the while loop
if (v.getIndex() != -1) {
if (theList.get(v.getIndex()).size() != 0) {
// If the entry we're looking at doesn't have an
// index of -1, and doesn't lead to an empty list,
// then it's something we follow!
BuildStep bs = new BuildStep(v, BuildStep.FOLLOW);
mStepList.add(bs);
success = buildList(theList, v.getIndex(), bs);
}
}
}
if (success) {
// We're already finished!
return true;
} else {
// We failed, and we've exhausted all the paths that we
// could take. The only choice is to back ourselves out.
if (follow == null)
mStepList.add(new BuildStep(null, BuildStep.FAIL));
else
mStepList.add(new BuildStep(follow.getVertex(),
BuildStep.BACK));
return false;
}
}
}
catch (Exception e) {}
// we'll never get here, but you know java...
return false;
}
/**
* Prints out a string representation of this AdjacencyList.
*
* @return String representation
*/
public String toString() {
String out = "[\n";
int i = 0;
for (List<Vertex> l : mOrigList) {
out = out + "LinkedList[" + i++ + "]:\n";
for (Vertex step : l) {
try {
out = out + step.toString();
out = out + "\n";
}
catch (Exception e) { out = out + "No Such Element\n"; }
}
}
out = out + "]\n";
return out;
}
}