/*
    * Licensed to the Apache Software Foundation (ASF) under one
    * or more contributor license agreements.  See the NOTICE file
    * distributed with this work for additional information
    * regarding copyright ownership. The ASF licenses this file
    * to you under the Apache License, Version 2.0 (the
    * "License"); you may not use this file except in compliance
    * with the License. You may obtain a copy of the License at
    * 
   *      http://www.apache.org/licenses/LICENSE-2.0
   * 
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.river.tool;
  
  import java.io.BufferedReader;
  import java.io.File;
  import java.io.FileInputStream;
  import java.io.FileOutputStream;
  import java.io.InputStreamReader;
  import java.io.IOException;
  import java.io.PrintWriter;
  
  import java.lang.Comparable;
  import java.lang.reflect.Constructor;
  import java.lang.reflect.Field;
  import java.lang.reflect.Method;
  import java.lang.reflect.Modifier;
  
  import java.net.URL;
  import java.net.URLClassLoader;
  
  import java.text.MessageFormat;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Enumeration;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.MissingResourceException;
  import java.util.ResourceBundle;
  import java.util.StringTokenizer;
  import java.util.TreeSet;
  
  import java.util.jar.JarEntry;
  import java.util.jar.JarFile;
  import java.util.jar.JarInputStream;
  import java.util.jar.JarOutputStream;
  import java.util.jar.Manifest;
  
  import java.util.regex.Matcher;
  import java.util.regex.Pattern;
  
  /**
   * Tool used to generate the preferred class information for downloadable JAR
   * files in the form of a META-INF/PREFERRED.LIST required for use by the <code>
   * net.jini.loader.pref.PreferredClassLoader</code>. The list is generated by
   * examining the dependencies of classes contained within a target JAR file and
   * zero or more additional supporting JAR files.  Through various command-line
   * options, a set of "root" classes are identified as belonging to a public API.
   * These root classes provide the starting point for recursively computing a
   * dependency graph, finding all of the classes referenced in the public API of
   * the root classes, finding all of the classes referenced in turn by the public
   * API of those classes, and so on, until no new classes are found.  The results
   * of the dependency analysis are combined with the preferred list information
   * in the additional supporting JAR files to compute a preferred list having the
   * smallest number of entries that describes the preferred state of the classes
   * and resources contained in all of the JAR files. The output of the tool is a
   * new version of the target JAR file containing the generated preferred list,
   * and/or a copy of the list printed to <code>System.out</code>.
   * <p>
   * This tool implements the first guideline described in <code>
   * net.jini.loader.pref</code>.  In many cases it is sufficient to specify
   * the roots via the <code>-proxy</code> option. The <code>-api</code> and 
   * <code>-impl</code> options are used to generate lists for JAR files
   * in which the roots are not completely defined by the
   * proxy classes, or for non-service JAR files. Since there is no definitive 
   * set of rules for determining whether a class should be preferred, 
   * the developer should verify the correctness of the generated list.
   * <p>
   * The following items are discussed below:
   * <ul>
   * <li><a href="#running">Running the Tool</a>
   * <li><a href="#processing">Processing Options</a>
   * <li><a href="#examples">Examples</a>
   * </ul>
   *
   * <a name="running"></a>
   * <h3>Running the Tool</h3>
   *
   * To run the tool on UNIX platforms:
   * <blockquote><pre>
   * java -jar <var><b>install_dir</b></var>/lib/preferredlistgen.jar <var><b>processing_options</b></var>
   * </pre></blockquote>
   * To run the tool on Microsoft Windows platforms:
  * <blockquote><pre>
  * java -jar <var><b>install_dir</b></var>\lib\preferredlistgen.jar <var><b>processing_options</b></var>
  * </pre></blockquote>
  * <p>
  * Note that the options for this tool can be specified in any order, and
  * can be intermixed.
  *
  * <a name="processing"></a>
  * <h3>Processing Options</h3>
  * <p>
  * <dl>
  * <dt><b><code>-cp</code> <var>input_classpath</var></b>
  * <dd>Identifies the classpath for all of the classes that might need to be
  * included in the dependency analysis. Typically this will include all of your
  * application classes, classes from the JGDMS release, and any other classes on
  * which your classes might depend. It is safe to include more classes than are
  * actually necessary because the tool limits the scope of the preferred list to
  * those classes actually included in the JAR files being analyzed.  It is not
  * necessary to include the JAR files being analyzed in the classpath as they
  * will be appended automatically. It is also unnecessary to include any classes
  * that are part of the Java(TM) 2 SDK.  The class path should be in the form of a
  * list of directories or JAR files, delimited by a colon (":") on UNIX
  * platforms and a semi-colon (";") on Microsoft Windows platforms. The order of
  * locations in the path does not matter.
  * </dd>
  * </dl>
  * <dl>
  * <dt><b><code>-jar</code> <var>file</var></b>
  * <dd>Identifies a JAR file containing the classes to analyze. If the JAR
  * manifest includes a <code>Class-Path</code> attribute, then these JAR files
  * will also be processed recursively. The default behavior is to replace the
  * original JAR file with a new file containing the generated preferred list. If
  * the original target JAR file contained a preferred list, that list is ignored
  * and is replaced by the newly generated list. This option may be specified
  * zero or more times. If multiple <code>-jar</code> options are specified, the
  * first file specified is considered the target JAR file.
  * </dd>
  * 
  * <dt><b><code>-proxy</code> <var>classname</var></b>
  * <dd>Identifies the class name of a proxy in the target JAR file. All of the
  * public interfaces implemented by the proxy, and all of the public super
  * interfaces of any non-public interfaces implemented by the proxy, are
  * included in the set of roots for performing dependency analysis. This option
  * may be specified zero or more times.
  * </dd>
  * 
  * <dt><b><code>-api</code> <var>name-expression</var></b>
  * <dd>
  * This option identifies a class or a JAR entry, package, or namespace that is
  * to be considered public and therefore <b>not</b> preferred. If
  * <var>name-expression</var> ends with ".class", it represents a class whose
  * name is <var>name-expression</var> without the ".class" suffix and with each
  * '/' character replaced with a '.'. Otherwise, if <var>name-expression</var>
  * ends with "/" or "/*", it represents a directory wildcard matching all
  * entries in the named directory. Otherwise, if <var>name-expression</var> ends
  * with "/-", it represents a namespace wildcard that matches all entries in the
  * named directory and all of its subdirectories. Otherwise
  * <var>name-expression</var> represents a non-class resource in the JAR
  * file. Alternatively, <var>name-expression</var> may be expressed directly as
  * a class name. A nested (including inner) class must be expressed as a binary
  * class name; if <code>Bar</code> is a nested class of <code>Foo,</code> then
  * <code>Bar</code> would be expressed as <code>Foo$Bar</code>. The most
  * specific <var>name-expression</var> is used to match an entry. By default,
  * any public class in the JAR file that matches <var>name-expression</var> will
  * be included in the set of roots for dependency analysis. If
  * <var>name-expression</var> is a class name, then that class will be included
  * in the set of roots irregardless of its access modifier. If the
  * <code>-nonpublic</code> option is also present, then matching non-public
  * classes will also be included in the set of roots. The <code>-api</code>
  * option may be specified zero or more times.
  * <p>
  * As an example, presuming the class <code>org.apache.river.example.Foo</code>
  * was included in the target JAR file, then the following would all cause
  * that class to be included in the public API:
  * <blockquote><pre>
  *    -api org/apache/river/example/Foo.class
  *    -api org.apache.river.example.Foo
  *    -api org/apache/river/example/*
  *    -api org/apache/river/example/-
  * </pre></blockquote>
  * and the last example would also apply to, for instance,
  * <code>org.apache.river.example.gui.FooPanel</code>.
  * </dd>
  * 
  * <dt><b><code>-impl</code> <var>name-expression</var></b>
  * <dd>This option identifies a class or a JAR entry, package, or namespace that
  * is to be considered private and therefore preferred.
  * <var>name-expression</var> is interpreted as described for the
  * <code>-api</code> option. If <var>name-expression</var> is a class name or a
  * class JAR entry name, that class will be considered preferred and will not be
  * selected by or included in the dependency analysis even if it was included in
  * the set of roots as a result of processing the <code>-proxy</code> and
  * <code>-api</code> options. This option may be specified zero or more times.
  * </dd>
  * 
  * <dt><b><code>-nonpublic</code></b>
  * <dd>This option forces any non-public classes matched by the
  * <code>-api</code> <var>name-expression</var>s to be included in the set of
  * roots for dependency analysis.
  * </dd>
  *
  * <dt><b><code>-nomerge</code></b>
  * <dd>Causes the classes in JAR files which do not contain preferred
  * lists to be considered not preferred. If this option is not specified, all classes in 
  * JAR files which do not contain preferred lists are merged with the classes supplied by 
  * the target JAR file for purposes of dependency
  * analysis; the additional classes are not included in the generated target JAR file.
  * The <code>-impl</code> and <code>-api</code> options may be used to initialize
  * the preferred state of the merged classes. 
  * </dd>
  * 
  * <dt><b><code>-default</code> <var>false|true</var></b>
  * <dd>Specifies the default preferred value to use when generating the
  * preferred list and forces the generation of an explicit default preferred
  * entry in the preferred list.  If this option is not provided, the default
  * that produces a list with the fewest entries is used; an explicit entry for
  * the default <code>false</code> case will not be generated (except when no
  * single entry is found, in which case a default preferred value of
  * <code>false</code> is written). In the event of optimization ties, a default
  * value of <var>false</var> is used.
  * </dd>
  * 
  * <dt><b><code>-noreplace</code></b>
  * <dd>
  * Inhibits the replacement of the original JAR file with a new updated JAR
  * file. If this option is specified, the preferred list is printed on
  * <code>System.out</code>.
  * </dd>
  * 
  * <dt><b><code>-print</code></b>
  * <dd>
  * Causes the preferred list to be printed to <code>System.out</code>, even if
  * the list is also placed in an updated JAR file.
  * </dd>
  * 
  * <dt><b><code>-tell</code> <var>classname</var></b>
  * <dd>Specifies the fully qualified name of a class for which dependency
  * information is desired. This option causes the tool to display information
  * about every class in the dependency graph that references the specified
  * class. If no class references the specified class, it will be identified as a
  * root class. This information is sent to the error stream of the tool, not to
  * the normal output stream.  This option can be specified zero or more
  * times. If this option is used, all other output options are ignored, and the
  * normal class output is not produced. This option is useful for debugging.
  * </dd>
  * </dl>
  * 
  * Using values from the <code>-api</code> and <code>-impl</code> options, a
  * graph is constructed that defines initial preferred values to be inherited by
  * the target JAR entries as they are loaded into the graph. If there were no
  * such options specified, all entries from the target JAR file loaded into the
  * graph initially will be marked as preferred.  The classes and resources
  * identified by the first <code>-jar</code> option (the target JAR file) are
  * then loaded into this graph and are assigned their initial preferred
  * values. The remaining JAR files that include preferred lists are loaded into
  * the graph and the entries assigned preferred values based on the preferred
  * list contained in the JAR file being loaded. If a non-target JAR file does
  * not contain a preferred list, the default behavior is to merge the classes
  * and resources in the file with those of the target JAR file (for purposes of
  * dependency analysis only), making them subject to the <code>-api</code> and
  * <code>-impl</code> options.  The <code>-nomerge</code> option can be used to
  * override the default behavior, causing all such classes to be assigned a
  * value of not preferred.  The set of root classes is constructed by finding
  * all of the classes from the target JAR file that are marked as not preferred
  * in the graph, and by adding all of the public interfaces, or any public
  * superinterfaces of non-public interfaces implemented by the proxy classes
  * specified via the <code>-proxy</code> option. Starting with the root classes,
  * dependent classes are identified by examining the compiled class file for the
  * class, finding all of the public and protected fields, methods, constructors,
  * interfaces, and super classes it references, and then in turn examining those
  * classes. Any dependent classes found that also exist in the graph will be
  * marked not preferred, unless that class was explicitly named by a
  * <code>-impl</code> option. Any root class or dependent class named by a
  * <code>-impl</code> option retains its original preferred value and no further
  * dependency analysis is performed for the class.  The range of the dependency
  * analysis is restricted to the set of classes included in the graph.
  * <p> 
  * The tool then processes the graph to find the smallest number of preferred
  * list entries that describes the preferred state of all classes and resources
  * in the graph.  The resulting preferred list may be printed or included in a
  * JAR file that replaces the original (first) JAR file.
  * <p>
  * <a name="examples"></a>
  * <h3>Examples</h3>
  *
  * The following example generates the preferred list for the codebase JAR file
  * for reggie, replacing the original reggie-dl.jar with a new file containing
  * the preferred list. The reggie implementation includes four proxy classes,
  * however <code>org.apache.river.reggie.RegistrarProxy</code> and
  * <code>org.apache.river.reggie.AdminProxy</code> are not identified on the command
  * line because they are parent classes of
  * <code>org.apache.river.reggie.ConstrainableRegistrarProxy</code> and
  * <code>org.apache.river.reggie.ConstrainableAdminProxy</code>.
  * <p>
  * <blockquote><pre>
  * java -jar <var><b>install_dir</b></var>/lib/preferredlistgen.jar \
  *      -cp <var><b>install_dir</b></var>/lib/jsk-platform.jar \
  *      -jar <var><b>install_dir</b></var>/lib-dl/reggie-dl.jar \
  *      -jar <var><b>install_dir</b></var>/lib-dl/jsk-dl.jar \
  *      -proxy org.apache.river.reggie.ConstrainableRegistrarProxy \
  *      -proxy org.apache.river.reggie.ConstrainableAdminProxy 
  * </pre></blockquote>
  * <p>
  *
  * @author Sun Microsystems, Inc.
  */
 
 public class PreferredListGen {
 
     /** remember classes processed to avoid redundant work or loops */
     private final Collection seen;
     
     /* 
      * NOTE: the Boolean class is used extensively to represent the three
      *       possible states of a preferred value of true/false/undefined
      *       (for instance, if there is no default preferred value).
      */
 
     /** Boolean equivalent of true */
     private final Boolean TRUE;
 
     /** Boolean equivalent of false */
     private final Boolean FALSE;
 
     /** the names of proxies supplied by the -proxy option */
     private final Collection proxies;
 
     /** the set of classes to report based on the -tell options */
     private final Collection tells;
 
     /** the first JAR in the set of files loaded via the -jar option */
     private File targetJar;
 
     /** replace the first JAR with a copy containing the preferred list */
     private boolean replaceJar;
 
     /** print the preferred list, only meaningful with the -jar option */
     private boolean printResults;
 
     /** ordered list of JAR files names specified by the -jar options */
     private final Collection jarList;
 
     /** the classpath specified by the -cp option */
     private String classpath;
 
     /** the ordered graph containing the JAR class info */
     private final Graph listGraph;
 
     /** if true, use defaultToForce for default, otherwise optimize */
     private boolean forceDefault;
 
     /** the default preference value to force */
     private boolean defaultToForce;
 
     /** the class loader for resolving class names */
     private ClassLoader loader;
 
     /** I18N resource bundle */
     private static ResourceBundle resources;
 
     /** flag to indicate that initialization of resources has been attempted */
     private static boolean resinit = false;
 
     /** union of the entries in all JAR files for -api/-impl existence check */
     private final HashSet jarEntries;
 
     /** loaded JAR names, to avoid infinite loops due to circular definitions */
     private final HashSet jarFiles;
 
     /** if true, non-public roots are allowed */
     private boolean keepNonPublicRoots;
 
     /** if true, load JARs without preferred lists directly into listGraph */
     private boolean doMerge;
 
     /**
      * Get the strings from our resource localization bundle.
      */
     private synchronized static String getString(String key, Object v1, Object v2, Object v3) {
         String fmt = "no text found: \"" + key + "\"";
 	if (!resinit) {
 	    try {
 		resinit = true;
 		resources = ResourceBundle.getBundle
 		    ("org.apache.river.tool.resources.preflistgen");
 	    } catch (MissingResourceException e) {
 		e.printStackTrace();
 	    }
 	}
 	if (resources != null) {
 	    try {
 		fmt = resources.getString(key);
 	    } catch (MissingResourceException e) {
 	    }
 	}
 	return MessageFormat.format(fmt, new Object[]{v1, v2, v3});
     }
 
     /**
      * Return  the string according to resourceBundle format.
      */
     private static String getString(String key) {
 	return getString(key, null, null, null);
     }
 
     /**
      * Return  the string according to resourceBundle format.
      */
     private static String getString(String key, Object v1) {
 	return getString(key, v1, null, null);
     }
 
     /**
      * Return  the string according to resourceBundle format.
      */
     private static String getString(String key, Object v1, Object v2) {
 	return getString(key, v1, v2, null);
     }
 
     /**
      * Print out string according to resourceBundle format.
      */
     private static void print(String key, Object v1) {
 	System.err.println(getString(key, v1));
     }
 
     /**
      * Print out string according to resourceBundle format.
      */
     private static void print(String key, Object v1, Object v2) {
 	System.err.println(getString(key, v1, v2));
     }
 
     /**
      * Print out string according to resourceBundle format.
      */
     private static void print(String key, Object v1, Object v2, Object v3) {
 	System.err.println(getString(key, v1, v2, v3));
     }
 
      /**
      * Create a preferred list generator and process the command line arguments.
      *
      * @param args the command line arguments
      */
     private PreferredListGen(String[] args) {
         this.FALSE = Boolean.FALSE;
         this.TRUE = Boolean.TRUE;
         this.doMerge = true;
         this.keepNonPublicRoots = false;
         this.jarFiles = new HashSet();
         this.jarEntries = new HashSet();
         this.loader = getClass().getClassLoader();
         this.defaultToForce = false;
         this.forceDefault = false;
         this.forceDefault = false;
         this.listGraph = new Graph();
         this.jarList = new ArrayList();
         this.printResults = false;
         this.replaceJar = true;
         this.tells = new HashSet();
         this.proxies = new HashSet();
         this.seen = new HashSet();
         seen.add("int"); // mark primitives as already seen or stack traces fly
 	seen.add("long");
 	seen.add("float");
 	seen.add("double");
 	seen.add("short");
 	seen.add("void");
 	seen.add("char");
 	seen.add("byte");
 	seen.add("boolean");
 	if (args.length == 0) {
 	    throw new IllegalArgumentException(getString("preflistgen.noargs"));
 	}
 	for (int i = 0; i < args.length ; i++ ) {
 	    String arg = args[i];
 	    if (arg.equals("-print")) {
 		setPrint(true);
 	    } else if (arg.equals("-noreplace")) {
 		setReplaceJar(false);
 		setPrint(true);
 	    } else if (arg.equals("-jar")) {
 		addJar(args[++i]);
 	    } else if (arg.equals("-tell")) {
 		addTell(args[++i]);
 	    } else if (arg.equals("-impl")) {
 		addImpl(args[++i]);
 	    } else if (arg.equals("-api")) {
 		addApi(args[++i]);
 	    } else if (arg.equals("-nonpublic")) {
 		setKeepNonPublicRoots(true);
 	    } else if (arg.equals("-nomerge")) {
 		setMerge(false);
 	    } else if (arg.equals("-default")) {
 		String def = args[++i];
 		if (def.equalsIgnoreCase("true") 
 		    || def.equalsIgnoreCase("false")) 
 		{
 		    setDefault(def.equalsIgnoreCase("true"));
 		} else {
 		    String msg = getString("preflistgen.baddefault", def);
 		    throw new IllegalArgumentException(msg);
 		}
 	    } else if (arg.equals("-cp")) {
 		setClasspath(args[++i]);
 	    } else if (arg.equals("-proxy")) {
 		addProxy(args[++i]);
 	    } else {
 		String msg = getString("preflistgen.badoption", arg);
 		throw new IllegalArgumentException(msg);
 	    }
 	}
     }
     
     /**
      * Constructor for programmatic access. The public <code>set</code> and
      * <code>add</code> methods must be called to supply the argument
      * values. Then <code>compute</code> and <code>generatePreferredList</code>
      * must be called to perform the dependency analysis and to generate the
      * preferred list.
      */
     public PreferredListGen() {
         this.doMerge = true;
         this.keepNonPublicRoots = false;
         this.jarFiles = new HashSet();
         this.jarEntries = new HashSet();
         this.loader = (ClassLoader) getClass().getClassLoader();
         this.defaultToForce = false;
         this.forceDefault = false;
         this.forceDefault = false;
         this.listGraph = new Graph();
         this.jarList = new ArrayList();
         this.printResults = false;
         this.replaceJar = true;
         this.tells = new HashSet();
         this.proxies = new HashSet();
         this.FALSE = Boolean.FALSE;
         this.TRUE = Boolean.TRUE;
         this.seen = new HashSet();
 	seen.add("int"); // mark primitives as already seen or stack traces fly
 	seen.add("long");
 	seen.add("float");
 	seen.add("double");
 	seen.add("short");
 	seen.add("void");
 	seen.add("char");
 	seen.add("byte");
 	seen.add("boolean");
     }
 
     /**
      * Set the flag controlling whether a preferred list is to be printed.
      * This flag is ignored if the <code>PrintWriter</code> supplied in
      * the call to <code>generatePreferredList</code> is non-<code>null</code>.
      * The default value is <code>false</code>.
      *
      * @param printResults if <code>true</code>, print the preferred list
      */
     public final synchronized void setPrint(boolean printResults) {
 	this.printResults = printResults;
     }
 
     /**
      * Set the flag controlling whether non-public classes should be retained
      * in the set of roots used for performing dependency analysis. By default,
      * non-public classes are discarded.
      *
      * @param keepNonPublicRoots if <code>true</code>, non-public root classes
      *        are retained
      */
     public final synchronized void setKeepNonPublicRoots(boolean keepNonPublicRoots) {
 	this.keepNonPublicRoots = keepNonPublicRoots;
     }
 
     /**
      * Select the behavior for processing non-target JAR files which do not
      * contain preferred lists. If <code>doMerge</code> is <code>true</code>, the
      * classes contained in these JAR files are merged with the target JAR
      * file for purposes of dependency analysis. The <code>-impl</code> and
      * <code>-api</code> options may be used to initialize the preferred state
      * of the merged classes. If <code>doMerge</code> is <code>false</code>,
      * the classes in non-target JAR files which do not contain preferred lists are
      * initialized with a preferred state of 'not preferred'. The default behavior
      * corresponds to calling <code>setMerge(true)</code>.
      *
      * @param doMerge if <code>true</code>, perform the merge
      */
     public final synchronized void setMerge(boolean doMerge) {
 	this.doMerge = doMerge;
     }
 
     /**
      * Set the flag controlling whether a preferred list is to be placed
      * in the target JAR file. The default value is <code>true</code>.
      *
      * @param replaceJar if <code>true</code>, update the target JAR file
      */
     public final synchronized void setReplaceJar(boolean replaceJar) {
 	this.replaceJar = replaceJar;
     }
 
     /**
      * Add <code>jarName</code> to the list of JAR files to process.
      * The first call identifies the target JAR file. This method must
      * be called at least once.
      *
      * @param jarName the name of the JAR file to add to the set.
      */
     public final void addJar(String jarName) {
 	jarList.add(jarName);
     }
 
     /**
      * Add <code>tellName</code> to the tell list. If a class is identified
      * as not preferred through the dependency analysis, and if that class
      * name is in the tell list, then the source dependency causing the class to
      * be included is printed. This is for debugging purposes.
      *
      * @param tellName the name of the JAR file to add to the tell set.
      */
     public final void addTell(String tellName) {
 	String tellClass = fileToClass(tellName);
 	tells.add(tellClass);
     }
     
     /**
      * Initialize the dependency graph with a private API entry.
      * <code>implName</code> identifies a class or a JAR entry, package, or
      * namespace that is to be considered private and therefore preferred. If
      * <code>implName</code> ends with ".class", it represents a class whose
      * name is <code>implName</code> without the ".class" suffix and with each
      * '/' character replaced with a '.'. Otherwise, if <code>implName</code>
      * ends with "/" or "/*", it represents a directory wildcard matching all
      * entries in the named directory. Otherwise, if <code>implName</code> ends
      * with "/-", it represents a namespace wildcard that matches all entries in
      * the named directory and all of its subdirectories. Otherwise
      * <code>implName</code> represents a non-class resource in the JAR
      * file. Alternatively, <code>implName</code> may be expressed directly as a
      * class name. The most specific <code>implName</code> is used to match an
      * entry found in the JAR files being analyzed. If <code>implName</code> is
      * either of the class name forms, then that class is forced to be preferred
      * and is not included in the public API even it is found by the dependency
      * analysis.
      *
      * @param implName the identifier for the private API entry
      *
      * @throws IllegalArgumentException if <code>implName</code> does not match
      *         any of the criteria above.
      */
     public final void addImpl(String implName) {
 	listGraph.initialize(implName, true, null); // preferred 
     }
 
     /**
      * Initialize the dependency graph with a public API entry.
      * <code>apiName</code> identifies a class or a JAR entry, package, or
      * namespace that is to be considered public and therefore <b>not</b>
      * preferred. If <code>apiName</code> ends with ".class", it represents a
      * class whose name is <code>apiName</code> without the ".class" suffix and
      * with each '/' character replaced with a '.'. Otherwise, if
      * <code>apiName</code> ends with "/" or "/*", it represents a directory
      * wildcard matching all entries in the named directory. Otherwise, if
      * <code>apiName</code> ends with "/-", it represents a namespace wildcard
      * that matches all entries in the named directory and all of its
      * subdirectories. Otherwise <code>apiName</code> represents a non-class
      * resource in the JAR file. Alternatively, <code>apiName</code> may be
      * expressed directly as a class name. The most specific
      * <code>apiName</code> is used to match an entry found in the JAR files
      * being analyzed. Any class in the JAR file that matches
      * <code>apiName</code> will be included in the set of roots for dependency
      * analysis. This method may be called zero or more times.
      *
      * @param apiName the identifier for the public API entry
      *
      * @throws IllegalArgumentException if <code>apiName</code> does not match
      *         any of the criteria above.
      */
     public final void addApi(String apiName) {
 	listGraph.initialize(apiName, false, null); // not preferred
     }
 
     /**
      * Set the default value to use for the preferred list. If this method
      * is not called, the default will be chosen which results in a preferred
      * list with the smallest number of entries. In the event of optimization
      * ties, a default value of <code>false</code> is used.
      *
      * @param def the default value to use for the list
      */
     public final synchronized void setDefault(boolean def) {
 	forceDefault = true;
 	defaultToForce = def;
     }
 
     /**
      * Set the classpath of the classes to include in the analysis. It is
      * not necessary to include the JAR files supplied via calls to the
      * <code>addJar</code> method.
      *
      * @param path the classpath for the classes to include in the analysis
      */
     public final synchronized void setClasspath(String path) {
 	this.classpath = path;
     }
 	
     /**
      * Add <code>proxy</code> to the set of proxies used to identify
      * roots. This method may be called zero or more times.
      *
      * @param proxy the name of the proxy class
      */
     public final void addProxy(String proxy) {
 	proxies.add(proxy);
     }
 
 
     /**
      * Load all of the JAR files named on the command line or referenced in
      * Class-Path manifest entries of those JAR files.
      *
      * @throws IOException if an error occurs reading the contents
      *         of any of the JAR files.
      */
     private void loadJars() throws IOException {
 	Iterator it = jarList.iterator();
 	while (it.hasNext()) {
 	    String jarName = (String) it.next();
 	    File jarFile = new File(jarName);
 	    loadJar(jarFile);
 	}
     }
 
     /**
      * Load the given JAR <code>File</code>, adding every class or resource in
      * the file a graph. The first time this method is called,
      * <code>listGraph</code> is loaded directly and all non-preferred classes
      * found in the graph are marked as roots. On subsequent calls, a new
      * temporary graph is created and initialized based on the preferred list in
      * the JAR. After entries are loaded into the graph, it is merged into
      * <code>listGraph</code>. The manifest is also read, and any JARs specified
      * by the manifest <code>Class-Path</code> attribute are loaded
      * recursively. If the given JAR file does not exist or is a directory, an
      * error message is printed.
      *
      * @param jar the <code>File</code> representing the JAR file
      * @throws IOException if an error occured reading the contents
      *         of the JAR or any of the JARs in the Class-Path.
      * @throws IllegalArgumentException if the JAR file does not exist
      *         or is a directory
      */
     private synchronized void loadJar(File jar) throws IOException {
 	if (jarFiles.contains(jar)) {
 	    return; // short-circuit circular definitions
 	}
 	jarFiles.add(jar);
 	if (!jar.exists()) {
 	    String msg = getString("preflistgen.nojarfound", jar);
 	    throw new IllegalArgumentException(msg);
 	}
 	if (jar.isDirectory()) {
 	    String msg = getString("preflistgen.jarisdir", jar);
 	    throw new IllegalArgumentException(msg);
 	}
 	if (targetJar == null) {
 	    targetJar = jar;
 	    populateGraph(listGraph, jar);
 	} else if (doMerge && noPreferredList(jar)) {
 	    populateGraph(listGraph, jar);
 	} else {
 	    Graph g = createGraph(jar); // read pref list to init graph
 	    populateGraph(g, jar);
 	    listGraph.merge(g);
 	}
     }
 
     /**
      * Return <code>true</code> if the given JAR file does not contain a preferred list.
      *
      * @param jar the file to examine
      * @return true if no preferred list is present
      * @throws IOException if an error occured reading the contents of the JAR
      */
     private boolean noPreferredList(File jar) throws IOException {
 	JarFile jarFile = new JarFile(jar);
 	return jarFile.getJarEntry("META-INF/PREFERRED.LIST") == null;
     }
 
     /**
      * Load the given JAR <code>File</code>, adding every class or resource in
      * the file to the given graph. The manifest is also read, and any JARs
      * specified by the manifest <code>Class-Path</code> attribute are loaded
      * recursively. 
      *
      * @param g the graph to populate
      * @param jar the <code>File</code> representing the JAR file
      */
     private void populateGraph(Graph g, File jar) {
 	try {
 	    JarFile jarFile = new JarFile(jar);
 	    Enumeration en = jarFile.entries();
 	    while (en.hasMoreElements()) {
 		JarEntry entry = (JarEntry) en.nextElement();
 		String id = entry.getName();
 		if (id.startsWith("META-INF") || id.endsWith("/")) {
 		    continue; // ignore directories and anything in meta-inf 
 		}
 		jarEntries.add(id);
 		if (id.endsWith(".class")) {
 		    g.add(fileToClass(id), Graph.CLASS, jar);
 		} else {
 		    g.add(fileToClass(id), Graph.RESOURCE, jar);
 		}
 	    }
 	    Manifest manifest = jarFile.getManifest();
 	    if (manifest == null) {
 		return; // processed a zip file
 	    }
 	    String classPath = 
 		manifest.getMainAttributes().getValue("Class-Path");
 	    if (classPath != null) {
 		StringTokenizer tok = new StringTokenizer(classPath);
 		while (tok.hasMoreTokens()) {
 		    String fileName = tok.nextToken();
 		    File nextJar = new File(jar.getParentFile(), fileName);
 		    loadJar(nextJar);
 		}
 	    }
 	} catch (IOException e) {
 	    e.printStackTrace();
 	}
     }
 
     /**
      * Create a <code>Graph</code> initialized from the preferred list of
      * the given JAR file.
      *
      * @param jarFile the JAR file from which an initialized graph is
      *                to be derived
      * @return an initialized <code>Graph</code>
      * @throws IOException if an error occurs reading <code>jarFile</code>
      */
     private Graph createGraph(File jarFile) throws IOException {
 
 	final Pattern headerPattern = 
 	    Pattern.compile("^PreferredResources-Version:\\s*(.*?)$");
 	final Pattern versionPattern =
 	    Pattern.compile("^1\\.\\d+$");
 	final Pattern namePattern =
 	    Pattern.compile("^Name:\\s*(.*)$");
 	final Pattern preferredPattern =
 	    Pattern.compile("^Preferred:\\s*(.*)$");
 
 	/**
 	 * Parses the given JAR file's preferred list, if any.
 	 */
 	Graph graph = new Graph();
 	JarFile jar = new JarFile(jarFile);
 	JarEntry ent = jar.getJarEntry("META-INF/PREFERRED.LIST");
 	if (ent == null) {
 	    graph.setDefaultPref(false);
 	    return graph;
 	}
 	BufferedReader r = new BufferedReader(
 	    new InputStreamReader(jar.getInputStream(ent), "UTF8"));
 
 	String s = r.readLine();
 	if (s == null) {
 	    throw new IOException("missing preferred list header");
 	}
 	s = s.trim();
 	Matcher m = headerPattern.matcher(s);
 	if (!m.matches()) {
 	    throw new IOException("illegal preferred list header: " + s);
 	}
 	s = m.group(1);
 	if (!versionPattern.matcher(s).matches()) {
 	    throw new IOException(
 		"unsupported preferred list version: " + s);
 	}
 
 	s = nextNonBlankLine(r);
 	if (s == null) {
 	    throw new IOException("empty preferred list");
 	}
 	if ((m = preferredPattern.matcher(s)).matches()) {
 	    graph.setDefaultPref(Boolean.valueOf(m.group(1)).booleanValue());
 	    s = nextNonBlankLine(r);
 	} else {
 	    graph.setDefaultPref(false);
 	}
 
 	while (s != null) {
 	    if (!(m = namePattern.matcher(s)).matches()) {
 		throw new IOException(
 		    "expected preferred entry name: " + s);
 	    }
 	    String name = m.group(1);
 
 	    s = nextNonBlankLine(r);
 	    if (s == null) {
 		throw new IOException("EOF before preferred entry");
 	    }
 	    if (!(m = preferredPattern.matcher(s)).matches()) {
 		throw new IOException("expected preferred entry: " + s);
 	    }
 	    boolean pref = Boolean.valueOf(m.group(1)).booleanValue();
 	    graph.initialize(name, pref, jarFile);
 	    s = nextNonBlankLine(r);
 	}
 	return graph;
     }
 
     /**
      * Returns next non-blank, non-comment line, or null if end of file has
      * been reached.
      *
      * @param reader the input stream
      * @return a <code>String</code> containing the next line, 
      *         or <code>null</code>
      * @throws IOException if an error occurs reading the stream
      */
     private static String nextNonBlankLine(BufferedReader reader)
 	throws IOException
     {
 	String s;
 	while ((s = reader.readLine()) != null) {
 	    s = s.trim();
 	    if (s.length() > 0 && s.charAt(0) != '#') {
 		return s;
 	    }
 	}
 	return null;
     }
 
     /**
      * Convert the given class reference to a class name. If the argument is
      * already a class name, the value is returned unchanged. If the argument is
      * a file name, the equivalent class name is returned. Path names are in JAR
      * format: path separators must be '/' characters and the first character
      * must not be a path separator.
      *
      * @param classID the class identifier, which may be a class file
      *                reference or a class name
      * @return the associated class name
      */
     private String fileToClass(String classID) {
 	classID = classID.replace('/', '.'); 
 	if (classID.endsWith(".class")) {
 	    classID = classID.substring(0, classID.length() - 6);
 	}
         return classID;
     }
 
     /**
      * Inspect the given class for dependencies. If the class is an
      * array, it's component type is inspected. Inspection consists
      * of processing the classes name.
      *
      * @param from the dependent of the given class, or null if this
      *             is the top-level class
      * @param c the class to inspect
      */
     private void process(String from, Class c) {
 	while (c.isArray())
 	    c = c.getComponentType();
 	process(from, c.getName());
     }
 
     /**
      * Inspect the given array of classes for dependencies. 
      *
      * @param from the dependent of the given array, or null if this
      *             is the top-level class
      * @param arr the array of classes to inspect
      */
     private void process(String from, Class[] arr) {
 	for (int i = arr.length; --i >= 0; )
 	    process(from, arr[i]);
     }
 
     /**
      * Determine whether the given modifier imply inclusion in the public api.
      * Return <code>true</code> if the modifiers include the public or protected
      * flags.
      *
      * @param modifiers the modifier value
      * @return true if a public api member is implied
      */
     private boolean include(int modifiers) {
 	return (modifiers & (Modifier.PUBLIC | Modifier.PROTECTED)) != 0;
     }
 
     /**
      * Inspect the given constructor for dependencies. Any parameter types
      * and exception types declared for the constructor are inspected.
      *
      * @param from the dependent of the constructor, or null if this
      *             is the top-level class
      * @param c the constructor to inspect
      */
     private void process(String from, Constructor c) {
 	if (!include(c.getModifiers()))
 	    return;
 	process(from, c.getParameterTypes());
 	process(from, c.getExceptionTypes());
     }
 
     /**
      * Inspect the given method for dependencies. Any parameter types,
      * exception types, and the return type declared for the method
      * are inspected.
      *
      * @param from the dependent of the method, or null if this
      *             is the top-level class
      * @param m the method to inspect
      */
     private void process(String from, Method m) {
 	if (!include(m.getModifiers()))
 	    return;
 	process(from, m.getReturnType());
 	process(from, m.getParameterTypes());
 	process(from, m.getExceptionTypes());
     }
 
     /**
      * Inspect the given field for dependencies. The field type is inspected.
      *
      * @param from the dependent of the field, or null if this
      *             is the top-level class
      * @param f the field to inspect
      */
     private void process(String from, Field f) {
 	if (!include(f.getModifiers()))
 	    return;
 	process(from, f.getType());
     }
 
     /**
      * Mark the given class in the <code>Graph</code> as 'not preferred'
      * unless overridden by the command line <code>-impl</code> argument.
      * If so marked, then the public and private methods, fields,
      * constructors, interfaces, and superclasses declared by the class are
      * also inspected recursively. Only classes classes contained within
      * <code>listGraph</code> are processed.
      *
      * @param from the class referencing the given class, or null if this
      *             is the top-level class
      * @param clazz the class to add to the public api
      */
     private void process(String from, String clazz) {
 	if (!seen.contains(clazz)) {
 	    seen.add(clazz);
 	    if ( ! listGraph.contains(clazz)) {
 		return;
 	    }
 	    for (Iterator it = tells.iterator(); it.hasNext();) {
 		if (clazz.equals((String)it.next())) {
 		    if (from != null) {
 			System.err.println(clazz + " caused by " + from);
 		    } else {
 			System.err.println(clazz + " is a root class");
 		    }
 		}
 	    }
 	    if (!listGraph.setPreferred(clazz, false, false)) {
 		return;
 	    }
             try {
                 inspectClass(clazz);
             } catch (NoClassDefFoundError e){
                 System.err.println(e.toString());
             }
 	}
     }
 
     /**
      * Process all public and protected fields, methods, constructors,
      * interfaces, and superclasses declared by the given class.
      *
      * @param className the name of the class to process
      */
     private void inspectClass(String className) {
 	Class c;
 	try {
 	    c = Class.forName(className, false, loader);
 	} catch (Exception e) {
 	    e.printStackTrace();
 	    return;
 	}
 	Class sup = c.getSuperclass();
 	if (sup != null)
 	    process(className, sup);
 	Class[] ifaces = c.getInterfaces();
 	for (int i = ifaces.length; --i >= 0; )
 	    process(className, ifaces[i]);
 	Constructor[] cons = c.getDeclaredConstructors();
 	for (int i = cons.length; --i >= 0; ) {
 	    process(className, cons[i]);
 	}
 	Method[] methods = c.getDeclaredMethods();
 	for (int i = methods.length; --i >= 0; ) {
 	    process(className, methods[i]);
 	}
 	Field[] fields = c.getDeclaredFields();
 	for (int i = fields.length; --i >= 0; ) {
 	    process(className, fields[i]);
 	}
     }
 
     /**
      * Load JAR files, initialize the dependency graph, and perform the 
      * dependency analysis.
      *
      * @throws IOException if an error occurs constructing the class loader
      *         or reading any of the JAR files.
      * @throws IllegalArgumentException in the following cases:
      *         <ul>
      *         <li>if <code>addJar</code>  was never
      *             called or <code>addJar</code> was called with a file which
      *             does not exist or is a directory
      *         <li>if any proxies supplied via the <code>addProxy</code> 
      *             method could not be found 
      *         <li>if any component in the classpath does not exist 
      *         </ul>
      */
     public synchronized void compute() throws IOException {
 	if (jarList.isEmpty()) {
 	    throw new IllegalArgumentException(getString("preflistgen.nojars"));
 	}
         ArrayList list = new ArrayList();
 	if (classpath != null) {
 	    StringTokenizer st = new StringTokenizer(classpath, 
 						     File.pathSeparator);
 	    while (st.hasMoreTokens()) {
 		String fileName = st.nextToken();
 		File cpFile = new File(fileName);
 		if (!cpFile.exists()) {
 		    String msg = getString("preflistgen.badcp", fileName);
 		    throw new IllegalArgumentException(msg);
 		}
 		list.add(cpFile.getCanonicalFile().toURI().toURL());
 	    }
 	}
 	for (Iterator it = jarList.iterator(); it.hasNext(); ) {
 	    String fileName = (String) it.next();
 	    list.add(new File(fileName).getCanonicalFile().toURI().toURL());
 	}
 	if (list.size() > 0) {
 	    URL[] urls = (URL[]) list.toArray(new URL[list.size()]);
 	    ClassLoader cl = ClassLoader.getSystemClassLoader();
 	    if (cl != null) {
 		cl = cl.getParent(); // the extension classloader
 	    }
 	    loader = new URLClassLoader(urls, cl);
 	}
 	loadJars();
 	Collection roots = getRoots();
 	for (Iterator it = roots.iterator(); it.hasNext(); ) {
 	    String clazz = (String) it.next();
 	    Class c = null;
             try {
 		c = Class.forName(clazz, false, loader);
 	    } catch (ClassNotFoundException e) {
 		throw new IllegalStateException("could not load root class " + clazz);
 	    }
 	    if ((c.getModifiers() & Modifier.PUBLIC) == 0) {
 		if (keepNonPublicRoots) {
 		    print("preflistgen.rootNotPublic", c);
 		} else {
 		    if (!listGraph.isFrozen(clazz)) {
 			//remove non public root and force preferred
 			it.remove();
 			listGraph.setPreferred(clazz, true, true);
 			continue;
 		    }
 		}
 	    }
 	    process(null, clazz);
 	}
     }
        
     /**
      * Generate the <code>Collection</code> of roots to use for the dependency
      * analysis. All classes from the first JAR with a preferred state of false
      * (which will only be true due to the -api option, or because the same
      * class in another JAR is marked not-preferred) are added to the set;
      * Also, all interfaces of classes in the set of <code>-proxy</code>
      * arguments are added to the set of roots.
      *
      * @return the <code>Collection</code> of roots
      * @throws IllegalArgumentException if any of the proxies supplied via
      *         the <code>addProxy</code> method could not be found.
      */
     private Collection getRoots() {
 	HashSet roots = new HashSet();
 	listGraph.addRoots(roots);
 	Iterator proxyIt = proxies.iterator();
 	while (proxyIt.hasNext()) {
 	    String proxy = (String) proxyIt.next();
 	    try {
 		Class proxyClass = Class.forName(proxy, false, loader);
 		addProxyRoot(proxyClass, roots);
 	    } catch (ClassNotFoundException e) {
 		String msg = getString("preflistgen.badproxyclass", proxy);
 		throw new IllegalArgumentException(msg, e);
 	    }
         }
 	return roots;
     }
 
     /**
      * Add to the given set of roots the public interfaces implemented by 
      * the <code>proxyClass</code> and all of its superclasses.
      * If any non-public interfaces are implemented, then any parent
      * interfaces which are public are added.
      *
      * @param proxyClass the proxy to inspect
      * @param roots the set of root class names
      */
     private void addProxyRoot(Class proxyClass, Collection roots) {
 	Class[] interfaces = proxyClass.getInterfaces();
 	for (int j = 0; j < interfaces.length; j++) {
 	    addIfPublic(interfaces[j], roots);
 	}
 	Class superClass = proxyClass.getSuperclass();
 	if (superClass != null) {
 	    addProxyRoot(superClass, roots);
 	}
     }
 
     /**
      * Add to the given set of roots the interface named <code>intFace</code> if
      * that interface is public. Otherwise, add any superinterfaces which are
      * public.
      *
      * @param intFace the interface to add
      * @param roots the set of roots
      */
     private void addIfPublic(Class intFace, Collection roots) {
 	if ((intFace.getModifiers() & Modifier.PUBLIC) != 0) {
 	    roots.add(intFace.getName());
 	    return;
 	}
 	Class[] parents = intFace.getInterfaces();
         int l = parents.length;
 	for (int i = 0; i < l; i++) {
 	    addIfPublic(parents[i], roots);
 	}
     }
 
     /**
      * Print the usage message.
      */
     private static void usage() {
 	print("preflistgen.usage", null);
     }
 
     /**
      * Generate the preferred list from the dependency graph. If a default value
      * was specified, the optimal list using that default value is
      * generated. Otherwise, the optimal list among the two possibilities
      * (<code>false/true</code> in order of precedence for 'optimization ties')
      * is generated. An explicit default entry is generated only for the
      * default <code>true</code> case.
      * <p>
      * The preferred list is sorted such that more specific
      * definitions precede less specific definitions; ties are broken with
      * an alphabetic secondary sort.
      * <p>
      * The preferred list will be placed in the target JAR file unless
      * <code>setReplaceJar(false)</code> was called. The preferred list will be
      * written to <code>writer</code> if it is non-<code>null</code>.  If
      * <code>writer</code> is <code>null</code> and <code>setPrint(true)</code>
      * was called, the preferred list will be written to
      * <code>System.out</code>.
      *
      * @param writer the <code>PrintWriter</code> to write the preferred list 
      *               to. 
      *
      * @throws IOException if an error occurs updating the target JAR file.
      */
     public synchronized void generatePreferredList(PrintWriter writer) throws IOException {
 	if (writer == null && printResults) {
 	    writer = new PrintWriter(System.out);
 	}
 	String newLine = System.getProperty("line.separator");
 	if (!tells.isEmpty()) {
 	    return;
         }
 	StringBuilder sb = new StringBuilder();
 	sb.append("PreferredResources-Version: 1.0");
 	sb.append(newLine);
 	Collection entries = new TreeSet();
 	boolean pref;
 	listGraph.markStaleInnerClasses(); // throw away inners matching outers
 	listGraph.deleteStaleNodes(); // discard all stale nodes
 	if (forceDefault) {
 	    pref = defaultToForce;
 	    listGraph.setDefaultPref(pref);
 	    listGraph.addEntries(entries); // create sorted list of entries
 	} else {
 	    // create list using optimal default
 	    HashSet bestEntries = new HashSet();
 	    // first create entries for default=false 
 	    pref = false;
 	    listGraph.setDefaultPref(pref);
 	    listGraph.addEntries(bestEntries);
 	    // create entries for default=true and remember the best result
 	    HashSet test = new HashSet();
 	    listGraph.setDefaultPref(true);
 	    listGraph.addEntries(test);
 	    if (test.size() < bestEntries.size()) {
 		bestEntries = test;
 		pref = true;
 	    }
 	    entries = new TreeSet(bestEntries); // do the sort
 	}
 	if (pref || forceDefault || entries.isEmpty()) {
 	    sb.append(newLine);
 	    sb.append("Preferred: ");
 	    sb.append(pref);
 	    sb.append(newLine);
 	}
 	// write the individual entries
 	Iterator it = entries.iterator();
 	while (it.hasNext()) {
 	    PrefData entry = (PrefData) it.next();
 	    sb.append(newLine);
 	    sb.append("Name: ");
 	    sb.append(entry.name);
 	    sb.append(newLine);
 	    sb.append("Preferred: ");
 	    sb.append(entry.preferred);
 	    sb.append(newLine);
 	}
 	// output the resulting list or JAR file or both
 	String preferredList = sb.toString();
 	if (writer != null) {
 	    writer.print(preferredList);
 	    writer.flush();
 	}
 	if (replaceJar) {
 	    buildJarFile(preferredList);
 	}
     }
 
     /**
      * Replace the first JAR file in the set of JARs with a new copy containing
      * the given preferred list. If the JAR contained a preferred list, it is
      * replaced.
      *
      * @param preferredList the new preferred list
      * @throws IOException if an error occurs updating the target JAR file.
      */
     private void buildJarFile(String preferredList) throws IOException {
 	// prepare to create a temp JAR file from the original
 	File newJar = File.createTempFile("pref", "jar");
 	newJar.deleteOnExit();
 	JarInputStream ji = new JarInputStream(new FileInputStream(targetJar));
 	JarOutputStream jo = 
 	    new JarOutputStream(new FileOutputStream(newJar));
 	JarEntry entry;
 	byte[] ba;
 
 	// write the META-INF directory entry, probably not really necessary
 	entry = new JarEntry("META-INF/");
 	jo.putNextEntry(entry);
 	jo.closeEntry();
 
 	// copy the original manifest entry to the new file
 	entry = new JarEntry("META-INF/MANIFEST.MF");
 	jo.putNextEntry(entry);
 	ji.getManifest().write(jo);
 	jo.closeEntry();
 
 	// write the new preferred list entry to the new file
 	entry = new JarEntry("META-INF/PREFERRED.LIST");
 	jo.putNextEntry(entry);
 	ba = preferredList.getBytes();
 	jo.write(ba, 0, ba.length);
 
 	// copy the remaining entries, discarding the old preferred list
 	while ((entry = ji.getNextJarEntry()) != null) {
 	    if (entry.getName().equals("META-INF/PREFERRED.LIST")) {
 		ji.closeEntry();
 		continue;
 	    }
 	    jo.putNextEntry(entry);
 	    ba = new byte[1000];
 	    int size;
 	    while ((size = ji.read(ba, 0, 1000)) >= 0) {
 		jo.write(ba, 0, size);
 	    }
 	    jo.closeEntry();
 	}
 	ji.close();
 	jo.close();
 
 	// copy the new JAR file over the old one
 	FileInputStream fi = new FileInputStream(newJar);
 	FileOutputStream fo = new FileOutputStream(targetJar);
 	ba = new byte[1000];
 	int size;
 	while ((size = fi.read(ba)) >= 0) {
 	    fo.write(ba, 0, size);
 	}
 	fi.close();
 	fo.close();
     }
 
     /**
      * The command line interface to the tool. Parses the command line arguments,
      * computes the dependency graph, and generates the preferred list.
      *
      * @param args the command line arguments
      */
     public static void main(String[] args) {
 	try {
 	    PreferredListGen dep = new PreferredListGen(args);
 	    dep.compute();
 	    dep.generatePreferredList(null);
 	    System.exit(0);
 	} catch (IllegalArgumentException e) {
 	    print("preflistgen.badarg", e.getMessage());
 	    usage();
 	} catch (IOException e) {
 	    print("preflistgen.ioproblem", e.getMessage());
 	    e.printStackTrace();
 	} catch (Error e){
             print("preflistgen.error", e.getMessage());
 	    e.printStackTrace();
         }
 	System.exit(1);
     }
 
     /**
      * A representation of a class path, package path wildcard, or namespace
      * path wildcard preferred list entry. This class implements
      * <code>Comparable</code> to provide a primary sort key for the
      * ordering of class/path/namespace, and a secondary sort key which
      * is alphabetic.
      */ 
      private class PrefData implements Comparable { 
 
 	 /** the preferred list entry name string */
 	 final String name; 
 
 	 /** the preferred value for this entry */
 	 final boolean preferred;
 
 	 /** the sourceJar, used when merging two graphs */
 	 final File sourceJar;
 
 	PrefData(String name, boolean preferred) {
 	    this(name, preferred , null);
 	}
 
 	PrefData(String name, boolean preferred, File sourceJar) {
             this.name = name;
 	    this.preferred = preferred;
 	    this.sourceJar = sourceJar;
 	}
 
 	public int compareTo(Object o) {
 	    String oPrefixed = ((PrefData) o).prefixedString();
 	    return prefixedString().compareTo(oPrefixed);
 	}
 
 	private String prefixedString() {
 	    if (name.endsWith(".class")) {
 		return "a" + name;
 	    } else if (name.endsWith("/*")) {
 		return "b" + name;
 	    } else {
 		return "c" + name;
 	    }
 	}
     }
 
     /**
      * A representation of the graph of classes contained in the set of
      * JARs being analyzed. This class implements the search algorithm to
      * find the optimal (smallest) set of preferred list entries which
      * describes the preferred state of entries in the graph. Nodes in
      * the graph can be one of seven types:
      * <ul>
      *  <li><code>PKG</code> nodes represent package wildcards
      *  <li><code>NAMESPACE</code> nodes represent namespace wildcards
      *  <li><code>DEFAULT</code> nodes represent the default preference. Only
      *      the root node of the graph can be of this type.
      *  <li><code>INHERIT</code> nodes inherit their preference values from
      *      their parent nodes. For the case where there is no default
      *      preferred value, the root of the graph will be of this type.
      *  <li> <code>CLASS</code> leaf node representing a class
      *  <li> <code>RESOURCE</code> leaf node representing a non-class resource
      *  <li> <code>STALE</code> an entry which has been marked for deletion
      * </ul>
      * All non-terminal nodes represent a component in the package name
      * of a class. All leaf nodes represent classes or resources.
      */
     private class Graph {
 
 	/** type value when non-leaf node inherits preference from its parent */
 	static final int INHERIT = 0;
 
 	/** type value for package wildcard nodes */
 	static final int PKG = 1;
 
 	/** type value for namespace wildcard nodes */
 	static final int NAMESPACE = 2;
 
 	/** type value for the default preference (root) node */
 	static final int DEFAULT = 3;
 
 	/** type value for a class node */
 	static final int CLASS = 4;
 
 	/** type value for a resource (non-class JAR entry) node */
 	static final int RESOURCE = 5;
 
 	/** type value for a stale node (marked for deletion) */
 	static final int STALE = 6;
 
 	/** the name of this node (e.g. com or sun, not com.sun) */
 	String name;
 
 	/** the set of child nodes of this node */
 	HashSet nodes;
 
 	/** the preferred state, only meaningful to leaf (class) nodes */
 	boolean preferred;
 
 	/** the parent of this node, or null for the root node */
 	Graph parent;
 
 	/** the type of the node */
 	int type;
 
 	/** the preferred value implied for child nodes */
 	Boolean impliedPref = null;
 
 	/** the source JAR causing creation of this node, or null */
 	File sourceJar;
 
 	/**
 	 * Create the root node of the graph, setting implied pref to TRUE
 	 */
 	Graph() {
             this.type = INHERIT;
             this.sourceJar = null;
             this.parent = null;
             this.preferred = true;
             this.nodes = new HashSet();
 	    name = "";
 	    impliedPref = TRUE;
 	    type = DEFAULT;
 	}
 
 	/**
 	 * Create a node of the graph having the given name and parent.
 	 * If the name contains multiple '.' separated tokens, the name
 	 * is taken from the first token, and another node is constructed
 	 * using the remainder of the name and this node as the parent.
 	 * The final (leaf) node created is given a preferred value inherited
 	 * from its ancestors.
 	 *
 	 * @param parent the parent of this node, or <code>null</code> if
 	 *        this is the root node.
 	 * @param name the (possibly dot-separated) name for this node (and
 	 *        child nodes).
 	 * @param type the node type, must be CLASS or RESOURCE
 	 * @param sourceJar source of this node definition, or null defined
 	 *        through the -api or -impl options
 	 */
 	Graph(Graph parent, String name, int type, File sourceJar) {
             this.type = INHERIT;
             this.nodes = new HashSet();
 	    if (type != CLASS && type != RESOURCE) {
 		throw new IllegalStateException("type must be CLASS or "
 					        + "RESOURCE");
 	    }
 	    this.parent = parent;
 	    this.sourceJar = sourceJar;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		this.name = name;
 		this.type = type;
 		preferred = parent.childPref();
 		if (type == CLASS) {
 		    Graph outer = getOuter();
 		    /* if outer == null, then either this node does not represent
 		     * a nested class, or it represents a nested class who's outer
 		     * class hasn't been loaded yet. In either case, inheriting the
 		     * parents preference is the right thing to do because when the
 		     * outer class get loaded later it will also inherit the parents
 		     * preference value. 
 		     */
 		    if (outer != null) {
 			preferred = outer.preferred;
 		    }
 		}
 	    } else {
 		this.name = name.substring(0, firstDot);
 		nodes.add(new Graph(this, 
 				    name.substring(firstDot + 1), 
 				    type, 
 				    sourceJar));
 	    }
 	}
 
 	/**
 	 * Create a node of the graph having the given name, parent, type and
 	 * preferred value.  If the name contains multiple '.' separated tokens,
 	 * the name is taken from the first token, and another node is
 	 * constructed using the remainder of the name and this node as the
 	 * parent.  The type and preferred value are only set on the last node
 	 * created in the chain. 
 	 *
 	 * @param parent the parent of this node, or <code>null</code> if
 	 *        this is the root node.
 	 * @param name the (possibly dot-separated) name for this node (and
 	 *        child nodes).
 	 * @param type the node type, must not be INHERIT
 	 * @param preferred the preferred state of this node
 	 * @param sourceJar source of this node definition, or null defined
 	 *        through the -api or -impl options
 	 *
 	 * @throws IllegalStateException if type is INHERIT
 	 */
 	Graph(Graph parent, 
 	      String name, 
 	      int type, 
 	      boolean preferred, 
 	      File sourceJar) 
 	{
             this.type = INHERIT;
             this.preferred = true;
             this.nodes = new HashSet();
 	    if (type == INHERIT) {
 		throw new IllegalStateException("Cannot create a preference "
 					        + "node of type INHERIT");
 	    }
 	    this.parent = parent;
 	    this.sourceJar = sourceJar;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		this.name = name;
 		this.type = type;
 		if (type == CLASS || type == RESOURCE) {
 		    this.preferred = preferred;
 		} else {
 		    impliedPref = Boolean.valueOf(preferred);
 		}
 	    } else {
 		this.name = name.substring(0, firstDot);
 		String childName = name.substring(firstDot + 1);
 		nodes.add(new Graph(this, 
 				    childName, 
 				    type, 
 				    preferred, 
 				    sourceJar));
 	    }
 	}
 
 	/**
 	 * Determines whether <code>arg</code> represents a path reference to a
 	 * class, a resource, a package wildcard, or a namespace wild card, and
 	 * add the value, converted to a '.' separated name, to the graph with
 	 * the given preferred value and appropriate type. If <code>arg</code>
 	 * contains at least one '.' character and no '/' characters, assume it
 	 * is a class name and add the value to the graph with the given
 	 * preferred value and a type of <code>Graph.CLASS</code>.
 	 *
 	 * @param arg the name of the component to add to the graph
 	 * @param preferred the preferred value of the component
 	 * @throws IllegalArgumentException if <code>arg</code> is not
 	 *         a recognized form.
 	 */
 	void initialize(String arg, boolean preferred, File sourceJar) {
 	    if (name.length() > 0) {
 		throw new IllegalStateException("must initialize "
 						+ "only the root");
 	    }
 	    if (arg.endsWith("/-")) {
 		String pkgName = fileToClass(arg.substring(0, arg.length() - 2));
 		addWithPreference(pkgName, NAMESPACE, preferred, sourceJar);
 	    } else if (arg.endsWith("/*")) {
 		String pkgName = 
 		    fileToClass(arg.substring(0, arg.length() - 2));
 		addWithPreference(pkgName, PKG, preferred, sourceJar);
 	    } else if (arg.endsWith("/")) {
 		String pkgName = 
 		    fileToClass(arg.substring(0, arg.length() - 1));
 		addWithPreference(pkgName, PKG, preferred, sourceJar);
 	    } else if (arg.endsWith(".class")) { // class file reference
 		String leafName = fileToClass(arg);
 		addWithPreference(leafName, CLASS, preferred, sourceJar);
 	    } else if (arg.indexOf('/') != -1) { // resource file reference
 		String leafName = fileToClass(arg);
 		addWithPreference(leafName, RESOURCE, preferred, sourceJar);
 	    } else if (arg.indexOf('.') != -1) { // class name reference
 		addWithPreference(arg, Graph.CLASS, preferred, sourceJar);
 	    } else {
 		String msg = getString("preflistgen.badapi", arg);
 		throw new IllegalArgumentException(msg);
 	    }
 	}
 
 	/**
 	 * Add roots from this subtree of the graph to the given
 	 * collection of roots. If this is a CLASS node and this node
 	 * has a preferred value of <code>false</code> and was defined
 	 * by a command line option or was supplied by the first JAR file,
 	 * add this node to the collection.
 	 *
 	 * @param roots the collection to add to
 	 */
 	synchronized void addRoots(Collection roots) {
 	    if (type == CLASS && sourceJar == null) {
 	        String entryName = getFullName() + ".class";
 	        if (!jarEntries.contains(entryName)) {
 		    System.err.println("Class entry " + entryName
 				     + " identified by the -" 
 				     + (preferred ? "impl" : "api") 
 				     + " option does not exist in any JAR file. "
 				     + "That entry has been discarded");
 		    return;
 		}
 	    }
 	    if (type == CLASS  
 		&& !preferred 
 		&& (sourceJar == null || sourceJar == targetJar)) 
 	    {
 		roots.add(fileToClass(getFullName()));
 	    } else {
 		for (Iterator it = nodes.iterator();it.hasNext(); ) {
 		    Graph g = (Graph) it.next();
 		    g.addRoots(roots);
 		}
 	    }
 	}
 
 	/**
 	 * For non-leaf nodes,
 	 * Reset the type and implied preference value for this node
 	 * and all child nodes recursively. If this is a leaf node,
 	 * do nothing.
 	 */
 	synchronized void reset() {
 	    if (type != CLASS && type != RESOURCE) {
 		type = INHERIT;
 		impliedPref = null;
 		Iterator it = nodes.iterator();
 		while (it.hasNext()) {
 		    Graph g = (Graph) it.next();
 		    g.reset();
 		}
 	    }
 	}
 
 	/**
 	 * Return the implied preference as determined by the nearest
 	 * parent namespace wildcard, or the default preference if
 	 * there are no parent namespace wildcards. This method should
 	 * only be called indirectly as a side-effect of calling 
 	 * <code>childPref</code>.
 	 *
 	 * @return the implied preferred value
 	 */
 	synchronized boolean impliedChildPref() {
 	    if (type == NAMESPACE || type == DEFAULT) {
 		if (!(impliedPref instanceof Boolean)) {
 		    throw new IllegalStateException("impliedPref is null");
 		}
 		return impliedPref.booleanValue();
 	    }
 	    if (parent == null) {
 		throw new IllegalStateException("default undefined in graph");
 	    }
 	    return parent.impliedChildPref();
 	}
 
 	/**
 	 * Return the implied preference of the parent node if the parent is a
 	 * package wildcard. Otherwise, return the implied preference as
 	 * determined by the nearest parent namespace wildcard, or the default
 	 * preference if there are no parent namespace wildcards.
 	 *
 	 * @return the implied preferred value
 	 */
 	synchronized boolean childPref() {
 	    if (type == NAMESPACE || type == DEFAULT || type == PKG) {
 		if (impliedPref == null) {
 		    throw new IllegalStateException("impliedPref is null");
 	    }
 		return impliedPref.booleanValue();
 	    }
 	    if (parent == null) {
 		throw new IllegalStateException("default undefined in graph");
 	    }
 	    return parent.impliedChildPref();
 	}
 
 	/**
 	 * Set the default preferred value for the graph. This method
 	 * may only be called on the root node of the graph.
 	 *
 	 * @param value the default preferred value, which may be 
 	 *        <code>null</code> to indicate that no default is defined
 	 */
 	synchronized void setDefaultPref(boolean value) {
 	    if (name.length() > 0) {
 		throw new IllegalStateException("must set default on root");
 	    }
 	    type = DEFAULT;
 	    impliedPref = Boolean.valueOf(value);
 	}
 
 	// inherit javadoc
 	public String toString() {
 	    return "Graph[" + name + ", Parent = " + parent + "]";
 	}
 
 	/**
 	 * Add a child node to this node having the given name. the name
 	 * may have multiple '.' separated components, in which case a
 	 * hierarchy of child nodes will be added. Only child nodes which
 	 * do not already exist are created. The preferred value for
 	 * the child will be set based on the value inherited from its
 	 * ancestors. Nodes added by this method must always be leaf nodes.
 	 * 
 	 * @param name the name of the child node to add
 	 * @param type the node type, must be CLASS or RESOURCE
 	 * @param sourceJar the JAR file causing this class or resource to be added
 	 */
 	synchronized void add(String name, int type, File sourceJar) {
 	    if (type != CLASS && type != RESOURCE) {
 		throw new IllegalStateException("type must be CLASS or "
 						+ "RESOURCE");
 	    }
 	    if (name == null) { // added previously - noop
 		return;
 	    }
 	    String nodeName;
 	    String childName = null;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		nodeName = name;
 	    } else {
 		nodeName = name.substring(0, firstDot);
 		childName = name.substring(firstDot + 1);
 	    }
 	    Iterator it = nodes.iterator();
 	    // search for a match to an existing child and recursively add
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(nodeName)) {
 		    g.add(childName, type, sourceJar); // noop if null
 		    return;
 		}
 	    }
 	    // if here, name doesn't exist in collection of child nodes
 	    nodes.add(new Graph(this, name, type, sourceJar));
 	}
 
 	/**
 	 * Return <code>true</code> if the graph contains a node having
          * the given name.
 	 * 
 	 * @param name the name of the node to test for
          * @return true if the node is found
 	 */
 	synchronized boolean contains(String name) {
 	    String nodeName;
 	    String childName = null;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		nodeName = name;
 	    } else {
 		nodeName = name.substring(0, firstDot);
 		childName = name.substring(firstDot + 1);
 	    }
 	    Iterator it = nodes.iterator();
 	    // search for a match to an existing child and recursively add
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(nodeName)) {
 		    if (childName == null) {
 			return true;
 		    } else {
 			return g.contains(childName);
 		    }
 		}
 	    }
 	    // if here, name doesn't exist in collection of child nodes
 	    return false;
 	}
 
 	/**
 	 * Return the frozen state of the class node having the
 	 * given name. A node is frozen if it was created through 
 	 * the <code>-api</code> or <code>-impl</code> options.
 	 *
 	 * @param name the dot-separate name
 	 * @return true if the node is frozen
 	 */
 	synchronized boolean isFrozen(String name) {
 	    String nodeName;
 	    String childName = null;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		nodeName = name;
 	    } else {
 		nodeName = name.substring(0, firstDot);
 		childName = name.substring(firstDot + 1);
 	    }
 	    Iterator it = nodes.iterator();
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(nodeName)) {
 		    if (childName == null) {
 			if (g.type != CLASS) {
 			    throw new IllegalStateException("Not a class: "
 							    + g.getFullName());
 			}
 			return g.sourceJar == null; // set by -api/-impl
 		    } else {
 			return g.isFrozen(childName);
 		    }
 		}
 	    }
 	    // if here, name doesn't exist in collection of child nodes
 	    return false;
 	}
 
 
 
 	/**
 	 * Add a child node to this node having the given name. the name may
 	 * have multiple '.' separated components, in which case a hierarchy of
 	 * child nodes will be added. Only child nodes which do not already
 	 * exist are created. The final node created will be assigned the given
 	 * type and preferred value. If the node already exists, new type and
 	 * preferred values will be assigned unless the original source JAR is
 	 * null, indicating node was created via the -api or -impl options.  The
 	 * source JAR is not changed from it's original value. If the node
 	 * already exists, the original source JAR is non-null and is also not
 	 * the first JAR, this is a leaf node, and preferred values differ, a
 	 * warning message is written to System.err to identify the conflicting
 	 * definitions; in this case, the state of the node is set to
 	 * not-preferred. The first JAR is ignored in this case because the
 	 * correct value for the preferred state of these classes is not known
 	 * until the dependency analysis is done. Therefore in this special case
 	 * the preferred state is reset to the new state.
 	 * 
 	 * @param name the name of the child node to add
 	 */
 	synchronized void addWithPreference(String name, 
 			       int type, 
 			       boolean preferred, 
 			       File sourceJar) 
 	{
 	    if (type == INHERIT) {
 		throw new IllegalStateException("Cannot add preference node "
 						+ "of type INHERIT");
 	    }
 	    // allow type to be redefined - should probably do an analysis
 	    if (name == null) {
 		if (this.sourceJar != null) {
 		    this.type = type;
 		    if (type == CLASS || type == RESOURCE) {
 			if(this.preferred != preferred 
 			   && this.sourceJar != targetJar) 
 			{
 			    print("preflistgen.prefconflict",
 				  getFullName(),
 				  this.sourceJar,
 				  sourceJar);
 			    this.preferred = false;
 			} else {
 			    this.preferred = preferred;
 			}
 		    } else {
 			impliedPref = Boolean.valueOf(preferred);
 		    }
 		}
 		return;
 	    }
 	    String nodeName;
 	    String childName = null;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot < 0) {
 		nodeName = name;
 	    } else {
 		nodeName = name.substring(0, firstDot);
 		childName = name.substring(firstDot + 1);
 	    }
 	    Iterator it = nodes.iterator();
 	    // search for a match to an existing child and recursively add
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(nodeName)) {
 		    g.addWithPreference(childName, type, preferred, sourceJar);
 		    return;
 		}
 	    }
 	    // if here, name doesn't exist in collection of child nodes
 	    nodes.add(new Graph(this, name, type, preferred, sourceJar));
 	}
 
 	/**
 	 * Set the preferred state of the leaf (class) child node having the
 	 * given '.' qualified name to the given value. If <code>name</code>
 	 * is <code>null</code>, set the preferred value for this node.
 	 * If the target name does not exist in the graph, this method
 	 * is a noop.
 	 * <p>
 	 * This method enforces the requirement that the ultimate target
 	 * node for the call must be a leaf node. 
 	 *
 	 * @param name the name of the child node to set, or <code>null</code>
 	 *             to represent this node
 	 * @param value the preferred value to set.
 	 * @param force if true, ignore frozen state
 	 * @return true if the preferred value matches <code>value</code>
 	 *              or is changed to <code>value</code> or if the named
 	 *              node does not exist in the graph. Returns
 	 *              <code>false</code> if the values don't match and
 	 *              the node is frozen and force is false.
   	 */
 	synchronized boolean setPreferred(String name, boolean value, boolean force) {
 	    if (name == null) {
 		if (type != CLASS && type != RESOURCE) {
 		    throw new IllegalStateException("only leaf node preferred"
 						     + " state may be set");
 		}
 		if (sourceJar != null || force) { // frozen if defined by -api or -impl
 		    preferred = value;
 		}
 		return preferred == value;
 	    }
 	    String childName = name;
 	    String targetName = null;
 	    int firstDot = name.indexOf(".");
 	    if (firstDot >= 0) { // must have reached the leaf node
 		childName = name.substring(0, firstDot);
 		targetName = name.substring(firstDot + 1);
 	    }
 	    Iterator it = nodes.iterator();
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(childName)) {
 		    return g.setPreferred(targetName, value, force);
 		}
 	    }
 	    // if here, name doesn't exist in the graph - noop
 	    return true;
 	}
 
 	/**
 	 * Count the number of child leaf nodes which
 	 * have a preferred state matching the given value. If this
 	 * is a leaf node, return 1 if the value matches the preferred
 	 * state of this node.
 	 *
 	 * @param value the preferred value to search for
 	 * @return the number of leaf nodes having the given value
 	 */
 	synchronized int countPreferred(boolean value) {
 	    if (type == CLASS || type == RESOURCE) { // leaf 
 		return (value == preferred) ? 1 : 0;
 	    } else {
 		int total = 0;
 		Iterator it = nodes.iterator();
 		while (it.hasNext()) {
 		    Graph g = (Graph) it.next();
 		    total += g.countPreferred(value);
 		}
 		return total;
 	    }
 	}
 
 	/**
 	 * Count the number of child leaf (class) nodes which have a preferred
 	 * state which differs from the value implied by * its ancestors. If
 	 * this is a leaf node and is also a nested class, return 1 if the outer
 	 * class has a different preferred state than this class. If this is a
 	 * leaf node and is not a nested class, return 1 if the implied value
 	 * differs the preferred state for this node. If no value is implied
 	 * by the ancestors, this is interpreted as a mismatch.
 	 *
 	 * @return the number of leaf nodes having preferred values which differ
          *         from that implied by its ancestors
 	 */
 	synchronized int countImpliedFailures() {
 	    if (type == CLASS || type == RESOURCE) { // leaf 
 		if (type == CLASS) {
 		    Graph outer = getOuter();
 		    if (outer != null) {
 			return (outer.preferred == preferred) ? 0 : 1;
 		    }
 		}
 		return (parent.childPref() != preferred) ? 1 : 0;
 	    } else {
 		int total = 0;
 		Iterator it = nodes.iterator();
 		while (it.hasNext()) {
 		    Graph g = (Graph) it.next();
 		    total += g.countImpliedFailures();
 		}
 		return total;
 	    }
 	}
 
 	/**
 	 * Count the number of child leaf nodes.
 	 *
 	 * @return the number of leaf nodes which have this node
 	 *         as an ancestor.
 	 */
 	synchronized int countLeafNodes() {
 	    int total = 0;
 	    Iterator it = nodes.iterator();
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.type == CLASS || g.type == RESOURCE) { // leaf node
 		    total++;
 		} else {
 		    total += g.countLeafNodes();
 		}
 	    }
 	    return total;
 	}
 
 	/**
 	 * Return the full name of this node expressed as a relative
 	 * path. No suffixes (".class", "/-", "/*") are appended.
 	 *
 	 * @return the full path name representing this node
 	 */
 	String getFullName() {
 	    if (name.length() == 0) {
 		return "";
 	    }
 	    String prefix = "";
 	    if (parent != null) {
 		prefix = parent.getFullName();
 	    }
 	    if (prefix.length() > 0) {
 		prefix += "/";
 	    }
 	    return prefix + name;
 	}
 
 	/**
 	 * If this node is of type CLASS and is an inner class, mark this node
 	 * as STALE if the outer class has the same preferred value. Print a
 	 * warning to <code>System.err</code> if they do not have the same
 	 * value. If there is no outer class corresponding to the inner class,
 	 * this node is retained. Call this method on all children.
 	 */
 	synchronized void markStaleInnerClasses() {
 	    if (type == CLASS) {
 		Graph outer = getOuter();
 		if (outer != null) {
 		    if (outer.preferred == preferred) {
 			type = STALE;
 		    } else {
 			print("preflistgen.innerwarn", outer.name, name);
 		    }
 		}
 	    } else {
 		for (Iterator it = nodes.iterator(); it.hasNext(); ) {
 		    Graph g = (Graph) it.next();
 		    g.markStaleInnerClasses();
 		}
 	    }
 	}
 
 	/**
 	 * Return the node for the outer class for this class if this is a nested
 	 * class. 
 	 *
 	 * @return the graph for the outer class, or <code>null</code> if this is
 	 *         not a nested class, or if the outer class is not in the graph
 	 */
 	final synchronized Graph getOuter() {
 	    if (type != CLASS) {
 		throw new IllegalStateException("Attempt to get outer of a non-class");
 	    }
 	    Graph g = null;
 	    int lastDollar = name.lastIndexOf('$');
 	    if (lastDollar > 0) {
 		String outerName = name.substring(0, lastDollar);
 		g = parent.getChild(outerName);
 	    }
 	    return g;
 	}
 
 	/**
 	 * Recursively remove child nodes of type STALE.
 	 */
 	synchronized void deleteStaleNodes() {
 	    for (Iterator it = nodes.iterator(); it.hasNext(); ) {
 		Graph g = (Graph) it.next();
 		if (g.type == STALE) {
 		    it.remove();
 		} else {
 		    g.deleteStaleNodes();
 		}
 	    }
 	}
 
 	/**
 	 * Get the child node having the given name.
 	 *
 	 * @param name the child name
 	 * @return the child <code>Graph</code> object, or null if the
 	 *         no child named <code>name</code> exists
 	 */
 	Graph getChild(String name) {
 	    for (Iterator it = nodes.iterator(); it.hasNext(); ) {
 		Graph g = (Graph) it.next();
 		if (g.name.equals(name)) {
 		    return g;
 		}
 	    }
 	    return null;
 	}
 
 	/**
 	 * Test whether all of the immediate child nodes of this
 	 * node are leaf (class) nodes.
 	 *
 	 * @return <code>true</code> if all a the nodes are leaf nodes
 	 */
 	synchronized boolean containsLeavesOnly() {
 	    Iterator it = nodes.iterator();
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		if (g.type != CLASS && g.type != RESOURCE) { // must be subpkg
 		    return false;
 		}
 	    }
 	    return true;
 	}
 
 	synchronized void addLeaves(Collection leaves) {
 	    if (type == CLASS) { 
 		leaves.add(new PrefData(getFullName() + ".class", 
 					preferred, 
 					sourceJar));
 		return;
 	    }
 	    if (type == RESOURCE) {
 		leaves.add(new PrefData(getFullName(), preferred, sourceJar));
 		return;
 	    }
 	    Iterator it = nodes.iterator();
 	    while (it.hasNext()) {
 		Graph g = (Graph) it.next();
 		g.addLeaves(leaves);
 	    }
 	    return;
 	}
 	
 	synchronized void merge(Graph g) {
 	    Collection leaves = new HashSet();
 	    g.addLeaves(leaves);
 	    Iterator it = leaves.iterator();
 	    while (it.hasNext()) {
 		PrefData data = (PrefData) it.next();
 		int type = ((data.name.endsWith(".class") ? CLASS : RESOURCE));
 		addWithPreference(fileToClass(data.name), 
 				  type,
 				  data.preferred, 
 				  data.sourceJar);
 	    }
 	}
 
 	/**
 	 * Add preferred list entries (represented by <code>PrefData</code>
 	 * objects) to the given <code>Collection</code>. One of the following
 	 * cases is handled:
 	 * <ul>
 	 *  <li>if this is the root node, then <code>addEntries</code> is 
 	 *      called on each of the child nodes. Otherwise:
 	 *  <li>if the preferred state of all leaf nodes (including possibly
 	 *      this one) matches the implied state provided by the ancestors,
 	 *      then return without adding any entries. Otherwise:
 	 *  <li>if this is a leaf node and its preferred state does not
 	 *      match the state implied by its parent, add a class style
 	 *      entry to the collection and return. Otherwise:
 	 *  <li>if this is not a leaf node, and there is a single child
 	 *      which is also not a leaf node, then this node represents
 	 *      an intermediate component in a package name. Call 
 	 *      <code>addEntries</code> on the child to generate a more
 	 *      qualified entry. Otherwise:
 	 *  <li>if this is not a leaf node and all of the child leaf nodes
 	 *      have the same preferred value, then make this a package
 	 *      wildcard having that value (if all children are leaves)
 	 *      or make this a namespace wildcard having that value (if
 	 *      some children are not leaves). Otherwise:
 	 *  <li>try all variations of package/namespace wildcards, as well
 	 *      as no wildcard setting, for this node. Add an entry
 	 *      to the collection giving the optimal (minimal) result, then
 	 *      call <code>addEntries</code> on all children.
 	 * </ul>
 	 * 
 	 */
 	synchronized void addEntries(Collection entries) {
 	    if (parent == null) {
 		Iterator it = nodes.iterator();
 		while (it.hasNext()) {
 		    Graph g = (Graph) it.next();
 		    g.addEntries(entries);
 		}
 		return;
 	    }
 	    reset(); // set all non-leaf nodes to type = INHERIT
 	    if (countImpliedFailures() == 0) {
 		return;
 	    }
 	    if (type == CLASS) { // entry failed previous count test
 		entries.add(new PrefData(getFullName() + ".class", preferred));
 		return;
 	    }
 	    if (type == RESOURCE) { // entry failed previous count test
 		entries.add(new PrefData(getFullName(), preferred));
 		return;
 	    }
 	    // special case - find max qualified variant of pkg name
 	    if (nodes.size() == 1) {
 		Iterator it = nodes.iterator();
 		if (! it.hasNext()) {
 		    throw new IllegalStateException("Inconsistent iterator");
 		}
 		Graph g = (Graph) it.next();
 		if (g.type != CLASS && g.type != RESOURCE) { // must be subpkg
 		    g.addEntries(entries);
 		    return;
 		}
 	    }
 	    /*
 	     * if here, some children have actual preferences which don't match
 	     * their implied preferences. Check whether all children have
 	     * the same preference value, and if so, make this node a
 	     * wildcard package (if all immediate children are leaves)
 	     * or a wildcard namespace otherwise (if at least one child
 	     * is a non-leaf)
 	     */
 	    boolean gotMatch = false;
 	    boolean matchValue = false;
 	    int leafCount = countLeafNodes();
 	    if (leafCount == countPreferred(true)) {
 		gotMatch = true;
 		matchValue = true;
 	    } else if (leafCount == countPreferred(false)) {
 		gotMatch = true;
 		matchValue = false;
 	    }
 	    if (gotMatch) {
 		if (containsLeavesOnly()) {
 		    entries.add(new PrefData(getFullName() + "/*", matchValue));
 		} else {
 		    entries.add(new PrefData(getFullName() + "/-", matchValue));
 		}
 		return;
 	    }
 	    /*
 	     * if here, children have a mix of preferred values. Find
 	     * which variation of wildcard type (if any) to assign to
 	     * this node to optimize the entries generated by children
 	     */
 	    int lowestValue = countEntries(INHERIT, null);
 	    int bestType = INHERIT;
 	    Boolean bestImpliedPref = null;
 	    // do PKG before NAMESPACE so 'leaf package' always get pkg wildcard
 	    int count = countEntries(PKG, TRUE);
 	    if (count < lowestValue) {
 		lowestValue = count;
 		bestType = PKG;
 		bestImpliedPref = TRUE;
 	    }
 
 	    count = countEntries(PKG, FALSE);
 	    if (count < lowestValue) {
 		lowestValue = count;
 		bestType = PKG;
 		bestImpliedPref = FALSE;
 	    }
 
 	    count = countEntries(NAMESPACE, TRUE);
 	    if (count < lowestValue) {
 		lowestValue = count;
 		bestType = NAMESPACE;
 		bestImpliedPref = TRUE;
 	    }
 
 	    count = countEntries(NAMESPACE, FALSE);
 	    if (count < lowestValue) {
 		lowestValue = count;
 		bestType = NAMESPACE;
 		bestImpliedPref = FALSE;
 	    }
 
 	    type = bestType;
 	    impliedPref = bestImpliedPref;
 	    if (type == NAMESPACE) {
 		entries.add(new PrefData(getFullName() + "/-",
 					 impliedPref.booleanValue()));
 	    }
 	    if (type == PKG) {
 		entries.add(new PrefData(getFullName() + "/*",
 					 impliedPref.booleanValue()));
 	    }
 	    for (Iterator it = nodes.iterator(); it.hasNext(); ) {
 		Graph g = (Graph) it.next();
 		g.addEntries(entries);
 	    }
 	}
 
 	/**
 	 * Count the number of entries which would be created
 	 * by this node for the given node type and preference. The
 	 * <code>type</code> and <code>impliedPref</code> class attributes
 	 * are side-affected by this method.
 	 *
 	 * @param type the node type to assign
 	 * @param pref the node's implied preference value
 	 * @return the number of entries generated by children
 	 */
 	synchronized int countEntries(int type, Boolean pref) {
 	    HashSet test = new HashSet();
 	    this.type = type;
 	    impliedPref = pref;
 	    for (Iterator it = nodes.iterator(); it.hasNext(); ) {
 		Graph g = (Graph) it.next();
 		g.addEntries(test);
 	    }
 	    return test.size();
 	}
     }
 }