path: root/src/org/noreply/fancydress/type3/PathSpec.java

/* $Id$ */
package org.noreply.fancydress.type3;

import org.noreply.fancydress.crypto.*;
import org.noreply.fancydress.status.*;
import org.noreply.fancydress.directory.*;
import org.noreply.fancydress.misc.Util;
import org.noreply.fancydress.type3.routing.*;
import java.net.InetAddress;
import java.util.*;


public class PathSpec {
	Directory dir;
	PathComponent[] pathComponents;
	boolean singleLeg;

	/**
	 * Class to hold one path component.
	 *
	 * A path component is either a component as defined in the mixminion
	 * path-spec, like a hop by nickname, one or more random hops, or
	 * gaussian hops; or it is the crossover point of a two-leg path spec.
	 */
	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;

		/**
		 * Constructor.
		 *
		 * @param dir A mixminion directory
		 * @param component the string representation of that component
		 */
		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;
			}
		}

		/**
		 * If this path component is the crossover point.
		 *
		 * @return true if this path component is the crossover point.
		 */
		public boolean isCrossover() {
			return (type == TYPE_CROSSOVER);
		}

		/**
		 * Get a number of hops statisfyi8ng this path component.
		 *
		 * @throws Error if this path spec is the crossover point.
		 */
		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;
				case TYPE_CROSSOVER :
					throw new Error("getHops() may not be called on the crossover point ");
				default :
					throw new Error("Unkown type "+type);
			}
			return result;
		}
	}

	/**
	 * Split a string on an optional crossover point, given by the
	 * separator token (colon).
	 *
	 * @param tokens the list of tokens to which the one or two new tokens are added.
	 * @param s the string to split.
	 */
	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);
		}
	}

	/**
	 * Parses a pathspec and returns an array of path components.
	 *
	 * @param dir A mixminion directory
	 * @param path the path specification to parse
	 * @return An array of PathComponent objects representing this pathSpec.
	 */
	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;
	}


	/**
	 * Create a path specification from a string.
	 *
	 * A path spec could look like "<code>Foo,Bar,?:Baz,*2,~1</code>".
	 *
	 * @param path given path
	 */
	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);
	}

	/**
	 * A class holding a list of Servers and a Crossover point location.
	 */
	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.
	 *
	 * @return a list of servers and a crossover point as an ServerWithCrossover object.
	 */
	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;
	}

	/**
	 * Return paths constructed from this PathSpec.
	 *
	 * Build paths from this pathspec that are able to deliver the payload
	 * in <code>payload</code>.
	 *
	 * 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(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;
	}
}