From a4c0d3d6d878da55435cb9d9cc8cff6199644199 Mon Sep 17 00:00:00 2001
From: Peter Palfrader <peter@palfrader.org>
Date: Sun, 19 Oct 2003 15:08:35 +0000
Subject: Support random path creation

---
 src/org/noreply/fancydress/type3/PathSpec.java | 366 +++++++++++++++++++++----
 1 file changed, 312 insertions(+), 54 deletions(-)

(limited to 'src/org/noreply/fancydress/type3/PathSpec.java')

diff --git a/src/org/noreply/fancydress/type3/PathSpec.java b/src/org/noreply/fancydress/type3/PathSpec.java
index cbc608f..9e975c6 100644
--- a/src/org/noreply/fancydress/type3/PathSpec.java
+++ b/src/org/noreply/fancydress/type3/PathSpec.java
@@ -11,53 +11,125 @@ import java.util.*;
 
 
 public class PathSpec {
-	String pathSpec;
-	Path singlePath;
+	Directory dir;
+	PathComponent[] pathComponents;
+	boolean singleLeg;
 
-	private String[] tokenize(String path) throws Mix3Exception {
-		ArrayList nicks = new ArrayList();
-		int indexFrom = 0;
-		int indexOf;
-
-		while ((indexOf = path.indexOf(',', indexFrom)) != -1) {
-			String v = path.substring(indexFrom, indexOf).trim();
-			if (v.equals(""))
-				throw new Mix3Exception("Invalid path.");
-			nicks.add( v );
-			indexFrom = indexOf + 1;
+	private class PathComponent {
+		public final static double GAUSS_STD_DEV = 1.5;
+
+		public final static int TYPE_NICKNAME = 1;
+		public final static int TYPE_RANDOM = 2;
+		public final static int TYPE_RANDOM_GAUSS = 3;
+		public final static int TYPE_CROSSOVER = 4;
+		int type;
+		Server byNickname;
+		int numRandoms;
+
+		public PathComponent(Directory dir, String component) throws Mix3BadArgumentsIllegalPathSpecException {
+			String c = component.trim();
+			if (c.equals(""))
+				throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: empty path component");
+			char b = c.charAt(0);
+			
+			Integer integer;
+			switch (b) {
+				case '*' :
+					try {
+						integer = new Integer(c.substring(1));
+					} catch (NumberFormatException e) {
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+					}
+					type = TYPE_RANDOM;
+					numRandoms = integer.intValue();
+					break;
+				case '~' :
+					try {
+						integer = new Integer(c.substring(1));
+					} catch (NumberFormatException e) {
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+					}
+					type = TYPE_RANDOM_GAUSS;
+					numRandoms = integer.intValue();
+					break;
+				case '?' :
+					if (c.length() > 1)
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+					type = TYPE_RANDOM;
+					numRandoms = 1;
+					break;
+				case ':' :
+					if (c.length() > 1)
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: illegal path component '"+c+"'");
+					type = TYPE_CROSSOVER;
+					break;
+				default :
+					Server server = dir.getServer(c);
+					if (server == null)
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' not found");
+					if (!server.isUseable())
+						throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Nickname '"+c+"' is not useable");
+					byNickname = server;
+					type = TYPE_NICKNAME;
+					break;
+			}
 		}
-		String v = path.substring(indexFrom).trim();
-		if (v.equals(""))
-			throw new Mix3Exception("Invalid path.");
-		nicks.add( v );
 
-		String[] result = new String[nicks.size()];
-		for (int i=0; i<result.length; i++)
-			result[i] = (String) nicks.get(i);
+		public boolean isCrossover() {
+			return (type == TYPE_CROSSOVER);
+		}
 
-		return result;
+		public Server[] getHops() {
+			Server[] result;
+			switch (type) {
+				case TYPE_NICKNAME :
+					result = new Server[1];
+					result[0] = byNickname;
+					break;
+				case TYPE_RANDOM :
+					result = new Server[numRandoms];
+					break;
+				case TYPE_RANDOM_GAUSS :
+					double d = CryptoPrimitives.normal(numRandoms, GAUSS_STD_DEV);
+					int num = (int) (d+0.5);
+					result = new Server[ num<0 ? 0 : num ];
+					break;
+				default :
+					throw new Error("Unkown type "+type);
+			}
+			return result;
+		}
 	}
 
-	private Hop[] parseHalfPath(Directory dir, String path) throws Mix3Exception {
-		String[] nicks = tokenize(path);
-		Hop[] hops = new Hop[nicks.length];
-
-		for (int i=0; i<hops.length; i++) {
-			Server server = dir.getServer(nicks[i]);
-			if (server == null)
-				throw new Mix3Exception("Invalid path: "+nicks[i]+" not found");
-			ServerDescriptor desc = server.getDescriptor();
-			IncomingMMTPSection incoming = desc.getIncomingMMTPSection();
-			Routing routing;
-
-			if (incoming.getHostname() != null) { /* FIXME */
-				routing = new RoutingHOST(incoming.getHostname(), incoming.getPort(), server.getKeyID());
-			} else {
-				routing = new RoutingIP4(incoming.getIP(), incoming.getPort(), server.getKeyID());
-			}
-			hops[i] = new Hop(routing, desc.getPacketKey());
+	private void splitCrossover(ArrayList tokens, String s) throws Mix3BadArgumentsIllegalPathSpecException {
+		int indexOf = s.indexOf(':');
+		if (indexOf != -1) {
+			String s1 = s.substring(0, indexOf).trim();
+			String s2 = s.substring(indexOf+1).trim();
+			if (s1.equals(""))
+				throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop before crossover point.");
+			if (s2.equals(""))
+				throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop after crossover point.");
+			tokens.add(s1.trim());
+			tokens.add(s2.trim());
+		} else {
+			if (s.equals(""))
+				throw new Mix3BadArgumentsIllegalPathSpecException("Invalid path: Empty hop in path.");
+			tokens.add(s);
 		}
-		return hops;
+	}
+
+	private PathComponent[] parsePath(Directory dir, String path) throws Mix3BadArgumentsIllegalPathSpecException {
+		ArrayList nicks = new ArrayList();
+		String[] tokens = Util.tokenize(path, ',');
+		for (int i=0; i<tokens.length; i++)
+			splitCrossover( nicks, tokens[i] );
+
+		PathComponent[] components = new PathComponent[nicks.size()];
+		for (int i=0; i<nicks.size(); i++)
+			components[i] = new PathComponent(dir, (String) nicks.get(i));
+
+		return components;
 	}
 
 
@@ -70,26 +142,212 @@ public class PathSpec {
 	 *
 	 * @param path given path
 	 */
-	public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3Exception {
-		this.pathSpec = pathSpec;
+	public PathSpec(Directory dir, String pathSpec, boolean singleLeg) throws Mix3BadArgumentsIllegalPathSpecException {
+		this.dir = dir;
+		this.singleLeg = singleLeg;
+
+		if (singleLeg) {
+			/* single legs do not have a crossover point */
+			int crossover = pathSpec.indexOf(':');
+			if (crossover >= 0)
+				throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: crossover point specified in single leg path.");
+		} else {
+			/* full paths may have up to one specified crossover point */
+			int crossover = pathSpec.indexOf(':');
+			if (crossover >= 0)
+				if (pathSpec.indexOf(':', crossover+1) >= 0)
+					throw new Mix3BadArgumentsIllegalPathSpecException("Path is not a valid path: more than one crossover points specified.");
+		}
+
+		this.pathComponents = parsePath(dir, pathSpec);
+	}
+
+	private class ServerWithCrossover {
+		public Server[] servers;
+		public int crossoverPoint;
+
+		public Server getLastServer() {
+			return (servers[servers.length - 1]);
+		}
+
+		public void setLastServer(Server s) {
+			servers[servers.length - 1] = s;
+		}
+
+		public Server getSecondToLastServer() {
+			return (servers[servers.length - 2]);
+		}
+
+		private void fillInRandoms() throws Mix3PathProblemException {
+			Server[] recommended = dir.getRecommendedServers();
+			for (int i=servers.length-1; i>=0 ; i--) {
+				if (servers[i] != null)
+					continue;
+				ArrayList s = new ArrayList();
+				for (int r=0; r<recommended.length; r++)
+					if (
+					    /* last hop or */
+					    ((i == servers.length-1) || (
+								      /* next hop is different */
+								      (recommended[r] != servers[i+1]) &&
+								      /* and can talk to next hop */
+								      dir.areFriends(recommended[r], servers[i+1]) )) &&
+					    /* first hop, or previos hop is random, or */
+					    ((i == 0) || (servers[i-1] == null) || (
+								      /* previous hop is different */
+								      (recommended[r] != servers[i-1]) &&
+								      /* and prev hop can talk to this */
+								      dir.areFriends(servers[i-1], recommended[r]) ))
+					   )
+						s.add(recommended[r]);
+				if (s.size() == 0)
+					throw new Mix3PathProblemException("Cannot find useable servers for random hop.");
+				servers[i] = (Server) s.get(CryptoPrimitives.randInt(s.size()));
+			}
+		}
+
+		public Path getPath() throws Mix3PathProblemException {
+			fillInRandoms();
+			Hop[] hops = new Hop[servers.length];
+			for (int i=0; i<hops.length ; i++)
+				hops[i] = new Hop(servers[i]);
+
+			if (crossoverPoint == -1)
+				crossoverPoint = (hops.length+1)/2;
+			int len1 = crossoverPoint;
+			int len2 = hops.length - len1;
+			Hop[] l1 = new Hop[len1];
+			Hop[] l2 = new Hop[len2];
+			System.arraycopy(hops, 0, l1, 0, len1);
+			System.arraycopy(hops, len1, l2, 0, len2);
+			return new Path(l1, l2);
+		}
+	}
+
+	/**
+	 * Concat path components, getting random amount of hops where requested.
+	 */
+	private ServerWithCrossover concatComponents() throws Mix3PathProblemException {
+		Server[][] components = new Server[pathComponents.length][];
+		int length = 0;
+		int crossoverBefore = -1;
+		for (int i=0; i<pathComponents.length ; i++) {
+			if (pathComponents[i].isCrossover())
+				crossoverBefore = length;
+			else {
+				components[i] = pathComponents[i].getHops();
+				length += components[i].length;
+			}
+		}
+		Server[] servers = new Server[length];
+		int c = 0;
+		for (int i=0; i<pathComponents.length ; i++) {
+			if (components[i] != null) {
+				System.arraycopy(components[i], 0, servers, c, components[i].length);
+				c += components[i].length;
+			}
+		}
+		if (c != length)
+			throw new Error ("Did not fill in length hops ("+c+" vs "+length+")");
+
+		ServerWithCrossover result = new ServerWithCrossover();
+		result.servers = servers;
+		result.crossoverPoint = crossoverBefore;
+		return result;
+	}
+
+	/**
+	 * get one instance of this path spec.
+	 * 
+	 * Also we filter acceptable exit nodes according to the payload's
+	 * constraints.
+	 *
+	 * @return one path constructed from the PathSpec
+	 */
+	/*
+	private Object getPathInstance() throws Mix3PathProblemException {
 
-		int crossover = pathSpec.indexOf(':');
-		if (crossover < 0)
-			throw new Mix3Exception("Path is not a valid path: no crossover point specified.");
+		ServerWithCrossover path = concatComponents();
+		fillInRandoms(path.components);
 
-		Hop[] leg1 = parseHalfPath(dir, pathSpec.substring(0, crossover));
-		Hop[] leg2 = parseHalfPath(dir, pathSpec.substring(crossover+1));
-		singlePath = new Path(leg1, leg2);
+		if (singleLeg)
+			throw new Error("not implemented yet"); // FIXME
+		else
+			return path.getPath();
 	}
+	*/
 
 	/**
-	 * Return a path constructed from this PathSpec
+	 * Return paths constructed from this PathSpec.
+	 *
+	 * Build paths from this pathspec that are able to deliver the payload
+	 * in <code>payload</code>.
 	 *
-	 * @param dir a directory
-	 * @return path
+	 * We build as many paths as <code>payload.numPackets()</code> requires.
+	 *
+	 * Also we filter acceptable exit nodes according to the payload's
+	 * constraints.
+	 *
+	 * @param payload the payload
+	 * @return paths constructed from the PathSpec
 	 */
-	public Path getPath() throws Mix3Exception {
-		return singlePath;
+	public Path[] getPath(Payload payload) throws Mix3PathProblemException {
+		if (singleLeg)
+			throw new IllegalArgumentException("getPath() may not be called for single leg path specs.");
+
+
+		ServerWithCrossover[] paths = new ServerWithCrossover[payload.numPackets()];
+		for (int i=0; i<paths.length; i++) {
+			paths[i] = concatComponents();
+			if (paths[i].servers.length < 2)
+				throw new Mix3PathProblemException("Path too short.");
+		}
+
+		Server lastHop = paths[0].getLastServer();
+		for (int i=1; i<paths.length; i++)
+			if (lastHop != paths[i].getLastServer())
+				throw new Mix3PathProblemException("Exit hop must be the same in all paths (random or fixed)");
+
+		Server[] possibleExitHops = payload.filterExithops( dir.getRecommendedServers() );
+		if (lastHop == null) {
+			boolean[] unuseable = new boolean[possibleExitHops.length];
+			for (int i=0; i<paths.length; i++) {
+				Server stls = paths[i].getSecondToLastServer();
+				if (stls == null)
+					continue;
+				for (int j=0; j<unuseable.length; j++)
+					if (unuseable[j])
+						continue;
+					else
+						if (! dir.areFriends(stls, possibleExitHops[j] ))
+							unuseable[j] = true;
+			}
+			ArrayList list = new ArrayList();
+			for (int j=0; j<unuseable.length; j++)
+				if (! unuseable[j])
+					list.add(possibleExitHops[j]);
+
+			if (list.size() == 0)
+				throw new Mix3PathProblemException("No useable exit hops found");
+
+			lastHop = (Server) list.get( CryptoPrimitives.randInt(list.size()) );
+			for (int i=0; i<paths.length; i++)
+				paths[i].setLastServer(lastHop);
+		} else {
+			boolean exitHopOK = false;
+			for (int j=0; j<possibleExitHops.length; j++)
+				if (possibleExitHops[j] == lastHop) {
+					exitHopOK = true;
+					break;
+				}
+			if (! exitHopOK)
+				throw new Mix3PathProblemException("Exit hop "+lastHop.getNickname()+" does not meet constraints.");
+		}
+
+		Path[] result = new Path[paths.length];
+		for (int i=0; i<paths.length; i++)
+			result[i] = paths[i].getPath();
+
+		return result;
 	}
 }
-
-- 
cgit v1.2.3