compiler-jburg-types/src/main/java/jburg/burg/JBurgGenerator.java

/*
 *
 *  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 jburg.burg;

//  BURM specification is parsed into ANTLR2 AST objects.
import antlr.collections.AST;

//  The code emitter interface definition.
import jburg.burg.emitlangs.EmitLang;

//  The factory that selects and creates an emitter.
import jburg.burg.emitlangs.JBurgEmitterFactory;

//  The i-node adapter interface definition.
import jburg.burg.inode.InodeAdapter;
import jburg.burg.inode.InodeAdapter2;
//  Interface for i-node adapters that need
//  to emit support routines.
import jburg.burg.inode.InodeAuxiliarySupport;

//  The factory that selects and creates an I-node adapter.
import jburg.burg.inode.InodeAdapterFactory;

//  Token types from ANTLR.
import jburg.parser.JBurgTokenTypes;

//  Version file, generated by build.
import jburg.generator.version.JBurgVersion;


import java.io.PrintStream;

import java.lang.reflect.Modifier;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;


@SuppressWarnings("nls")
public class JBurgGenerator implements JBurgTokenTypes
{
    /**
     *  The JBurg specification's rules are categorized as:
     *  <ul>
     *  <li> Pattern  (e.g., integer = PLUS(integer, integer) )
     *  <li> Simple Transformational   (e.g., registerOperand  = integer)
     *  <li> Complex Transformational  (e.g., string = integer { code to convert integer to string} )
     *  </ul>
     *
     *  Simple transformational rules allow a subgoal to satisfy
     *  other subgoals without additional processing; complex
     *  transformational rules allow one subgoal to feed additional
     *  processing that can satisfy other subgoals (at added cost).
     *
     *  Syntactically, a simple transformational rule is distinguished 
	 *  by its lack of a block of code.
	 *  Simple transformational rules are also known as "chain rules"
	 *  in simpler BURGs that don't support complex transformational
	 *  rules.  This longer name was adopted to highlight that difference,
	 *  but a simple transformational rule is, in fact, a chain rule
	 *  by a different name.
     */

	/**
     *   The table of all transformation rules; keyed
     *   by the rules' necessary state, e.g., integer
	 *   in the rule number = integer).
     */
    Map<String, Vector<JBurgRule>> transformationRules = new HashMap<String, Vector<JBurgRule>>();

	/**
	 *  The table of all pattern rules, keyed
	 *  by the top-level operator of the pattern,
	 *  e.g., PLUS in the pattern integer = PLUS(integer, integer).
	 */
    Map<String, Vector<JBurgRule>> patternRules = new HashMap<String, Vector<JBurgRule>>();

    /**
     *  The goal states' names become symbolic constants
     *  in the generated reducer.
     */
    Set<String> allGoalStates = new HashSet<String>();

    /**
     *  Closure sets are organized by their goal state; each state's
     *  closure set contains an entry for every closure
     *  path from any other non-terminal state to the target state.
     */
    Map<String, Vector<ClosureRecord>> closureSets = new HashMap<String, Vector<ClosureRecord>>();

    /**  Action code fragments.  */
    ArrayList<JBurgReduceAction> reduceActions = new ArrayList<JBurgReduceAction>();

    /**
     *  Cost function fragments.
     *  Note that cost functions may also be embedded
     *  in the inline code blocks in a specification.
     */
    ArrayList<AST> costFunctions = new ArrayList<AST>();

    /**  The names of any interfaces that the generated BURM implements.  */
    Vector<String> interfaceNames = new Vector<String>();
    
    /** blocks of code to be added into the class verbatim */
    Vector<String> inclassCode = new Vector<String>();

    /**
     *  Rules that can generate compressed annotations.
     */
    RulesByOperatorAndArity compressedAnnotations = new RulesByOperatorAndArity();

    /** The package name of the generated reducer. */
    String packageName = null;

    /**  Header code, copied as-is into the reducer. */
    String headerBlock = null;

    /**
     *  The name of the i-node class that's being labeled and reduced.
     */
    String iNodeClass = null;

	/** 
	 *  I-node adapter class name.  The adapter is instantiated by name.
	 *  @note: specified as an alternative to the I-node class' name,
	 *  which selects a builtin adapter.
	 */
	String iNodeAdapterClass;

    /**
     *  The return types for specific states.
     */
    Map<String, String> returnTypeTable = new HashMap<String, String>();

    /**
     *  The default return type of the reducer functions.
     *  If this is defaulted to null, the generated reducer will return nodes of the iNodeClass.
     */
    String defaultReturnType = null;

    /**
     *  Table of properties to be added to the BURM.
     *  Each one is a name/type pair; the BURM gets
     *  a private member and get/set methods.
     */
    Map<String, String> burmProperties = new HashMap<String, String>();

    /**
     *  Simple transformations simply delegate to their antecedent reduction,
     *  so all transformations to a given nonterminal state can share the
     *  same rule.
     */
    Map<String, JBurgRule> simpleTransformationRules = new HashMap<String,JBurgRule>();

    /**  Include debugging code in the generated reducer?  */
    boolean debugMode;
    
    /** 
     * If the pattern-matcher generator fails, dump its annotation tree here.
     * Note: this is only enabled (or useful) when debugging JBurg's own BURM. 
     */
    String patternMatcherDumpFile = null;

    /**  
     *  Caller's logging interface.  If defaulted to null, informational and
     *  error messages go to System.out and System.err respectively.
     */
    Logger logger = null;
    
    /**
     * Name for the language to emit code in (default is assumed to be java (=emitlang.EmitJava)
     */
    String emitLanguageName = null;
    
    /** Code emitter to use (selected using the language name) */
	EmitLang codeEmitter = null;

	/** I-node adapter to use */
	InodeAdapter iNodeAdapter;
	
	/** 
	 *  If the InodeAdapter is also an InodeAdapter2,
	 *  keep a reference to it. 
	 */
	InodeAdapter2 adapter2;

	/**  Cumulative error count. */
	int errCount = 0;

	/**  Name of the initial parameter to the label routine. */
	private static String initalParamName = "to_be_labelled";
	
	/** Name of the node in the reducer */
	private String reducerNodeName = "__p";
	
	/** Name of the stack of reduced values */
	private String reducedValuesName = "__reducedValues";

    /**  Default error handler.  null means use hard-coded default, i.e., throw an exception. */
    String defaultErrorHandler = null;

    /**  Prologue snippets mapped to the corresponding rule number. */
    Map<Integer,String> prologueBlocks = new TreeMap<Integer,String>();

    /** 
     *  All operators known to any pattern accumulate in this set
     *  so that the BURG can generate operator-specific getNthChild()
     *  routines.
     */
    Set<String> allOperators = new TreeSet<String>();
    
    /**
     * operator mapped to node type. This map is populated by JBurg.NodeType
     * directives.
     * <p>
     * For example, an operator named IdentifierID would be associated with
     * {@code IIdentifierNode*} in this map if the input contained
     * {@code JBurg.NodeType IdentifierID = IIdentifierNode*;
     */
    final Map<String, String> opcodeNodeTypes = new HashMap<String, String>();
    
    /**
     *  The type of the INodes' opcode.  Defaults to int but
     *  can be an enum for maintainability.
     */
    String opcodeType = "int";

    /**
     *  Manifest constants in the JBurg specification.
     */
    Map<String,Integer> manifestConstants = new HashMap<String,Integer>();
    
    /**
     *  Patterns that have been optimized out are represented
     *  by this not-likely-to-compile sequence.
     */
    final private static String nilPattern = "-null-";

    /**
     *  Manifest constant for method declarations.
     */
    final private static Class<?>[] throwsNothing = null;

    /**
     *  Manifest constant for method declarations.
     */
    final private static Class<?>[] throwsException = new Class<?>[] { Exception.class };


    /**
     *  Manifest constant for method declarations.
     */
    final private static String[][] noFormalParameters = new String[][] { };

    /**
     *  Manifest constant for method calls.
     */
    final private static String[] noActualParameters = { };

    /**
     *  Manifest constant for an unfeasible rule.
     */
    final private static String NO_FEASIBLE_RULE = "-1";

    /**
     *  Manifest constant for an uninitialized cost.
     */
    final private static String UNINITIALIZED = "-1";

    /**
     *  NamedPattern holds a named pattern, and keeps a table of the reductions that refer to it.
     *  (See defect 3063143 for problems with multiple reductions sharing a pattern.)
     */
    class NamedPattern
    {
        String patternName;
        AST pattern = null;
        Vector<AST> reductions = new Vector<AST>();

        NamedPattern(String name)
        {
            this.patternName = name;
        }
    }

    /**
     *  A PatternMap keeps the map of pattern names to reductions.
     */
    @SuppressWarnings("serial")
    class PatternMap extends  TreeMap<String,NamedPattern>
    {
        NamedPattern getPattern(String key)
        {
            if ( !super.containsKey(key) )
                put(key, new NamedPattern(key));
            return super.get(key);
        }

        void addPattern(String key, AST pattern)
        {
            NamedPattern p = getPattern(key);
            p.pattern = pattern;
        }

        void addReduction(String key, AST reduction)
        {
            NamedPattern p = getPattern(key);
            p.reductions.add(reduction);
        }
    }

    PatternMap namedPatterns = new  PatternMap();

    /**
     *  Aggregate path computations if more than this threshold
     *  number of pattern elements share a path.
     */
    private int aggregatePathThreshold = Integer.MAX_VALUE;

    public void setAggregatePathThreshold(int threshold)
    {
        this.aggregatePathThreshold = threshold;
    }

    /**
      *  @param root - the root of the AST generated by parsing the .jburg specification.
      */
    public JBurgGenerator(AST root, Logger log) throws Exception
    {
        this.logger = log;

        //  Walk over the children of the root, each of which 
		//  is a self-contained syntactical construct, and
        //  find an appropriate action for each.
        for (AST currentNode = root; currentNode != null;
                currentNode = currentNode.getNextSibling()) 
		{
            switch (currentNode.getType()) 
			{
            case COST_FUNCTION:
                this.costFunctions.add(currentNode);
                break;

            case HEADER_DECLARATION:

				if ( null == this.headerBlock )
				{
					this.headerBlock = getCodeBlock(currentNode);
				}
				else
				{
                    throw new IllegalArgumentException("The class header may only be specified once.");
				}

                break;
                
            case INCLASS_DECLARATION:
				{
            		this.inclassCode.add( stripBrackets(getCodeBlock(currentNode)) );
            	}
				
				break;

            case INODE_ADAPTER_DECLARATION:

                if (this.iNodeAdapterClass == null)
				{
					this.iNodeAdapterClass = getIdentifierText(currentNode.getFirstChild());
				}
				else
				{
                    throw new IllegalArgumentException("INodeAdapter may only be specified once.");
				}

				break;

            case INODE_TYPE_DECLARATION:

                if (this.iNodeClass == null)
				{
                    this.iNodeClass = getIdentifierText(currentNode.getFirstChild());
				}
                else
				{
                    throw new IllegalArgumentException("INodeType may only be specified once.");
				}

                break;
                
            case LANGUAGE_DECLARATION:

            	if ( null == this.emitLanguageName )
				{
            		this.emitLanguageName = currentNode.getFirstChild().getText();
				}
            	else
				{
            		throw new IllegalArgumentException("Language may only be specified once.");
				}

            	break;

            case IMPLEMENTS_INTERFACE_SPECIFICATION:
                this.interfaceNames.addElement(getIdentifierText( currentNode.getFirstChild()) );

                break;

            case PACKAGE_SPECIFICATION:
                if ( null == this.packageName )
				{
					this.packageName = getIdentifierText(currentNode.getFirstChild());
				}
				else
				{
            		throw new IllegalArgumentException("package may only be specified once.");
				}

                break;

            case PROPERTY_SPECIFICATION: 
				{
					String propertyType = getIdentifierText(currentNode.getFirstChild());
					String propertyName = currentNode.getFirstChild().getNextSibling().getText();
					this.burmProperties.put(propertyName, propertyType);
				}

                break;

            case RETURN_DECLARATION:

                if (this.defaultReturnType == null)
                    this.defaultReturnType = getIdentifierText(currentNode.getFirstChild());
                else
                    throw new IllegalArgumentException( "ReturnType may only be specified once.");

                break;

            case PATTERN_RULE:
                addPatternRule(currentNode);

                break;

            case SIMPLE_TRANSFORMATION_RULE:
                addSimpleTransformationRule(currentNode);

                break;

            case TRANSFORMATION_RULE:
                addComplexTransformationRule(currentNode);

                break;

            case TYPED_RETURN_DECLARATION:

                {
                    String stateName = currentNode.getFirstChild().getText();
                    String returnType = getIdentifierText(currentNode.getFirstChild()
                            .getNextSibling());

                    //  Put the return declaration in the table, but only once per state.
                    Object typeCollision = this.returnTypeTable.put(stateName, returnType);
                    if ( null != typeCollision )
                    {
                        throw new IllegalArgumentException(
                            "A state may only specify one ReturnType."
                        );
                    }
                }

                break;

            case PATTERN_DECLARATION:
                {
                    String pattern_name = currentNode.getFirstChild().getText();
                    namedPatterns.addPattern(pattern_name, currentNode);
                }
                break;

            case REDUCTION_DECLARATION:
                {
                    String pattern_name = currentNode.getFirstChild().getNextSibling().getText();
                    namedPatterns.addReduction(pattern_name, currentNode);
                }
                break;

            case DEFAULT_ERROR_HANDLER:
                this.defaultErrorHandler = getCodeBlock(currentNode);
                break;
            case NODE_TYPE:
            {
                final String operatorID = currentNode.getFirstChild().getText();
                assert !operatorID.isEmpty() : "Parser should never create empty operator!";
                final String nodeType = currentNode.getFirstChild().getNextSibling().getText();               
                assert !nodeType.isEmpty() : "Parser should never create empty node type!";
                
                if (this.opcodeNodeTypes.put(operatorID, nodeType) != null)
                {
                    final String message = "Duplicate node type declaration for '"
                        + operatorID
                        + "'.";
                    throw new IllegalArgumentException(message);
                }
                break;
            }
            case OPCODE_TYPE:
                this.opcodeType = currentNode.getFirstChild().getText();
                break;

            case MANIFEST_CONSTANT:
                manifestConstants.put(currentNode.getFirstChild().getText(), Integer.parseInt(currentNode.getFirstChild().getNextSibling().getText()));
                break;

            default:
                throw new IllegalArgumentException("Unknown specification AST type " +
            											String.valueOf(currentNode.getType()));
            }
        }

        //  Set the language emitter.
        codeEmitter = JBurgEmitterFactory.getEmitter(emitLanguageName, getLogger());

        if ( codeEmitter == null )
		{
			throw new IllegalStateException("Unknown language specified: \""+ emitLanguageName +"\"");
        }

		if ( iNodeClass != null )
		{
			if ( iNodeAdapterClass != null )
			{
				try
				{
					this.iNodeAdapter = (InodeAdapter)Class.forName(iNodeAdapterClass).newInstance();
				}
				catch ( Exception ex )
				{
					ex.printStackTrace();
					throw new IllegalArgumentException ("Unable to instantiate i-node adapter " + iNodeAdapterClass );
				}
			}
			else
			{
				this.iNodeAdapter = InodeAdapterFactory.getAdapter(iNodeClass);
			}
			
			codeEmitter.setINodeType(this.iNodeClass);

			if ( this.iNodeAdapter != null )
			{
				logger.info("Using i-node adapter " + this.iNodeAdapter.getClass().getName() );
			}
			else
			{
				getLogger().warning("using default i-node adapter, no adapter matches " + iNodeClass );
				this.iNodeAdapter = new jburg.burg.inode.DefaultAdapter();
			}
			
			//  See if the adapter is also an InodeAdapter2 implementation.
			this.adapter2 = (this.iNodeAdapter instanceof InodeAdapter2)? (InodeAdapter2)this.iNodeAdapter : null;
		}
		else
		{
			throw new IllegalStateException("You must specify the i-node type.");
		}

		codeEmitter.setInodeAdapter(this.iNodeAdapter);

        //  Default return type is the same as the INode class.
        if (this.defaultReturnType == null)
		{
            this.defaultReturnType = this.iNodeClass;
		}

        //  Mutate pattern/reduction decl pairs into pattern rules.
        for ( NamedPattern np: namedPatterns.values() )
        {
            if ( np.pattern != null && np.reductions.size() > 0 )
            {
                AST named_pattern = np.pattern.getFirstChild().getNextSibling().getFirstChild();

                for ( AST reduction: np.reductions )
                {    
                    //  Splice the pattern into the reduction AST.
                
                    AST nt_state = reduction.getFirstChild();
                    AST pattern_name = nt_state.getNextSibling();
                    AST cost_decl = pattern_name.getNextSibling();
                    
                    //  Create a new holder for the pattern
                    //  so the original AST isn't mutated.
                    AST pattern_holder = new antlr.CommonAST();
                    pattern_holder.setFirstChild(named_pattern);
                    nt_state.setNextSibling(pattern_holder);
                    pattern_holder.setNextSibling(cost_decl);
    
                    //  Give the composite AST the appropriate type
                    //  for its pattern.
                    reduction.setType(PATTERN_RULE);
    
                    addPatternRule(reduction);
                }
            }
            else if ( np.pattern != null )
            {
                getLogger().warning("pattern " + np.patternName + " has no reduction - ignored.");
            }
            else if ( np.reductions.size() > 0 )
            {
                throw new IllegalStateException("Reduction " + np.patternName + " has no associated pattern.");
            }
        }

        //  Add target-specific logic to the simple transformations' rules.
        for ( JBurgRule rule: this.simpleTransformationRules.values() )
        {
            String actionCode = String.format(
                "%s%s",
                codeEmitter.genReturnValue(
                    codeEmitter.genPopFromStack(reducedValuesName, getReturnType(rule.getGoalState()))
                ),
                codeEmitter.genEndStmt()
            );

            JBurgReduceAction action = addAction(actionCode, rule.getGoalState());
            action.setAntecedentState(rule.getAntecedentState());
            rule.setReduceAction(action);
        }

        //  Compute the closure sets.
        computeClosureSets();
    }
    
    /**
     *  Add a reduce action to the action list.
	 *  Actions are keyed by number in the generated BURM.
     */
    private JBurgReduceAction addAction(String strAction, String strState)
    {
        JBurgReduceAction newAction = new JBurgReduceAction(strAction);
        this.reduceActions.add(newAction);

        //  The first index is used as the default action for
        //  simple transformation rules.
        newAction.setIndex(this.reduceActions.size());
        newAction.setState(strState);

        return newAction;
    }

    /**
     *  Sort through a rule's action routine specifications and assemble
     *  a JBurgReduceAction from them.
     *  @param parent - the rule's AST.
     *  @param goal_state - the state the rule produces.
     *  
     */
    private JBurgReduceAction decodeReduction(AST parent, String goal_state)
    {
        JBurgReduceAction action = null;
        AST reduction = null;

        if ( hasASTOfType(parent, REDUCTION_ACTION) )
        {
            reduction = getASTByType(parent, REDUCTION_ACTION);
            action = addAction(getCodeBlock(reduction), goal_state);
        }
        else if ( hasASTOfType(parent, EXPLICIT_REDUCTION ) )
        {
            reduction = getASTByType(parent, EXPLICIT_REDUCTION);
            action = addAction( "return " + decodeProcedureCall(reduction) + ";", goal_state );
        }
        else
        {
            throw new IllegalStateException("A reduction must specify an implementation block or callback function");
        }

        if ( hasASTOfType(reduction, PROLOGUE) )
        {
            AST prologue = getASTByType(reduction, PROLOGUE);
            String prologue_action = null;

            if ( hasASTOfType(prologue, BLOCK) )
            {
                prologue_action = getCodeBlock(prologue);
            }
            else if ( hasASTOfType(prologue, PROCEDURE_CALL) )
            {
                prologue_action = "\t" + decodeProcedureCall(prologue) + ";";
            }
            else
            {
                throw new IllegalStateException("Prologue block with no inline code or callback");
            }

            this.prologueBlocks.put(action.index, prologue_action);
        }

        return action;
    }

    private String decodeProcedureCall(AST parent)
    {
        AST procall = getASTByType(parent, PROCEDURE_CALL);

        StringBuilder buffer = new StringBuilder();

        AST id = procall.getFirstChild();
        buffer.append(id.getText());
        buffer.append("(");

        AST param = id.getNextSibling();
        if ( param != null )
        {
            buffer.append(param.getText());

            for ( param = param.getNextSibling(); param != null; param = param.getNextSibling() )
            {
                buffer.append(",");
                buffer.append(param.getText());
            }
        }
        buffer.append(")");

        return buffer.toString();
    }

    /**
     *  Add a complex transformation rule to its table,
     *  and record the rule's reduction action.
     */
    private void addComplexTransformationRule(AST transform)
        throws Exception
    {
        JBurgRule n = addNamedRule(this.transformationRules, transform);

        //  Prepare the rule's reduce action.
        JBurgReduceAction action = decodeReduction(transform, n.getGoalState());
        action.setAntecedentState(n.getAntecedentState());

        //  Add the antecedent state by name as an alias action routine "parameter."
        //  The "parameter" is popped off the reduced values stack into a local variable.
        action.addParameter(
            n.getAntecedentState(), 
            n.getAntecedentState(), 
            ParameterDescriptor.ArityType.Fixed
        );

        n.setReduceAction(action);
    }

    /**
     *  If this simple transformation is not yet known, add it to its rule table.
     */
    private void addSimpleTransformationRule(AST transform)
    {
        JBurgRule newRule = new JBurgRule(transform);

        String key = String.format("%s=%s", newRule.getGoalState(), newRule.getAntecedentState());

        if ( ! this.simpleTransformationRules.containsKey(key) )
        {
            //  Ensure this rule's nonterminal is known.
            this.allGoalStates.add(newRule.getGoalState());
            addNamedRule(this.transformationRules, newRule);

            //  Target-specific action logic will be
            //  added once the code emitter is up.
            this.simpleTransformationRules.put(key, newRule);
        }
    }

    /**
     *  Wrap a pattern rule in an I-node, and add it to pattern rule table.
     */
    private void addPatternRule(AST newRule) throws Exception
    {
        JBurgRule n = addNamedRule(this.patternRules, newRule);

        JBurgReduceAction newAction = decodeReduction(newRule, n.getGoalState());

        n.setReduceAction(newAction);
    }

    /**
     *  Wrap a rule in an I-node, and add it to the list of rules
     *  that produce a particular subgoal.
     */
    private JBurgRule addNamedRule(Map<String, Vector<JBurgRule>> ruleTable, AST newAST)
    {
        JBurgRule newRule = new JBurgRule(newAST);

        //  Ensure this rule's nonterminal is known.
        this.allGoalStates.add( newRule.getGoalState() );
        return addNamedRule(ruleTable, newRule);
    }

    /**
     *  Add a rule to its rule table.
     *  @param ruleTable - the appropriate table for this type of rule.  Keyed by operator.
     *  @param newRule - the rule to add.
     */
    private JBurgRule addNamedRule(Map<String, Vector<JBurgRule>> ruleTable, JBurgRule newRule)
    {
        //  Store the rule by operator.
        String operator = newRule.getOperator();

        Vector<JBurgRule> vRules = ruleTable.get(operator);

        if (vRules == null)
        {
            vRules = new Vector<JBurgRule>();
            ruleTable.put(operator, vRules);
        }

        vRules.add(newRule);

        return newRule;
    }

    /**
     *  Compute the closure set of a rule:  the set of rules that
     *  that can transform this rule's goal to satsify another goal.
	 *  @note computeClosure is public so that it can be applied
	 *    by JBurgUtilities.
     */
    public void computeClosure(JBurgRule n) throws Exception
    {
		//  Get the list of transformation rules that can use this rule's goal state.
        Vector<JBurgRule> vClosureCandidate = this.transformationRules.get(n.getGoalState());

        if (vClosureCandidate != null) 
		{
            //  Found some closures:
            //  create or fetch this target state's closure set.
            Vector<ClosureRecord> vClosureSet = this.closureSets.get(n.getGoalState());

            if (vClosureSet == null) 
			{
                vClosureSet = new Vector<ClosureRecord>();
                this.closureSets.put(n.getGoalState(), vClosureSet);
            }

            for (JBurgRule nPrime:vClosureCandidate ) 
			{

                //  Add this closure to the closure set.
                ClosureRecord newClosure = new ClosureRecord(nPrime);

                if (!vClosureSet.contains(newClosure)) 
				{
                    vClosureSet.add(newClosure);
                }
            }
        }
    }

    /**
     *  Scan all the rules and compute their closure sets.
     */
    private void computeClosureSets() throws Exception
    {
        for (Vector<JBurgRule> patterns : this.patternRules.values() ) 
		{
            try 
			{
                JBurgUtilities.applyToAll( this, patterns, "computeClosure", JBurgRule.class);
            }
			catch (Exception e)
			{
                e.printStackTrace();
            }
        }

        for (Vector<JBurgRule> transformations : this.transformationRules.values() )
		{
            try
			{
                JBurgUtilities.applyToAll( this, transformations, "computeClosure", JBurgRule.class);
            }
			catch (Exception e)
			{
                e.printStackTrace();
            }
        }
    }

    /**
     *  Emit the BURG specification's resultant BURM to an output stream.
     */
    public int generate(String className, PrintStream output)
    {
        try
		{
            codeEmitter.setOpcodeType(this.opcodeType);
        	emitHeader(className, output);
        	codeEmitter.emitInclass(iNodeClass, this.inclassCode, output);

        	emitNTConstants(this.allGoalStates, output);
            emitStatics(output);

			if ( this.iNodeAdapter instanceof InodeAuxiliarySupport )
			{
				((InodeAuxiliarySupport)this.iNodeAdapter).emitAuxiliarySupport(codeEmitter, output);
			}

            emitLabelFunction(this.iNodeClass, output);
            ruleSemanticAnalysis();

            if  ( codeEmitter.supportsSpecializedAnnotations() )
            {
                for (Vector<JBurgRule> vPatternRules: this.patternRules.values())
                    this.compressedAnnotations.addAll(vPatternRules);
            }
            else
            {
                emitComputeCostMatrixFunction(this.iNodeClass, output);
                emitClosures(this.closureSets, this.iNodeClass, output);
            }
            emitActions(this.reduceActions, this.iNodeClass, output);
            emitCostFunctions(this.costFunctions, this.iNodeClass, output);

            if ( codeEmitter.supportsSpecializedAnnotations() )
                emitCompressedAnnotations(output);
            
            //  If there's an InodeAdapter2 present,
            //  emit the getNthChild routine that
            //  implements the adapter's node-handling logic.
            if ( this.adapter2 != null)
                emitGetNthChild(output);

            codeEmitter.emitTrailer(
				className,
				this.iNodeClass,
				this.allGoalStates,
				this.burmProperties,
				this.debugMode,
                this.defaultErrorHandler,
                this.prologueBlocks,
				output
			);
        }
		catch (Exception e)
		{
            e.printStackTrace();
			this.errCount++;
        }

		return this.errCount;
    }

    //  Emit static lookup tables.
    private void emitStatics(PrintStream output)
    {
        //  Emit the static table of subgoal records.
        Map<Integer, Vector<JBurgPatternMatcher>> rules_by_action = new HashMap<Integer,Vector<JBurgPatternMatcher>>();
        int max_action = 0;
        for (Vector<JBurgRule> vPatternRules: patternRules.values())
        {
            for (JBurgRule p: vPatternRules)
            {
                int action_number = p.getReduceAction().getIndex();
                max_action = Math.max(max_action, action_number);
                
                if ( p.patternMatcher.isNary() )
                {
                    rules_by_action.put(action_number,new Vector<JBurgPatternMatcher>());
                    rules_by_action.get(action_number).add(p.patternMatcher);
                }
                else if (!p.patternMatcher.getParameterizedSubtrees().isEmpty() )

                {
                    rules_by_action.put(action_number,p.patternMatcher.getParameterizedSubtrees());
                }
            }
        }

        //  Ensure the transformation rules' actions have subgoal records.
        for ( Vector<JBurgRule> transformations:  this.transformationRules.values() )
            for ( JBurgRule t: transformations )
                max_action = Math.max(max_action, t.getReduceAction().getIndex());
        
        codeEmitter.emitStatics(max_action, rules_by_action, output);

        //  Generate manifest constant declarations.
        for ( Map.Entry<String,Integer> constants : this.manifestConstants.entrySet() )
            genInstanceField(
                output,
                Modifier.PUBLIC + Modifier.STATIC + Modifier.FINAL,
                "int",
                constants.getKey(),
                constants.getValue().toString()
            );
    }

    /**
     *  Get the payload of an identifier, with error checking.
     *  @return the identifier's text.
     */
    private String getIdentifierText(AST p)
    {
		if ( p.getType() != IDENTIFIER )
		{
			throw new IllegalStateException ( "Expected IDENTIFIER, found " + p.toStringTree() );
		}

        return p.getText();
    }

    /**
     *  Does this production have a closure set?
     *  @return true if n has a closure set.
     *  @param n - the production of interest.
     */
    public boolean hasClosure(JBurgProduction n)
    {
        return this.closureSets.get(n.getGoalState()) != null;
    }

    /**
      *  Emit the file/class header information.
      */
    private void emitHeader(String className, PrintStream output)
    {
        genComment(output, " Generated " + new java.util.Date().toString() + " by JBurg version " + JBurgVersion.version  );
        output.println();
        
        codeEmitter.emitHeader(className, this.packageName, this.headerBlock, this.interfaceNames, this.debugMode, output);
    }

	/**
	 *  @return the return type for a specific state.
	 */
	public String getReturnType(String stateName)
	{
		Object result = returnTypeTable.get(stateName);

		if (result == null)
			result = defaultReturnType;

		return result.toString();
	}
	
    /**
     *  setDebugMode controls the level of debugging code that will be generated in the reducer.
     */
    public void setDebugMode(boolean bDebugMode)
    {
        debugMode = bDebugMode;
    }
    
	/**
	 *  @return the text of the parent AST's code block, which is represented as a BLOCK token.
	 */
	private String getCodeBlock( AST parent )
	{
		return getASTByType(parent, BLOCK).getText();
	}

    /**
     *  @return the first child of the parent AST with the specified node type.
     */
    private AST getASTByType(AST parent, int node_type)
    {
        for ( AST current = parent.getFirstChild(); current != null; current = current.getNextSibling() )
        {
            if ( current.getType() == node_type )
                return current;
        }

        throw new IllegalStateException ( "AST " + parent.toString() + " has no child of node type " + node_type + "." );
    }

    private boolean hasASTOfType(AST parent, int node_type)
    {
        for ( AST current = parent.getFirstChild(); current != null; current = current.getNextSibling() )
        {
            if ( current.getType() == node_type )
                return true;
        }

        return false;
    }

    /**
     *  A JBurgProduction is a view of a pattern-matching rule (JBurgRule) 
     *  or a nonterminal transformation rule (ClosureRecord) that exposes
     *  characteristics important in their static analysis.
     */
    public interface JBurgProduction
    {
        /**
         *  @return the nonterminal this production produces.
         */
        public String getGoalState();

        /**
         *  @return the code snippet that computes
         *    or retrieves this production's 
         *    (potentially) cached code.
         */
        public String getCachedCost();

        /**
         *  @return this production's reduce action.
         */
        public JBurgReduceAction getReduceAction();

        /**
         *  Is this production's cost constant in the
         *  context where it's to be invoked?
         *  @param productions - the set of productions at the
         *    point where this productions's cost is required.
         */
        public boolean computesConstantCost(Multimap<String, JBurgProduction> productions);

        /**
         *  Get the constant cost of a production.
         *  @param productions - the set of productions at the
         *    point where this production's cost is required.
         *  @return the cost, with overflow-safe addition.
         *  @pre computesConstantCost(productions) must be true.
         */
        public int getConstantCost(Multimap<String, JBurgProduction> productions);
    }

    /**
     *  JBurgRule contains an AST that represents a rule, 
     *  its associated JBurgReduceAction,
     *  and accessors to the AST's components.
     */
    public class JBurgRule implements JBurgProduction
    {
        /**
         *  The parsed rule.
         */
        AST m_AST;
        
        /**
         *  If the rule is a pattern rule, its pattern matcher.
         */
        JBurgPatternMatcher patternMatcher = null;
        
        /**
         * The rule's reduction action.
         */
        JBurgReduceAction reduceAction;

        /**
         *   The pattern as a String; precomputed so it can be used as a key
         *   to group labeling choices by common patterns.
         */
        private String encodedPattern;

        public JBurgRule(AST n)
        {
            m_AST = n;
            
            if ( m_AST.getType() == PATTERN_RULE )
            {
                AST pattern_root = m_AST.getFirstChild().getNextSibling().getFirstChild();
                try
                {
                    this.patternMatcher = generateMatcher(pattern_root); 
                }
                catch ( Exception ex )
                {
                    logger.exception("Building pattern recognizer for " + m_AST.toStringTree(), ex);
                }
            }
        }

        String getEncodedPattern()
        {
            if ( this.encodedPattern == null )
            {
                this.encodedPattern = 
                    patternMatcher.generatePatternRecognizer(
                        codeEmitter,
                        "node",
                        JBurgGenerator.this.adapter2
                    );
            }
            
            if ( this.encodedPattern == null )
                this.encodedPattern = nilPattern;

            return this.encodedPattern;
        }

        /**
         * @param baseNode - the path to the base of the subtree.
         * @return the subtree's cost specification.
         */
        public String getCost(String baseNode)
        {
            if ( m_AST.getType() != SIMPLE_TRANSFORMATION_RULE )
            {
                AST cost_spec = m_AST.getFirstChild().getNextSibling()
                        .getNextSibling();

                String costText = cost_spec.getFirstChild().getText();

                if ( hasCostFunction() )
                    return genCallMethod(null, costText, baseNode);
                else
                    return costText;
            }
            else
            {
                // Simple transformation rules don't cost anything.
                return "0";
            }
        }
        
        /** 
         *  @return true if the rule has a constant cost.
         */
        public boolean hasConstantCost()
        {
            if ( m_AST.getType() != SIMPLE_TRANSFORMATION_RULE )
            {
                AST cost_spec = m_AST.getFirstChild().getNextSibling()
                        .getNextSibling();

                String costText = cost_spec.getFirstChild().getText();

                boolean ownCostConstant =
                    cost_spec.getType() == LITERAL_COST_SPEC ||
                    JBurgGenerator.this.manifestConstants.containsKey(costText);
                
                return ownCostConstant &&
                     (this.isTerminalPattern() || this.patternMatcher == null);
            }
            else
            {
                // Simple transformation rules all cost 0.
                return true;
            }
        }
        
        /**
         *  @return the rule's cost.
         *  @throws IllegalStateException if the cost isn't constant.
         */
        public Integer getConstantCost()
        {
            if ( m_AST.getType() != SIMPLE_TRANSFORMATION_RULE )
            {
                AST cost_spec = m_AST.getFirstChild().getNextSibling()
                        .getNextSibling();

                String costText = cost_spec.getFirstChild().getText();

                if ( cost_spec.getType() == LITERAL_COST_SPEC )
                {
                    return new Integer(costText);
                }
                else if ( JBurgGenerator.this.manifestConstants.containsKey(costText) )
                {
                    return JBurgGenerator.this.manifestConstants.get(costText);
                }
                else
                {
                    throw new IllegalStateException("non constant cost: " + costText);
                }
            }
            else
            {
                // Simple transformation rules don't cost anything.
                return 0;
            }
        }

        /**
         *  @return true if the cost specification is a function call.
         */
        public boolean hasCostFunction()
        {
            boolean result = false;

            if ( m_AST.getType() != SIMPLE_TRANSFORMATION_RULE )
                result = m_AST.getFirstChild().getNextSibling().getNextSibling().getType() == FUNCTION_CALL;

            return result;
        }

        /**
         *  @return the rule's cached cost.
         */
        @Override
        public String getCachedCost()
        {
            if ( this.hasCostFunction() )
                return String.format("cachedCost_%h()", getCost(reducerNodeName));
            else
                return getCost(reducerNodeName);

        }

        /**
         *  @return the rule's reduction action.
         */
        @Override
        public JBurgReduceAction getReduceAction()
        {
			if ( null == this.reduceAction )
			{
				throw new IllegalStateException( "getReduceAction() has no action to return." );
			}

            return this.reduceAction;
        }

        /**
         *  @return the antecedent state of a nonterminal-to-nonterminal
         *    reduction, i.e., the state that the subtree must be reduced
         *    to before this reduction can run.
         */
        public String getAntecedentState()
        {
             if ( m_AST.getType() == SIMPLE_TRANSFORMATION_RULE )
             {
                 return m_AST.getFirstChild().getNextSibling().getText();
             }
             else if ( m_AST.getType() == TRANSFORMATION_RULE )
             {
                 return m_AST.getFirstChild().getNextSibling().getText();
             }
             else
                 throw new IllegalStateException(String.format("no antecedent for %s", m_AST.getType()));
        }

        /**
         *  @return the node ID of the node at the root of the subtree.
         */
        public String getOperator()
        {
			int type = m_AST.getType();

			if ( PATTERN_RULE == type )
			{
				return m_AST.getFirstChild().getNextSibling().getFirstChild().getFirstChild().getText();
			}
			else
			{
			    //  A transformation rule.
				return m_AST.getFirstChild().getNextSibling().getText();
			}
        }

        /**
         *  @return the nonterminal produced by this reduction.
         */
        @Override
        public String getGoalState()
        {
            return m_AST.getFirstChild().getText();
        }

        /**
         *  Set this rule's associated action code.
         */
        public void setReduceAction(JBurgReduceAction reduceAction)
        {
            this.reduceAction = reduceAction;
        }

        /**
         *  @return true if this node has no children (a "leaf" node).
         */
        public boolean isTerminalPattern()
        {
            return this.isFixedArity() && this.patternMatcher.getNominalArity() == 0;
        }

        /**
         *  @return true if this rule's pattern has a fixed number of "operand" subtrees.
         */
        public boolean isFixedArity()
        {
            return this.patternMatcher != null && !this.patternMatcher.hasNaryTail();
        }

        /**
         *  @return true if this rule needs an out-of-line method to check its cost.
         */
        public boolean needsCostFunction()
        {
            if ( this.isTerminalPattern() )
                return false;
            else if ( this.patternMatcher.hasNaryTail() )
                return  this.patternMatcher.getNominalArity() != this.patternMatcher.getMinimumNaryChildCount();
            else
                return true;
        }

        /**
         *  Is this production's cost constant in the
         *  context where it's to be invoked?
         *  @param productions - the set of productions at the
         *    point where this productions's cost is required.
         */
        @Override
        public boolean computesConstantCost(Multimap<String, JBurgProduction> productions)
        {
            return hasConstantCost();
        }

        /**
         *  Get the constant cost of a production.
         *  @param productions - the set of productions at the
         *    point where this production's cost is required.
         *  @return the cost, with overflow-safe addition.
         *  @pre computesConstantCost(productions) must be true.
         */
        @Override
        public int getConstantCost(Multimap<String, JBurgProduction> productions)
        {
            return getConstantCost();
        }

        @Override
        public String toString()
        {
            return m_AST.toStringTree();
        }
    }

    /**
     *  JBurgReduceAction holds action code fragments and their associated "parameters."
     *  A rule specifies "parameters" by naming individual subgoal states within a pattern
     *  rule specifiction, for example,
     *  <xmp>integer = PLUS ( integer i1, integer i2 )</xmp>
     *  In this example, i1 and i2 are the action routine's "parameters."  Since the action
     *  routines all share a common signature, the parameters are passed via the reducer's
     *  reduced values stack.
     */
    private class JBurgReduceAction
    {
        /** The routine's source, from the input specification. */
        private String actionCode;
        
        /**
         * The non-terminal state produced by this action, e.g., expression from
         * <xmp>expression = ADD(expression l, expression r)</xmp>
         */
        private String m_state;

        /**
         *  The antecedent reduction of a nonterminal-to-nonterminal rule.
         */
        private String antecedentState;
        
        /**
         *  The operator ID of a pattern rule; used to find content-handling
         *  code from the InodeAdapter2.
         */
        private String m_operator;
        
        /**
         * Names and types of the routine's parameters.
         * Types are given as their non-terminal state names; toString()
         * translates these BURM-centric types into the corresponding
         * types in the target language using the mapping set up by
         * the ReturnType directives in the input specification.
         */
        private Vector<ParameterDescriptor> m_parameterList = new Vector<ParameterDescriptor>();

        /**
         *  This action routine's index, assigned in entry order.
         *  The action routines are enumerated as action_1(JBurgNode p), action_2(JBurgNode p),
         *  etc. in the generated reducer.
         */
        int index;
        
        /**
         * Track name-to-subtree mappings to be emitted.
         */
        class NamedSubtree
        {
            String path;
            String name;
            
            NamedSubtree(String path, String name)
            {
                this.path = path;
                this.name = name;
            }
        }
        /**
         *  Saved name-to-subtree mappings.
         */
        Vector<NamedSubtree> namedChildNodes = new Vector<NamedSubtree>();
        
        /**
         * Construct a reduce action.
         * @param strActionCode - the action's implementation
         * code, in a target-specific language 
         */
        public JBurgReduceAction(String strActionCode)
        {
            this.actionCode = strActionCode;
        }

        /**
         * Add a parameter to the action's parameter list.
         */
        public void addParameter(String parmName, String parmState, ParameterDescriptor.ArityType arityType)
            throws Exception
        {
            m_parameterList.add(new ParameterDescriptor(parmName, parmState, arityType));
        }

        /**
         *  Return this action's index (the N constituent of its generated name, action_N).
         */
        public int getIndex()
        {
            return this.index;
        }

        /**
         *  Set this action's index (the N constituent of its generated name, action_N).
         */
        public void setIndex(int index)
        {
            this.index = index;
        }

        /**
         * Set the non-terminal state this reduction derives.
         * @param state - the non-terminal state, e.g., expression from
         * <xmp>expression = ADD(expression l, expression r)</xmp>
         */
        public void setState(String state)
        {
            this.m_state = state;
        }

        /**
         * @return the non-terminal state this reduction derives.
         */
        public String getState()
        {
            return this.m_state;
        }

        /**
         *  @param operator the operator at the root of 
         *    the matched subtree.
         */
        public void setOperator(String operator)
        {
            this.m_operator = operator;
        }

        /**
         * @return the operator at the root of 
         *    the matched subtree.
         */
        public String getOperator()
        {
            return m_operator;
        }

        /**
         *  Return the reduction action's code, 
         *  with prepended logic to pop its parameters off the stack.
         */
        @Override
        public String toString()
        {
            String result = "";

            for ( ParameterDescriptor next_param: m_parameterList )
            {
                String paramName = next_param.paramName;
                String paramType = getReturnType(next_param.paramState);

				if ( next_param.arityType == ParameterDescriptor.ArityType.Variable )
				{
					paramType = codeEmitter.genNaryContainerType(paramType);
				}
                
                result += codeEmitter.genActionRoutineParameter(reducedValuesName, paramType, paramName);
            }
            
            for ( NamedSubtree named_child: this.namedChildNodes )
            {
                result += "\n\t" + iNodeClass + " " + named_child.name + " = " + named_child.path + ";";
            }

            // insert 2 tabs into each line, and convert \r\n to \n so the generated
			// files have consistent line endings.
			String[] actionlines = this.actionCode.toString().split("\n");
			for( int l = 0; l < actionlines.length; ++l )
			{
				if(actionlines[l].endsWith("\r"))
				{
					actionlines[l] = actionlines[l].substring(0,actionlines[l].length()-1);
				}
				result += "\n\t\t" + actionlines[l];
			}

			return result;
        }

        /**
         *  Track a name-to-subtree mapping.  These are unreduced I-nodes,
         *  typically a terminal identified by pattern match.
         *  @param path - the path from the root node to the subtree.
         *  @param name - the name to give to the subtree.
         */
        public void addNamedSubtree(String path, String name)
        {
            namedChildNodes.add(new NamedSubtree(path, name));
        }

        /**
         *  Set this reduction's antecedent state, which
         *  determines what reduction needs to run before
         *  this one to transform one nonterminal to another.
         */
        public void setAntecedentState(String antecedentState)
        {
            this.antecedentState = antecedentState;
        }

        /**
         *  @return true if this rule has an antecedent state,
         *    which also means it's a nonterminal-to-nonterminal rule.
         */
        public boolean hasAntecedentState()
        {
            return getAntecedentState() != null;
        }

        /**
         *  @return this rule's antecedent state,
         *    or null if no antecedent is present.
         */
        public String getAntecedentState()
        {
            return this.antecedentState;
        }
    }

    /**
     *  ClosureRecord tracks the target state, cost, and action code associated
     *  with a reduction from an antecedent nonterminal to a target nonterminal state.
     */
    private class ClosureRecord implements JBurgProduction
    {
        private JBurgRule rule;

        public ClosureRecord(JBurgRule rule) throws Exception
        {
            this.rule = rule;
        }

        /**
         *  Get the closure's uncached cost.
         *  @deprecated Will be removed when rules start caching costs.
         */
        public String getCost(String baseNT)
        {
            return this.rule.getCost(baseNT);
        }

        /**
         *  Get the closure's (potentially) cached cost.
         */
        @Override
        public String getCachedCost()
        {
            String cost = this.rule.getCost(reducerNodeName);

            //  The cost function result will be cached;
            //  return a unique accessor method name.
            if ( hasCostFunction() )
                return genCallMethod(null, String.format("getCostFunctionResult_%h", cost));
            else
                return cost;
        }

        /**
         *  @return the rule's hasCostFunction() result.
         */
        public boolean hasCostFunction()
        {
            return rule.hasCostFunction();
        }

        /**
         *  @return the rule's getConstantCost() result.
         */
        public int getConstantCost()
        {
            return this.rule.getConstantCost();
        }

        /**
         *  @return the rule's hasConstantCost() result.
         */
        public boolean hasConstantCost()
        {
            return this.rule.hasConstantCost();
        }

        /**
         *  @return the rule's getAntecedentState() result.
         */
        public String getAntecedentState()
        {
            return this.rule.getAntecedentState();
        }

        /**
         *  @return the rule's getGoalState() result.
         */
        @Override
        public String getGoalState()
        {
            return this.rule.getGoalState();
        }

        /**
         *  @return this closure's reduce action.
         */
        @Override
        public JBurgReduceAction getReduceAction()
        {
            return rule.getReduceAction();
        }

        /**
         *  Closure records are equal if they have the same goal state, action, and cost.
         *  @see java.lang.Object#equals
         *
         * @param o -- the object to test for equality.
         * @return true if o is a ClosureRecord and it equals this one.
         *
         */
        @Override
        public boolean equals(Object o)
        {
            boolean result = false;

            if (o instanceof ClosureRecord)
            {
                ClosureRecord cuz = (ClosureRecord) o;

                result = getGoalState().equals(cuz.getGoalState());
                result &= getReduceAction().equals(cuz.getReduceAction());
                result &= this.rule.getCost(reducerNodeName).equals(cuz.rule.getCost(reducerNodeName));
            }

            return result;
        }

        /**
         *  @return true if the cost of this closure is known to be zero.
         */
        public boolean costIsZero()
        {
            return hasConstantCost() && getConstantCost() == 0;
        }

        /**
         *  @return the computation of this closure's cost,
         *    which is somewhat error-prone when open coded.
         */
        public String getCostComputation()
        {
            String antecedentCost = 
                genCallMethod(
                    null,
                    "getCost",
                    getNonterminal(this.getAntecedentState())
                );

            if ( this.costIsZero() )
            {
                return antecedentCost;
            }
            else
                return codeEmitter.genOverflowSafeAdd(this.getCachedCost(), antecedentCost);
        }

        /**
         *  Precompute the cost of this closure if possible.
         *  @param productions - the set of productions at the
         *    point where the closure's cost is required.  If
         *    the closure derives a single pattern-match 
         *    rule that has a constant cost, and the closure
         *    itself has a constant cost, then the cost
         *    can be precomputed.
         *  @return the precomputed cost, or the result of
         *    calling {@link getCostComputation()} to get
         *    a non-constant cost.
         */
        public String getCostComputation(Multimap<String, JBurgProduction> productions)
        {
            //  A closure back to a pattern-match with constant cost can be precomputed.
            if ( this.computesConstantCost(productions) )
            {
                return Integer.toString(getConstantCost(productions));
            }
            else
            {
                //  Return the naive cost computation.
                return getCostComputation();
            }
        }

        /**
         *  Get the constant cost of a closure.
         *  @param productions - the set of productions at the
         *    point where the closure's cost is required.
         *  @return the cost, with overflow-safe addition.
         *  @pre computesConstantCost(productions) must be true.
         */
        @Override
        public int getConstantCost(Multimap<String, JBurgProduction> productions)
        {
            long constantAntecedent;
            JBurgProduction production = productions.get(this.getAntecedentState()).get(0);

            if ( production instanceof JBurgRule )
                constantAntecedent = ((JBurgRule)production).getConstantCost();
            else
                constantAntecedent = ((ClosureRecord)production).getConstantCost(productions);

            //  Integer-overflow safe addition.
            @SuppressWarnings("cast")
            long accum = (long)this.getConstantCost() + constantAntecedent;

            if ( accum < Integer.MAX_VALUE )
                return (int) accum;
            else
                return Integer.MAX_VALUE;
        }

        /**
         *  Does this closure compute a constant cost
         *  in the context of the given productions?
         *  @param productions - the set of productions at the
         *    point where the closure's cost is required.  If
         *    the closure derives a single pattern-match 
         *    rule that has a constant cost, and the closure
         *    itself has a constant cost, then the cost
         *    can be precomputed.
         *  @return true if the computed cost is constant.
         */
        @Override
        public boolean computesConstantCost(Multimap<String, JBurgProduction> productions)
        {
            boolean result = false;
            if ( this.hasConstantCost() )
            {
                ArrayList<JBurgProduction> antecedents = productions.get(this.getAntecedentState());

                if ( antecedents.size() == 1 )
                {
                    JBurgProduction production = antecedents.get(0);

                    if ( production instanceof JBurgRule )
                        result = ((JBurgRule)production).hasConstantCost();
                    else
                        result = ((ClosureRecord)production).computesConstantCost(productions);
                }
            }

            return result;
        }

    }

	/**
	 *  A ParameterDescriptor is a pair (name, subgoalState) which parallels
	 *  the FOO(name, subgoalState) found in the specification's syntax.
	 */
    private static class ParameterDescriptor
    {
        String paramName;
        String paramState;
        ArityType arityType;
        
        enum ArityType {Fixed, Variable}

        ParameterDescriptor(String paramName, String paramState, ArityType arityType)
        {
            this.paramName = paramName;
            this.paramState = paramState;
            this.arityType = arityType;
        }
    }

    /**
     *  Finish semantic analysis of the pattern rules.
     */
	private void ruleSemanticAnalysis() throws Exception
    {
        for (Vector<JBurgRule> vPatternRules: this.patternRules.values())
        {
            for (JBurgRule rule: vPatternRules)
            {
                for (JBurgPatternMatcher subgoal: rule.patternMatcher.getParameterizedSubtrees())
                {
                    rule.getReduceAction().addParameter(
                            subgoal.getParameterName(), 
                            subgoal.getSubgoal(), 
                            subgoal.isNary()? ParameterDescriptor.ArityType.Variable: ParameterDescriptor.ArityType.Fixed
                            );
                }

                //  Add the named subtrees as a convenience.
                for ( JBurgPatternMatcher named_terminal: rule.patternMatcher.getNamedSubtrees())
                {
                    rule.getReduceAction().addNamedSubtree(
                            named_terminal.generateReduceTimePath(codeEmitter, reducerNodeName, this.iNodeAdapter, this.adapter2 != null), 
                            named_terminal.getParameterName()
                            );
                }

                //  If the pattern matches an operator, send that operator
                //  to the rule so it can be matched in content-access snippets.
                if ( rule.patternMatcher.matchesOperator() )
                    rule.getReduceAction().setOperator(rule.patternMatcher.getOperator());
            }
        }
    }

	private void emitComputeCostMatrixFunction(String iNodeClass, PrintStream output) throws Exception 
	{
		//  Emit the method declaration and local variables.
		genDeclareMethod( output, Modifier.PRIVATE, "void", "computeCostMatrix", "JBurgAnnotation", "node");
		genBeginBlock(output);
		genLocalVar(output,  "long", "iCost", null );

		//  The calculations are based on finding patterns
		//  that can label the node's type.
		genSwitch(output, genCallMethod( "node", "getOperator" ));

		//  Try each pattern for a match.
		//  Any pattern that matches then checks its 
		//  cost to see if it's less than the current
		//  best cost for the node, and replaces the 
		//  node's current rule and cost with its own
		//  if it's the new best cost.

		for (Vector<JBurgRule> vPatternRules: this.patternRules.values())
		{
            genCase( output, vPatternRules.firstElement().getOperator() );
            
            //  Group rules by the patterns they match.
            Multimap<String, JBurgRule> rules_by_pattern = new Multimap<String, JBurgRule>();

            for (JBurgRule rule: vPatternRules)
            {
                String encoded_pattern = rule.getEncodedPattern();
                rules_by_pattern.addToSet(encoded_pattern, rule);
            }

            
            for ( String encoded_pattern: rules_by_pattern.keySet() )
            {
                ArrayList<JBurgRule> current_rules = rules_by_pattern.get(encoded_pattern);

                //  Emit the structural pattern match if it was not optimized out.
                if ( !encoded_pattern.equals(nilPattern))
                    genIf(output, encoded_pattern);
                
                //  Begin a block whether there was a test or not, to scope variables.
                //  TODO: This will not work for a target that doesn't block-scope locals.
                genBeginBlock(output);
                
                //  Find common path and cost subexpressions.
                Multimap<JBurgPatternMatcher, JBurgPatternMatcher> aggregated_matchers = new Multimap<JBurgPatternMatcher, JBurgPatternMatcher>();
                
                Multimap<String, JBurgPatternMatcher> costs = new Multimap<String, JBurgPatternMatcher>();
                
                for ( JBurgRule rule: rules_by_pattern.get(encoded_pattern))
                {
                    for (JBurgPatternMatcher subgoal: rule.patternMatcher.getParameterizedSubtrees() )
                    {
                        subgoal.aggregatePaths(aggregated_matchers);
                        costs.addToSet(subgoal.generateCost(codeEmitter, "node"), subgoal);
                    }
                }
                
                //  Factor out common paths.
                int factored_path_count = 0;
                for ( JBurgPatternMatcher key: aggregated_matchers.keySet())
                {
                    ArrayList<JBurgPatternMatcher> matchers = aggregated_matchers.get(key);
                    
                    if ( matchers.size() > aggregatePathThreshold  )
                    {
                        String factored_path_var = "factored_path_" + Integer.toString(++factored_path_count);
                        genLocalVar(output, "JBurgAnnotation ", factored_path_var, key.generatePathToRoot(codeEmitter, "node"));
                        
                        for ( JBurgPatternMatcher matcher: matchers)
                            matcher.factoredPath = factored_path_var;
                        
                    }
                }
                
                //  Now that the paths have been factored, factor out common costs.
                int factored_cost_count = 0;
                
                for (String key: costs.keySet() )
                {
                    if ( costs.get(key).size() > 1 )
                    {
                        String factored_cost_var = "factored_cost" + Integer.toString(++factored_cost_count);
                        //  Regenerate the cost because it may now use factored path expressions.
                        ArrayList<JBurgPatternMatcher> matchers = costs.get(key);
                        genLocalVar(output, "int", factored_cost_var, matchers.get(0).generateCost(codeEmitter, "node"));
                        for ( JBurgPatternMatcher subgoal: matchers)
                        {
                            subgoal.factoredCost = factored_cost_var;
                        }
                    }
                }

                //  Emit the cost checks and their labeling logic.
                
                int patternPosition = 0;

                for ( JBurgRule rule: current_rules )
                    emitPatternRule(rule, iNodeClass, output, patternPosition++ == 0);

                genEndBlock(output);
            }

            genEndCase(output);
		}

		genEndSwitch(output);
		genEndBlock(output);
	}
	
	/**
	 *  Emit a routine that inspects the operators found at compiler compile time,
	 *  and emits code to get the corresponding node's Nth child.
	 *  @param output - the current output stream.
	 */
	private void emitGetNthChild(PrintStream output)
	{
	    genDeclareMethod(
            output,
            Modifier.PRIVATE,
            this.iNodeClass,
            "getNthChild",
	        genFormals(this.iNodeClass, "node", "int", "index"),
            throwsNothing
        );
	    genBeginBlock(output);
	    genLocalVar(output, this.iNodeClass, "result", null);
	    
	    genSwitch(output, this.iNodeAdapter.genGetOperator("node", this.codeEmitter));
	    for ( String opcode: this.allOperators)
	    {
	        Integer choice_count = this.adapter2.getMaxNthChildChoice(opcode);
	        if ( choice_count != null )
	        {
                genCase(output, opcode);
	            genSwitch(output, "index");
	            for ( int i = 0; i < choice_count; i++ )
	            {
	                genCase(output, Integer.toString(i));
	                genAssignment(output, "result", this.adapter2.genGetNthChild(opcode, "node", i, codeEmitter));
	                genEndCase(output);
	                
	            }
                //  generate the default case for the index.
                {
                    genDefaultCase(output);
                    genAssignment(output, "result", this.adapter2.genGetDefaultChild(opcode, "node", "index", codeEmitter));
                    genEndCase(output);
                }

                genEndSwitch(output);
	            genEndCase(output);
	        }
	        
	    }
        //  generate the default case for the opcode.
        {
            genDefaultCase(output);
            genAssignment(output, "result", this.iNodeAdapter.genGetNthChild("node", "index", codeEmitter));
            genEndCase(output);
        }
	    genEndSwitch(output);
	    genReturnValue(output, "result");
	    genEndBlock(output);
	}

	private void emitPatternRule(JBurgRule p, String iNodeClass, PrintStream output, boolean isFirstRule ) throws Exception
	{
	    genComment(output, "Try matching " + p.getOperator() + " ==> " + p.getGoalState());
	    
        /*
		 *   Emit code to compute this rule's cost, which is the cost of the rule itself 
		 *   and all the non-terminals associated with it; then emit a comparison with
		 *   the current best cost.
		 */
		Vector<String> sub_costs = new Vector<String>();

		//  Compute the basic cost of the pattern match.
		sub_costs.add(
		    p.getCost( 
    			codeEmitter.genCast( 
    				iNodeClass, 
    				codeEmitter.genAccessMember("node", "m_node")
    			)
            )
		);
		
	   //  Try and compute a constant cost.
        Integer constant_cost = null;

		if ( p.hasConstantCost() )
		{
		    constant_cost = p.getConstantCost();
		}

		
		for ( JBurgPatternMatcher subgoal: p.patternMatcher.getParameterizedSubtrees() )
		{
		    String subgoal_cost = subgoal.generateCost(codeEmitter, "node");
		    if ( subgoal_cost != null )
		    {
		        sub_costs.add(subgoal_cost);
		        constant_cost = null;
		    }
		}
		
		String cost_factor;
        boolean checkCostFactor = true;
		
		if ( constant_cost != null )
		{
		    cost_factor = constant_cost.toString();
            checkCostFactor = constant_cost == Integer.MAX_VALUE;
		}
		else if ( sub_costs.size() == 1 )
		{
		    cost_factor = sub_costs.get(0);
		}
		else
		{
            //  Compute the cost using a long accumulator.
		    cost_factor = "iCost";

    		String match_cost = codeEmitter.genCast("long", sub_costs.get(0));
        		
            for ( int i = 1; i < sub_costs.size(); i++ )
                match_cost = codeEmitter.genAddition(match_cost, codeEmitter.genCast("long", sub_costs.get(i)));
    		
    		genAssignment(output, "iCost", match_cost);
		}

        if ( !isFirstRule || checkCostFactor )
        {
            //  Does this pattern match cost less than the previously best match?
            String getCostCall = genCallMethod ( "node", "getCost", codeEmitter.genGetGoalState(p) );
            String costCheck = codeEmitter.genCmpLess( getCostCall, cost_factor );
            genIf(output, costCheck );
        }

		output.print( codeEmitter.genBeginBlock() );

		/*
		 *   Emit code to handle a successful match.
		 */

		//  Reset the reduce-time rule to fire.
        String strRule = String.valueOf(p.getReduceAction().getIndex());
        
        //  Now that the comparison has been done using long arithmetic,
        //  iCost can be safely truncated to fit in an int.
        if ( cost_factor.equals("iCost"))
            cost_factor = codeEmitter.genCast("int", cost_factor);

        genExpressionStmt(
            output, 
			codeEmitter.genCallMethod(
				"node", 
				"reset", 
				new String[] { codeEmitter.genGetGoalState(p), cost_factor, strRule }
			)
		);

        if (hasClosure(p))
		{
            genExpressionStmt(
                output,
				genCallMethod( 
					null, 
					"closure_" + p.getGoalState(),
					"node", cost_factor
				)
			);
        }

        //  End the block begun by the cost comparison above.
        genEndBlock(output);
    }
	
	private JBurgPatternMatcher generateMatcher(AST pattern_root)
	throws Exception
	{   
        JBurgPatternEncoder patternBURM = new JBurgPatternEncoder();

        //  As we traverse the subtree, we may find parameterized subtrees,
        //  for example, in ADD(expr lhs, expr rhs) lhs and rhs are paramterized
        //  subtrees.  These subtrees play several parts in the computation of the
        //  locally-optimal reduction:
        //  -  They contribute to the rule's computed cost.
        //  -  The reduction's action code may refer to these elements by name.
        //  -  If the rule is of the form OP(nttype1 a [, nttype2 b]), then the rule
        //     must enforce this reduce-time goal state on its subtrees' reductions.
        patternBURM.setSubgoals(new Vector<JBurgPatternMatcher>());
        
        //  There may also be named terminals in the pattern;
        //  as a convenience, record these so that they
        //  can be used by name in the reduction.
        patternBURM.setNamedterminals(new Vector<JBurgPatternMatcher>());
        
        patternBURM.setOperators(this.allOperators);

        try
        {
            patternBURM.burm( pattern_root );
        }
        catch (IllegalStateException burm_error )
        {
            if ( this.patternMatcherDumpFile != null )
            {
                //  Dump the BURM's debugging info.
                java.io.PrintWriter dumper = new java.io.PrintWriter(new java.io.FileWriter(patternMatcherDumpFile));
                dumper.println ( "<?xml version=\"1.0\"?>");
                dumper.println("<BurmDump date=\"" + new java.util.Date().toString() + "\">");
                patternBURM.dump(dumper);
                dumper.println("<AST>");
                dumper.println("<![CDATA[");
                dumper.println(pattern_root.toStringTree());
                dumper.println("]]>");
                dumper.println("</AST>");
                dumper.println("</BurmDump>");
                dumper.flush();
                dumper.close();
            }
            
            throw burm_error;
        }
        
        JBurgPatternMatcher recognizer = (JBurgPatternMatcher) patternBURM.getResult();
        recognizer.setParameterizedSubtrees(patternBURM.getSubgoals());
        recognizer.setNamedSubtrees(patternBURM.getNamedterminals());
        
        return recognizer;
	}

	private void emitActions(ArrayList<JBurgReduceAction> reduceActions, String iNodeClass, PrintStream output)
	{
		int i = 1;

		//  Print out the individual action routines.
		for (JBurgReduceAction nextAction: reduceActions )
		{
            output.println();
			genComment(output, nextAction.getState());
			
            //  Compute the type of the i-node.
            String typeOfOperatorINode;
			final String actionOperator = nextAction.getOperator();

			if ( opcodeNodeTypes.containsKey(actionOperator) )
			    typeOfOperatorINode = opcodeNodeTypes.get(actionOperator);
			else
			    typeOfOperatorINode = iNodeClass;

			genDeclareMethod(
                output,
				Modifier.PRIVATE,
				getReturnType(nextAction.getState()),
				"action_" + String.valueOf(i++),
				genFormals(typeOfOperatorINode, reducerNodeName),
				throwsException
			);
				
			genBeginBlock(output);

			String action_routine = nextAction.toString();
			
			//  Replace #OPERATOR# with a content-access snippet.
			if ( this.adapter2 != null && nextAction.getOperator() != null )
			{
			    String content_access = this.adapter2.genGetContent(nextAction.getOperator(), this.reducerNodeName, nextAction.getState(), codeEmitter);
			    
			    if ( content_access != null )
			    {
			        String content_pattern = "#" + nextAction.getOperator() + "#";
			        action_routine = action_routine.replaceAll( content_pattern, content_access );
			    }
			}
			//  Replace #goalstate with the name of the action's input node.
			
			String goalPattern = "#" + nextAction.getState();
			action_routine = action_routine.replaceAll( goalPattern, this.reducerNodeName );
			
			output.print( action_routine );

			genEndBlock(output);
		}

		//  Emit their common dispatch routine.
		genDeclareMethod(
            output,
			Modifier.PRIVATE,
			"void",
			"dispatchAction",
			genFormals("JBurgAnnotation", "___node", "int", "iRule"),
			throwsException
		);

		genBeginBlock(output);

        genLocalVar(
            output,
            iNodeClass,
            this.reducerNodeName,
            genCallMethod("___node", "getNode")
        );

		genSwitch(output, "iRule" );

		//  Emit the dispatch case statement.
		for (i = 1; i <= reduceActions.size(); i++)
		{
            JBurgReduceAction action = reduceActions.get(i-1);

			genCase(output, String.valueOf(i));
            {
                //  If this is a nonterminal-to-nonterminal
                //  transformation, run the antecedent
                //  reduction action.
                if ( action.hasAntecedentState() )
                {
                    genExpressionStmt(
                        output,
                        genCallMethod(
                            "this",
                            "reduceAntecedent",
                            "___node", codeEmitter.genGetGoalState(action.getAntecedentState())
                        )
                    );
                }

                final String operatorName = action.getOperator();
                final String nodeTypeForOperator =
                    operatorName != null ? opcodeNodeTypes.get(operatorName) : null;
                String nodeParameterString = reducerNodeName;
                if (nodeTypeForOperator != null)
                    nodeParameterString = codeEmitter.genCast(nodeTypeForOperator, nodeParameterString);
                
                genExpressionStmt(
                    output,
                    codeEmitter.genPushToStack(
                        reducedValuesName,
                        genCallMethod(
                            "this",
                            "action_" + String.valueOf(i),
                            nodeParameterString
                        )
                    )
                );
            }
			genEndCase(output);
		}

		genDefaultCase(output);
        {
            genThrow(output, "\"Unmatched reduce action \" + iRule" );
        }
        genEndBlock(output); // genEndCase() without unreachable break
	    
		genEndSwitch(output);
		genEndBlock(output);
	}

	private void emitNTConstants(Set<String> goal_states, PrintStream output)
	{
		Iterator<String> keys = goal_states.iterator();

		int nthConstant = 0;

		output.print(codeEmitter.genBeginLine());
		while (keys.hasNext())
		{
			nthConstant++;

			String strNTName = codeEmitter.genGetGoalState(keys.next().toString() );

            genInstanceField(
                output, 
                Modifier.PUBLIC + Modifier.STATIC + Modifier.FINAL,
                "int",
                strNTName,
                String.valueOf(nthConstant)
			);
		}
	
        genInstanceField(
            output,
            Modifier.PUBLIC + Modifier.STATIC + Modifier.FINAL,
            "int",
            "nStates",
            String.valueOf(nthConstant)
		);
	}

	public void emitCostFunctions(ArrayList<AST> costFunctions, String iNodeClass, PrintStream output) 
	{
		String[][] costParms = genFormals( iNodeClass, reducerNodeName );

		for (int i = 0; i < costFunctions.size(); i++)
		{
			AST currentNode = costFunctions.get(i);

			String functionName = currentNode.getFirstChild().getText();

			genDeclareMethod(output, Modifier.PRIVATE, "int", functionName, costParms, throwsNothing );
			output.print( codeEmitter.genBeginLine() );
			output.print( getCodeBlock(currentNode) );
		}
	}

	public void emitClosures(Map<String, Vector<ClosureRecord>> closureSets, String iNodeClass, PrintStream output)
	{
        //  TODO: This method can be removed once the C++ target
        //  has been updated to 1.9.0 style semantics.
		for (String strClosureNT: closureSets.keySet())
		{
			genDeclareMethod(
				output,
                Modifier.PRIVATE,
                "void",
                "closure_" + strClosureNT,
                genFormals("JBurgAnnotation", reducerNodeName, "long", "c"),
                throwsNothing
			);

			genBeginBlock(output);

			genLocalVar(output, "long", "iCost", null );

			for (ClosureRecord newClosure: closureSets.get(strClosureNT) )
			{
				String strRule;

				if (newClosure.getReduceAction() != null)
					strRule = String.valueOf(newClosure.getReduceAction()
													   .getIndex());
				else
					strRule = "0";

				String closureCost = newClosure.getCost( codeEmitter.genAccessMember(reducerNodeName, "m_node"));

				if (closureCost.equals("0") )
				{
					genAssignment( output, "iCost", "c");
				}
				else
				{
					genAssignment( output, "iCost",  codeEmitter.genAddition( "c", closureCost ));
				}

                genIf(
                    output,
                    codeEmitter.genCmpLess(
                        genCallMethod (
                            reducerNodeName,
                            "getCost", 
                            getNonterminal(newClosure.getGoalState())
                        ),
                        "iCost"
					)
				);
				output.print( codeEmitter.genBeginBlock() );

                genExpressionStmt(
                    output,
					codeEmitter.genCallMethod(
						reducerNodeName,
						"reset",
						new String[] { getNonterminal(newClosure.getGoalState()), codeEmitter.genCast("int","iCost"), strRule }
					)
				);

                genExpressionStmt(
                    output,
					codeEmitter.genCallMethod(
						reducerNodeName,
						"recordAntecedent",
						new String[] { getNonterminal(newClosure.getGoalState() ), getNonterminal(strClosureNT ) }
					)
				);

				if (hasClosure(newClosure))
				{
                    genExpressionStmt(
                        output,
						genCallMethod(
							"this",
							"closure_" + newClosure.getGoalState(),
							reducerNodeName, "iCost"
						)
					);
				}

				genEndBlock(output);
			}

			genEndBlock(output);
		}
	}


	public void emitLabelFunction(String iNodeClass, PrintStream output)
	{
        genDeclareMethod(
            output,
            Modifier.PUBLIC,
            "JBurgAnnotation",
            "label",  
            genFormals(iNodeClass, JBurgGenerator.initalParamName),
            throwsNothing
		);

		genBeginBlock(output);
		genLocalVar (output,  "JBurgAnnotation", "result", codeEmitter.genNullPointer() );
		genLocalVar (output,  "int", "i", null);
		genLocalVar (output,  "int", "arity", null);

        String nodeAlloc = null;

        if ( codeEmitter.supportsSpecializedAnnotations() )
        {
			nodeAlloc = genCallMethod( "this", "getJBurgAnnotation", JBurgGenerator.initalParamName);
        }
        else
        {
			nodeAlloc = codeEmitter.genNewObject( "JBurgAnnotation", new String[] { JBurgGenerator.initalParamName, "nStates + 1" } );
        }
		genAssignment( output, "result", nodeAlloc );

		//  Generate a loop over children that labels them,
		//  and adds their labelled JBurgAnnotation nodes to the current node.
		genAssignment(output, "arity", this.iNodeAdapter.genGetArity(JBurgGenerator.initalParamName, codeEmitter));	
		genAssignment(output, "i", "0");

		genLine(output, codeEmitter.genWhileLoop( codeEmitter.genCmpLess("arity", "i")));
		genBeginBlock(output);
        {
            genExpressionStmt(
                output,
                genCallMethod(
                    "result",
                    "addChild",
                    genCallLabel("i")
                )
            );
            
            genAssignment(output, "i", codeEmitter.genAddition("i", "1") );
        }
		genEndBlock(output); // while

		//  Call the costing function.
        if ( ! this.codeEmitter.supportsSpecializedAnnotations() )
            genExpressionStmt(output, genCallMethod( "this", "computeCostMatrix", "result"));

		genReturnValue(output, "result" );
		genEndBlock(output);
	}

    /**
     *  Emit the subclasses of JBurgAnnotation that encode data for specific pattern matches.
     *  @param output - the destination output stream.
     */
    void emitCompressedAnnotations(PrintStream output)
    {
        //  Emit an annotation object for each equivalence class of rules.
        for ( String operator: this.compressedAnnotations.getOperators() )
            for ( ArrayList<JBurgRule> currentRules : this.compressedAnnotations.getRulesFor(operator) )
                emitAnnotation(output, currentRules);

        //  Emit getJBurgAnnotation
        genDeclareMethod(
            output,
            Modifier.PUBLIC,
            "JBurgAnnotation",
            "getJBurgAnnotation",  
            genFormals(iNodeClass, "node"),
            throwsNothing
        );

        genBeginBlock(output);

	    genSwitch(output, this.iNodeAdapter.genGetOperator("node", this.codeEmitter));

        for ( String operator: compressedAnnotations.getOperators() )
        {
            genCase(output, operator);

            for ( ArrayList<JBurgRule> rules : this.compressedAnnotations.getRulesFor(operator) )
            {
                int arity = getMinumumArity(rules);

                if ( hasNaryness(rules) )
                    genIf(output, String.format("%s >= %d", this.iNodeAdapter.genGetArity("node", codeEmitter), arity));
                else
                    genIf(output, String.format("%s == %d", this.iNodeAdapter.genGetArity("node", codeEmitter), arity));
                indentNextLine();
                genReturnValue(output, String.format("new %s(node)", getSpecializedClassName(rules)));
            }

            genEndCase(output);
        }

        genEndSwitch(output);
        
        genLine(output, "return new JBurgAnnotationGeneral(node, nStates+1);");
        genEndBlock(output); // getJBurgAnnotation
        
    }

    /**
     *  Emit an annotation subclass.
     *  @param output - the output stream.
     *  @param currentRules - the set of rules that are this annotation's
     *    domain.  The rules all have the same operator, but their arity
     *    may differ if some of them are n-ary.
     */
    void emitAnnotation(PrintStream output, ArrayList<JBurgRule> currentRules )
    {
        int nominalArity = getMinumumArity(currentRules);

        // The coalesced graph of closures for all the rules.
        ClosureGraph closureCosts = new ClosureGraph();

        //  Factored common subtrees of each pattern matcher.
        //  TODO: These can be further coalesced by using the right comparator.
        Multimap<JBurgPatternMatcher,JBurgPatternMatcher> commonSubtrees = new Multimap<JBurgPatternMatcher,JBurgPatternMatcher>();

        //  Rules and closures by nonterminal.
        Multimap<String, JBurgProduction> productions = new Multimap<String, JBurgProduction>();

        //  Cached subtree costs.
        Map<String, String> cachedCosts = new HashMap<String, String>();

        //  Are all these rules fixed-arity?
        //  If so, the annotation knows its arity a priori.
        boolean fixedArity = !hasNaryness(currentRules);

        /*
         *  **  Semantic analysis  **
         */
        
        //  Populate the closure graph and factor the pattern matchers.
        for ( JBurgRule rule: currentRules)
        {
            productions.addToSet(rule.getGoalState(), rule);

            closureCosts.addClosures(rule.getGoalState());

            if ( fixedArity )
                rule.patternMatcher.setFixedArityContext(true);

            for ( JBurgPatternMatcher subgoal: rule.patternMatcher.getParameterizedSubtrees() )
                subgoal.findFactors(commonSubtrees);

            if ( rule.patternMatcher.getNominalArity() > 0 )
            {
                cachedCosts.put(rule.getGoalState(), String.format("cachedCostFor_%s", rule.getGoalState()));
            }
        }

        //  Add the closures from the coalesced closure graph
        //  to the set of productions.
        for ( Map.Entry<String, ArrayList<ClosureRecord>> closures: closureCosts.entrySet() )
        {
            for ( ClosureRecord closure: closures.getValue() )
                productions.addToSet(closures.getKey(), closure);
        }

        //  Emitting these variable declarations mutates the 
        //  pattern matchers, so they can only be emitted once.
        //  Capture the results so we can write it more than once.
        Map<JBurgPatternMatcher,String> factored_variables = emitFactoredPathVariables(commonSubtrees);

        /*
         * Begin code-gen of the class.
         */
        output.println();
        String annotationClass = getSpecializedClassName(currentRules);
        
        genLine(output, String.format("class %s extends JBurgSpecializedAnnotation", annotationClass));
        genBeginBlock(output);

        //  Emit a field for each child.
        for ( int fieldIdx = 0; fieldIdx < nominalArity; fieldIdx++ )
        {
            genInstanceField( output, Modifier.PRIVATE, "JBurgAnnotation", String.format("subtree%d", fieldIdx), null);
        }

        if ( !fixedArity )
        {
            genInstanceField( 
                output,
                Modifier.PRIVATE,
                codeEmitter.genNaryContainerType("JBurgAnnotation"),
                "narySubtrees",
                String.format("new %s()", codeEmitter.genNaryContainerType("JBurgAnnotation"))
            );
        }

        // Emit the constructor.
        //  TODO: The emitter needs a genConstructor() API.
        genLine(output, String.format("%s(%s node)", annotationClass, this.iNodeClass));
        genBeginBlock(output);
        //  TODO: The emitter also needs a callSuperclassConstructor() API.
        genLine(output, "super(node);");
        genEndBlock(output);

        for ( String cachedCostVar: cachedCosts.values() )
        {
            genInstanceField( output, Modifier.PRIVATE, "int", cachedCostVar, UNINITIALIZED);
        }

        /*
         *  ** Emit getCost()  **
         */
        genDeclareMethod( output, Modifier.PUBLIC, "int", "getCost", "int", "goalState" );
        genBeginBlock(output);

        genSwitch(output, "goalState");

        for ( Map.Entry<String, ArrayList<JBurgProduction>> productionsByNonterminal: productions.entrySet() )
        {
            genCase(output, getNonterminal(productionsByNonterminal.getKey()));

            ArrayList<JBurgProduction> currentProductions = productionsByNonterminal.getValue();

            //  Try to find the optimal production at compiler-compile time.
            JBurgProduction optimalProduction = findOptimalProduction(currentProductions, productions);

            if ( optimalProduction != null )
            {
                genReturnValue(output, Integer.toString(optimalProduction.getConstantCost(productions)));
            }
            else
            {
                final boolean hasMultipleProductions = currentProductions.size() > 1;
                final boolean cacheCost = cachedCosts.containsKey(productionsByNonterminal.getKey());

                boolean currentCostDeclared = false;

                String bestCostVar;

                if ( cacheCost )
                {
                    bestCostVar = cachedCosts.get(productionsByNonterminal.getKey());
                    genIf ( output, codeEmitter.genCmpEquality(bestCostVar, UNINITIALIZED, true) );
                    genBeginBlock(output);
                }
                else if ( hasMultipleProductions )
                {
                    //  Store the best cost in a local.
                    bestCostVar = "bestCost";
                    genLocalVar(output, "int", "bestCost");
                }
                else
                {
                    bestCostVar = codeEmitter.genMaxIntValue();
                }

                for ( int i = 0; i < currentProductions.size(); i++ )
                {
                    JBurgProduction production = currentProductions.get(i);
                    String productionCost = getCostForProduction(production, productions);

                    if ( currentProductions.size() == 1 && !cacheCost )
                    {
                        //  Only one production, just return its cost.
                        genReturnValue(output, productionCost);
                    }
                    else if ( i == 0 )
                    {
                        //  Emit an assignment with no if guards
                        //  if this is the first (or only) assignment.
                        genAssignment(output, bestCostVar, productionCost);
                        output.println();
                    }
                    else
                    {
                        //  If the cost uses a computation, put it in a temp.
                        if ( !production.computesConstantCost(productions) )
                        {
                            if ( ! currentCostDeclared )
                            {
                                genLocalVar(output, "int", "currentCost", productionCost);
                                currentCostDeclared = true;
                            }
                            else
                            {
                                genAssignment(output, "currentCost", productionCost);
                            }
                            
                            productionCost = "currentCost";
                        }

                        genIf(output, codeEmitter.genCmpLess(bestCostVar, productionCost));
                        indentNextLine();
                        genAssignment(output, bestCostVar, productionCost);
                    }
                }

                if ( cacheCost )
                    //  End the if statement.
                    genEndBlock(output);

                if ( cacheCost || hasMultipleProductions )
                    genReturnValue(output, bestCostVar);
                // else the cost has already been returned.
            }

            genEndBlock(output); // end case without unreachable break
        }
        genEndSwitch(output);
        genReturnValue(output, codeEmitter.genMaxIntValue());
        genEndBlock(output); // getCost

        /*
         *  ** Emit getRule()  **
         */
        genDeclareMethod(output, Modifier.PUBLIC, "int", "getRule", "int", "goalState" );
        genBeginBlock(output);

        genSwitch(output, "goalState");

        for ( Map.Entry<String, ArrayList<JBurgProduction>> productionsByNonterminal: productions.entrySet() )
        {
            genCase(output, getNonterminal(productionsByNonterminal.getKey()));

            ArrayList<JBurgProduction> currentProductions = productionsByNonterminal.getValue();

            //  Try to resolve the optimal production at compiler-compile time.
            JBurgProduction optimalProduction = findOptimalProduction(currentProductions, productions);

            if ( optimalProduction != null )
            {
                genReturnValue(output, Integer.toString(optimalProduction.getReduceAction().getIndex()));
            }
            else
            {
                // Emit the analogous compile-time computation.
                genLocalVar(output, "int", "rule", NO_FEASIBLE_RULE);
                genLocalVar(output, "int", "bestCost", codeEmitter.genMaxIntValue());

                //  Emit this declaration at its first use.
                boolean currentCostDeclared = false;

                for ( int i = 0; i < currentProductions.size(); i++ )
                {
                    boolean costIsConstant = false;
                    String currentProductionCost;

                    //  Extract required information from the production:
                    //  what is its cost, and is it constant?
                    JBurgProduction production = currentProductions.get(i);

                    if ( production.computesConstantCost(productions) )
                    {
                        int constantCost = production.getConstantCost(productions);
                        costIsConstant = constantCost < Integer.MAX_VALUE;
                        currentProductionCost = Integer.toString(constantCost);
                    }
                    else
                    {
                        currentProductionCost = getCostForProduction(production, productions);
                    }

                    //  Generate the necessary tests and assignments.

                    //  If the first production's cost is constant
                    //  (and feasible, which has been checked and
                    //  incorporated into costIsConstant), then 
                    //  testing it against bestCost is a tautology.
                    boolean needComparison = (!costIsConstant) || i > 0;

                    if ( needComparison )
                    {
                        //  If the cost uses a computation, put it in a temp.
                        if ( ! costIsConstant )
                        {
                            if ( ! currentCostDeclared )
                            {
                                genLocalVar(output, "int", "currentCost", currentProductionCost);
                                currentCostDeclared = true;
                            }
                            else
                            {
                                genAssignment(output, "currentCost", currentProductionCost);
                            }
                            currentProductionCost = "currentCost";
                        }

                        genIf(output, codeEmitter.genCmpLess("bestCost", currentProductionCost));
                        genBeginBlock(output);
                    }

                    //  Track the new best cost if there's another choice to be evaluated.
                    if ( i + 1 < currentProductions.size() )
                        genAssignment(output, "bestCost", currentProductionCost);

                    genAssignment(output, "rule", Integer.toString(production.getReduceAction().getIndex()));

                    if ( needComparison )
                        genEndBlock(output);
                }

                genReturnValue(output,"rule");
            }

            genEndBlock(output);  // endCase() without unreachable break statement
        }

        genEndSwitch(output);
        genReturnValue(output, NO_FEASIBLE_RULE);
        genEndBlock(output); // getRule

        /*
         *  ** Emit getArity()  **
         */
        genDeclareMethod(output, Modifier.PUBLIC, "int", "getArity");
        genBeginBlock(output);

        if ( fixedArity )
        {
            genReturnValue(output, Integer.toString(nominalArity));
        }
        else if ( nominalArity != 0 )
        {
            //  TODO: Need an emitter method to get the correct size() call
            genReturnValue(output, String.format("%d + %s", nominalArity, "narySubtrees.size()" ));
        }
        else
        {
            genReturnValue(output, "narySubtrees.size()" );
        }

        genEndBlock(output); // getArity

        /*
         *  **  Emit overrides for getNthChild() and addChild() if necessary  **
         */
        if ( nominalArity > 0 || ! fixedArity )
        {
            //  getNthChild
            genDeclareMethod( output, Modifier.PUBLIC, "JBurgAnnotation", "getNthChild", "int", "index");

            genBeginBlock(output); // getNthChild
            genSwitch(output, "index");

            for ( int i = 0; i < nominalArity; i++ )
            {
                genLine(output, String.format("case %d:", i));
                genSingleLineBlock(output, String.format("return subtree%d;", i));
            }

            genDefaultCase(output);
            if ( ! fixedArity )
            {
                if ( nominalArity == 0 )
                    genLine(output, "return narySubtrees.get(index);");
                else
                    genLine(output, String.format("return narySubtrees.get(index - %d);", nominalArity));
            }
            else
            {
                genThrow(output, "\"Invalid index \" + index");
            }
            genEndBlock(output);  //  genEndCase() without unreachable break

            genEndBlock(output); // switch
            genEndBlock(output); // getNthChild

            //  addChild
            genDeclareMethod(output, Modifier.PUBLIC, "void", "addChild", "JBurgAnnotation", "child");

            genBeginBlock(output); // addChild

            for ( int i = 0; i < nominalArity; i++ )
            {
                if ( i == 0 )
                    genLine(output, String.format("if ( subtree%d == null )", i));
                else
                    genLine(output, String.format("else if ( subtree%d == null )", i));
                genSingleLineBlock(output, String.format("subtree%d = child;", i));
            }

            if ( nominalArity > 0 )
                genLine(output, String.format("else"));

            if ( ! fixedArity )
                genSingleLineBlock(output, "narySubtrees.add(child);");
            else
                genSingleLineBlock(output, "throw new IllegalStateException(\"too many children\");");

            genEndBlock(output); // addChild
        }

        //  Emit caches for any costs that require a function call;
        //  the BURM's contract says these functions are only called once.
        Set<String> emittedCosts = new HashSet<String>();

        for ( ArrayList<ClosureRecord> closures: closureCosts.values() )
            for ( ClosureRecord closure: closures )
                if ( closure.hasCostFunction() && emittedCosts.add(closure.getCachedCost()) )
                    emitCachedCost(output, closure.getCachedCost(), closure.getCost("m_node")); 

        for ( JBurgRule rule: currentRules )
        {
            if ( rule.needsCostFunction() )
                emitGetCostForRule(output, rule, factored_variables);

            if ( rule.hasCostFunction() && emittedCosts.add(rule.getCachedCost()) )
                emitCachedCost(output, rule.getCachedCost(), rule.getCost("m_node")); 
        }

        //  Finish the compressed annotation's class declaration.
        genEndBlock(output);
    }

    /**
     *  @param productions - a list of productions.
     *  @return true if the list has one member and that member has a constant cost.
     */
    boolean hasConstantCost(ArrayList<JBurgProduction> productions)
    {
        return productions != null &&
            productions.size() == 1 && 
            productions.get(0) instanceof JBurgRule &&
            ((JBurgRule)productions.get(0)).hasConstantCost();
    }

    /**
     *  @return the expression to use for a production's cost;
     *    this may be an arithmetic expression or a call
     *    to an implementation method, depending on
     *    the production's complexity.
     */
    String getCostForProduction(JBurgProduction production, Multimap<String,JBurgProduction> productions)
    {
        if ( production instanceof JBurgRule )
        {
            JBurgRule rule = (JBurgRule) production;
            if ( rule.needsCostFunction() )
                return genCallMethod(null, getCostingFunctionForRule(rule), "goalState");
            else
                return getCompositeCostOfRule(rule);
        }
        else
        {
            return ((ClosureRecord)production).getCostComputation(productions);
        }
    }

    /**
     *  Do compiler-compile time dynamic programming to choose
     *  the best alternative from a list of possibilities.
     *  @param currentProductions - the list of productions to choose from.
     *  @param allProductions - the entire set of productions active at the site.
     */
    JBurgProduction findOptimalProduction(List<JBurgProduction> currentProductions, Multimap<String, JBurgProduction> allProductions)
    {
        int bestCost = Integer.MAX_VALUE;
        JBurgProduction result = null;

        for ( JBurgProduction production: currentProductions )
        {
            if ( production.computesConstantCost(allProductions) )
            {
                int cost = production.getConstantCost(allProductions);
                if ( cost < bestCost )
                {
                    result = production;
                    bestCost = cost;
                }
            }
            else
            {
                //  Can't be determined at compiler-compile time.
                result = null;
                break;
            }
        }

        return result;
    }

    /**
     *  Emit a rule's cost function.
     *  @param output - the current output stream.
     *  @param rule - the rule to emit.
     *  @param factored_variables - the list of pattern matchers it's worth factoring.
     */
    void emitGetCostForRule(PrintStream output, JBurgRule rule, Map<JBurgPatternMatcher,String> factored_variables )
    {
        assert(rule.needsCostFunction());

        genDeclareMethod(output, Modifier.PRIVATE, "int", getCostingFunctionForRule(rule), "int", "goalState");
        genBeginBlock(output);
        {
            for ( String var_decl: factored_variables.values() )
                if ( rule.patternMatcher.usesFactoredVariable(var_decl) )
                genLine(output, var_decl);

            output.println();

            String patternMatch = rule.patternMatcher.generatePatternRecognizer(
                    codeEmitter,
                    "this",
                    JBurgGenerator.this.adapter2
                );

            // The pattern match may be null if it's trival.
            if ( patternMatch != null )
            {
                genIf(output, patternMatch);
                indentNextLine();
            }

            genReturnValue(output, getCompositeCostOfRule(rule));

            if ( patternMatch != null )
            {
                genLine(output, codeEmitter.genElse());
                indentNextLine();
                genReturnValue(output, codeEmitter.genMaxIntValue());
            }

        }
        genEndBlock(output);
    }

    /**
     *  @return a unique identifier for the method that computes
     *    a rule's cost (note: this is not the rule's cost function).
     */
    String getCostingFunctionForRule(JBurgRule rule)
    {
        if ( ! ruleNumber.containsKey(rule) )
            ruleNumber.put(rule, String.format("getCostForRule%x", ruleNumber.size()));
        return ruleNumber.get(rule);
    }

    private Map<JBurgRule,String> ruleNumber = new HashMap<JBurgRule, String>();
    
    /**
     *  Emit the cache field and accessor function for a cached 
     *    result of a cost function call.
     */
    void emitCachedCost(PrintStream output, String functionName, String payload)
    {
        //  Strip () characters.
        functionName = functionName.substring(0, functionName.length() -2);

        String varName = String.format("cachedCostFunctionResult_%h", functionName);

        genInstanceField( output, Modifier.PRIVATE, "int", varName, UNINITIALIZED);

        genDeclareMethod( output, Modifier.PRIVATE, "int", functionName );

        genBeginBlock(output);
        {
            genIf ( output, codeEmitter.genCmpEquality(varName, UNINITIALIZED, true) );
            indentNextLine();
            genAssignment(output, varName, payload);
            genReturnValue(output, varName);
        }
        genEndBlock(output);
    }

    /**
     *  Add up all of a rule's cost factors.
     *  @param rule - the rule of interest.
     *  @return an overflow-safe addition of the
     *    rule's cost and the costs of its subtrees.
     */
    String getCompositeCostOfRule(JBurgRule rule)
    {
        String subtreeCost = null;

        for ( JBurgPatternMatcher subgoal: rule.patternMatcher.getParameterizedSubtrees() )
        {
            String subgoalCost = subgoal.generateCost(codeEmitter, "this");

            if ( subgoalCost != null )
                subtreeCost = codeEmitter.genAddition(subtreeCost, codeEmitter.genCast("long", subgoalCost));
        }

        if ( subtreeCost != null )
            return codeEmitter.genOverflowSafeAdd(rule.getCachedCost(), subtreeCost);
        else
            return rule.getCachedCost();
    }

    /**
     *  Emit the factored path variables into a map,
     *  and mutate the affected pattern matchers
     *  to refer to the factored variable.
     *  @param commonSubtrees - the map of common subtrees to their pattern matchers.
     */
    Map<JBurgPatternMatcher,String> emitFactoredPathVariables(Multimap<JBurgPatternMatcher, JBurgPatternMatcher> commonSubtrees)
    {
        Map<JBurgPatternMatcher,String> result = new TreeMap<JBurgPatternMatcher, String>();

        int varNum = 0;
        for ( Map.Entry<JBurgPatternMatcher, ArrayList<JBurgPatternMatcher>> factored: commonSubtrees.entrySet() )
        {
            String varName = String.format("factoredPath_%d", varNum++);

            result.put(factored.getKey(), codeEmitter.genLocalVar("JBurgAnnotation", varName, factored.getKey().generateFactoredReference(codeEmitter)));

            for ( JBurgPatternMatcher matcher: factored.getValue() )
                matcher.factoredPath = varName;
        }
    
        return result;
    }

    /**
     *  ClosuresByNonterminal is a convenience class that holds
     *  closure sets grouped by nonterminal; the NT may
     *  be the production or the antecedent, depending on usage.
     */
    class ClosuresByNonterminal extends Multimap<String, ClosureRecord>
    {
        /**
         *  Add a closure record.
         *  @param nt - the nonterminal that indexes this closure.
         *    May be the production or the antecedent.
         */
        public void addClosure(String nt, ClosureRecord closure)
        {
            if ( ! this.getSet(nt).contains(closure) )
                this.getSet(nt).add(closure);
        }
    }

    /**
     *  A ClosureGraph holds the graph of closures that
     *  can be reached from a starting nonterminal.
     */
    class ClosureGraph extends ClosuresByNonterminal
    {
        /**
         *  Sweep the set of nonterminal-to-nonterminal rules and
         *  add any that can be produced by the most recently
         *  added nonterminal.
         *  @param currentNT - the most recently added nonterminal.
         */
        void addClosures(String currentNT)
        {
            addClosures(currentNT, currentNT);
        }

        /**
         *  Sweep the set of nonterminal-to-nonterminal rules and
         *  add any that can be produced by the most recently
         *  added nonterminal.
         *  @param currentNT - the most recently added nonterminal.
         *  @param patternNT - the nonterminal produced by the pattern match.
         */
        void addClosures(String currentNT, String patternNT)
        {
            if ( JBurgGenerator.this.closureSets.containsKey(currentNT) )
            {
                for ( ClosureRecord closure: JBurgGenerator.this.closureSets.get(currentNT) )
                {
                    String newNT = closure.getGoalState();

                    //  Can't replace the pattern with a closure.
                    if ( !newNT.equals(patternNT) )
                    {
                        if ( ! this.containsKey ( newNT ) )
                        {
                            super.addClosure(newNT, closure);
                            addClosures(newNT);
                        }
                        else
                        {
                            //  Add this closure, but its consequent
                            //  closures are already in the set so
                            //  it's not necessary to add them.
                            super.addClosure(newNT, closure);
                        }
                    }
                }
            }
        }
    }

    /**
     *  @return the current Logger implementation;
     *    constructs a Logger that emits messages
     *    to stdout/stderr.
     */
    Logger getLogger()
    {
        if ( null == this.logger )
            this.logger = new Logger(true, true, true);
        return this.logger;
    }

    /**
     *  Convenience method wraps codeEmitter.genAssignment and prints the result.
     */
	void genAssignment(PrintStream output, String lvalue, String rvalue)
	{
		genLine(output, codeEmitter.genAssignment( lvalue, rvalue ) );
	}

    /**
     *  Convenience method wraps codeEmitter.genComment and prints the result.
     */
    void genComment(PrintStream output, String comment)
    {
        genLine(output, codeEmitter.genComment(comment) );
    }

    /**
     *  Convenience method wraps codeEmitter.genLine and prints the result.
     *  @param output - the current output stream
     *  @param contents - the contents to write.  Contents will be trimmed
     *    of whitespace before output.
     */
    void genLine(PrintStream output, String contents)
    {
        String formattedContents = contents.trim();

        if ( doIndentNextLine )
            formattedContents = "\t" + formattedContents;

        doIndentNextLine = false;
        output.print(codeEmitter.genLine(formattedContents) );
    }

    /**
     *  When set, indent the next line of output to note that
     *  the statement on that line is an if/then branch.
     *  @see {@link #indentNextLine()}, which sets this field.
     *  @see {@link #genLine(PrintStream,String)}, which consumes this field and resets it.
     *
     */
    boolean doIndentNextLine = false;

    /**
     *  Signal that the next line should be indented.
     *  @see {@link #doIndentNextLine}, which this method sets.
     */
    void indentNextLine()
    {
        doIndentNextLine = true;
    }

    /**
     *  Convenience method wraps codeEmitter.genLine and prints the result,
     *  with an extra level of nesting added to improve readability.
     */
    void genSingleLineBlock (PrintStream output, String contents)
    {
        indentNextLine();
        genLine(output, contents);
    }

    /**
     *  Convenience method wraps codeEmitter.genBeginBlock and prints the result.
     */
    void genBeginBlock(PrintStream output)
    {
        output.print(codeEmitter.genBeginBlock());
    }
    
    /**
     *  Convenience method wraps codeEmitter.genEndBlock and prints the result.
     */
    void genEndBlock(PrintStream output)
    {
        output.print(codeEmitter.genEndBlock());
    }

    /**
     *  Convenience method wraps codeEmitter.genSwitch and prints the result.
     */
    void genSwitch(PrintStream output, String expression)
    {
        genLine(output, codeEmitter.genSwitch(expression) );
        genBeginBlock(output);
    }

    /**
     *  Convenience method wraps codeEmitter.genEndSwitch and prints the result.
     */
    void genEndSwitch(PrintStream output)
    {
        genLine(output, codeEmitter.genEndSwitch() );
    }

    /**
     *  Convenience method wraps codeEmitter.genCase and prints the result.
     */
    void genCase(PrintStream output, String selector )
    {
        output.print(codeEmitter.genCase(selector));
    }

    /**
     *  Convenience method wraps codeEmitter.genEndCase and prints the result.
     */
    void genEndCase(PrintStream output)
    {
        output.print(codeEmitter.genEndCase());
    }

    /**
     *  Convenience method wraps codeEmitter.genDefaultCase and prints the result.
     */
    void genDefaultCase(PrintStream output)
    {
        genLine(output, codeEmitter.genDefaultCase());
        genBeginBlock(output);
    }

    /**
     *  Convenience method wraps codeEmitter.genIf and prints the result.
     */
    void genIf(PrintStream output, String condition )
    {
        genLine(output, codeEmitter.genIf(condition));
    }

    /**
     *  Convenience method wraps codeEmitter.genReturnValue and prints the result.
     */
    void genReturnValue(PrintStream output, String value )
    {
        genLine(output, codeEmitter.genReturnValue(value) + codeEmitter.genEndStmt());
    }

    /**
     *  Convenience method prints an expression as a statement.
     */
    void genExpressionStmt(PrintStream output, String expr)
    {
        genLine(output, expr + codeEmitter.genEndStmt());
    }

    /**
     *  Convenience method wraps codeEmitter.genDeclareMethod and prints the result.
     */
    void genDeclareMethod(PrintStream output, int modifiers, String returnClass, String name, String[][] plist, Class<?>[] exceptions )
    {
        output.print(codeEmitter.declareMethod(modifiers, returnClass, name, plist, exceptions));
    }

    /**
     *  Convenience method declares BURM methods that don't throw.
     */
    void genDeclareMethod(PrintStream output, int modifiers, String returnClass, String name, Object ... plist)
    {
        genDeclareMethod(output, modifiers, returnClass, name, genFormals(plist), throwsNothing);
    }

    /**
     *  Convenience method declares BURM methods that don't throw or have parameters.
     */
    void genDeclareMethod(PrintStream output, int modifiers, String returnClass, String name)
    {
        genDeclareMethod(output, modifiers, returnClass, name, noFormalParameters, throwsNothing);
    }

    /**
     *  Generate formal parameters from a list of type, name pairs.
     *  @param raw_formals - a variadic list of type, name pairs.
     *  @return the raw formals marshalled into a 2-dimensional array.
     */
    String[][] genFormals(Object ... raw_formals)
    {
        assert(raw_formals.length % 2 == 0): "n-ary formal parameters must be in (type, name) pairs";

        String[][] plist = new String[raw_formals.length/2][2];
        for ( int i = 0; i < raw_formals.length - 1; i += 2  )
        {
            plist[i/2][0] = raw_formals[i].toString();
            plist[i/2][1] = raw_formals[i+1].toString();
        }

        return plist;
    }

    /**
     *  Convenience method wraps codeEmitter.genLocalVar and prints the result.
     */
    void genLocalVar(PrintStream output, String varType, String varName, String initializer)
    {
        genLine(output, codeEmitter.genLocalVar(varType, varName, initializer));
        output.println();
    }

    /**
     *  Convenience method wraps codeEmitter.genLocalVar and prints the result.
     */
    void genLocalVar(PrintStream output, String varType, String varName)
    {
        genLocalVar(output, varType, varName, null);
    }

    /**
     *  Convenience method wraps codeEmitter.genThrow and prints the result.
     */
    void genThrow( PrintStream output, String diagnostic )
    {
        genLine(output, codeEmitter.genThrow(diagnostic) + codeEmitter.genEndStmt() );
    }

    /**
     *  Convenience method wraps codeEmitter.genInstanceField and prints the result.
     */
    void genInstanceField(PrintStream output, int modifiers, String type, String name, String initializer)
    { 
        genLine(output, codeEmitter.genInstanceField(modifiers, type, name, initializer));
    }

    /**
     *  Convenience method wraps codeEmitter.genGetGoalState.
     */
    String getNonterminal(String raw_nt)
    {
        return codeEmitter.genGetGoalState(raw_nt);
    }

    /**
     *  Convenience method wraps codeEmitter.genCallMethod for methods with no parameters.
     */
    String genCallMethod(String stem, String methodName)
    {
        return codeEmitter.genCallMethod(stem, methodName, noActualParameters );
    }
    
    /**
     *  Convenience method wraps codeEmitter.genCallMethod for methods with one parameter.
     */
    String genCallMethod(String stem, String methodName, Object param)
    {
        return codeEmitter.genCallMethod(stem, methodName, new String[] { param.toString() } );
    }

    /**
     *  Convenience method wraps codeEmitter.genCallMethod for methods with two parameters.
     */
    String genCallMethod(String stem, String methodName, Object param1, Object param2)
    {
        return codeEmitter.genCallMethod(stem, methodName, new String[] { param1.toString(), param2.toString() } );
    }


    /**
     *  @return the input string with its outer
     *    layer of {} brackets stripped off.
     */
    public static String stripBrackets(String src)
    {
        int startchar = src.indexOf('{') + 1;
        int lentoend = src.lastIndexOf('}');
        return src.substring( startchar, lentoend-startchar );
    
    }

    /**
     *  Generate the correct calling sequence to get the nth child
     *  of an input i-node.
     *  @param indexTerm - the n in nth child.
     */
    String genGetNthChild(String indexTerm)
    {
		return this.adapter2 != null ?
		    genCallMethod("this", "getNthChild", JBurgGenerator.initalParamName, indexTerm):
	        this.iNodeAdapter.genGetNthChild( JBurgGenerator.initalParamName, indexTerm, codeEmitter );
    }
		
    /**
     *  Generate the calling sequence for the label() method.
     */
    String genCallLabel(String indexTerm)
    {
        return genCallMethod(
            "this",
            "label",
            codeEmitter.genCast( 
                iNodeClass, 
                genGetNthChild(indexTerm)
            )
        );
    }

    /**
     *  @return true if any rules in the list have n-ary operands.
     */
    private boolean hasNaryness(Collection<JBurgRule> rules)
    {
        boolean result = false;

        for ( JBurgRule rule: rules )
            result |= rule.patternMatcher.hasNaryness();

        return result;
    }

    /**
     *  @return the minumum arity of a list of rules.
     */
    private int getMinumumArity(Collection<JBurgRule> rules)
    {
        int result = Integer.MAX_VALUE;

        for ( JBurgRule rule: rules )
            result = Math.min(result, rule.patternMatcher.getNominalArity());

        return result;
    }

    /**
     *  @return the name of a JBurgAnnotation specialized subclass.
     */
    String getSpecializedClassName(ArrayList<JBurgRule> rules )
    {
        if ( hasNaryness(rules) )
            return String.format("JBurgAnnotation_%s_%d_n", rules.get(0).getOperator(), getMinumumArity(rules));
        else
            return String.format("JBurgAnnotation_%s_%d", rules.get(0).getOperator(), getMinumumArity(rules));
    }

    /**
     *  RulesByOperatorAndArity is a multidimensional associative store that
     *  sorts JBurgRules into equivalence classes, where the equivalaence
     *  relation is "these rules can share an annotation object."
     */
    class RulesByOperatorAndArity
    {
        /**
         *  Unsorted rules.
         */
        Multimap<String, JBurgRule> unsortedRules = new Multimap<String, JBurgRule>();

        Map<String, Iterable<ArrayList<JBurgRule>>> sortedRules = null;

        public void addAll(List<JBurgRule> rules)
        {
            assert sortedRules == null;

            String operator = rules.get(0).getOperator();
            this.unsortedRules.addAllToSet(operator, rules);
        }

        public void addRule(JBurgRule rule)
        {
            assert sortedRules == null;
            this.unsortedRules.addToSet(rule.getOperator(), rule);
        }

        public Set<String> getOperators()
        {
            return unsortedRules.keySet();
        }

        public Iterable<ArrayList<JBurgRule>> getRulesFor(String operator)
        {
            if ( this.sortedRules == null )
            {
                this.sortedRules = new TreeMap<String, Iterable<ArrayList<JBurgRule>>>();

                for ( String op: getOperators() )
                    this.sortedRules.put(op, sortRules(this.unsortedRules.get(op)));
            }

            return this.sortedRules.get(operator);
        }

        private Iterable<ArrayList<JBurgRule>> sortRules( ArrayList<JBurgRule> unsorted_rules)
        {
            //  Find the minumum arity of all n-ary patterns;
            //  any rule with arity >= this limit gets sorted
            //  into the "variable-arity" bucket.
            int arity_requires_variable = Integer.MAX_VALUE;

            for ( JBurgRule rule: unsorted_rules )
                if ( rule.patternMatcher.hasNaryness() )
                    arity_requires_variable = Math.min(arity_requires_variable, rule.patternMatcher.getNominalArity());

            Multimap<Integer, JBurgRule> rules = new Multimap<Integer, JBurgRule>(); 

            for ( JBurgRule rule: unsorted_rules )
            {
                //  All n-ary patterns and any fixed-arity patterns that
                //  overlap with n-ary patterns go into a common annotation;
                //  fixed-arity patterns of arity less than the smallest
                //  n-ary arity can't be confused with an n-ary pattern
                //  and can go in their own annotation.
                Integer key = 
                    rule.patternMatcher.getNominalArity() < arity_requires_variable?
                    rule.patternMatcher.getNominalArity():
                    arity_requires_variable;

                rules.addToSet(key,rule);
            }

            return rules.values();
        }

    }
}