You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@royale.apache.org by ah...@apache.org on 2019/04/05 17:47:25 UTC
[royale-compiler] branch develop updated: JBurgGenerator.java
version 1.10 contributed by Adobe Inc and Tom Harwood. Permission to
relicense granted in
https://lists.apache.org/thread.html/ea55377e78d3124add309044dfd00470a16a52be16b97804ea4fa10c@%3Cdev.royale.apache.org%3E
This is an automated email from the ASF dual-hosted git repository.
aharui pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/royale-compiler.git
The following commit(s) were added to refs/heads/develop by this push:
new b0ddc75 JBurgGenerator.java version 1.10 contributed by Adobe Inc and Tom Harwood. Permission to relicense granted in https://lists.apache.org/thread.html/ea55377e78d3124add309044dfd00470a16a52be16b97804ea4fa10c@%3Cdev.royale.apache.org%3E
b0ddc75 is described below
commit b0ddc75daef307d10d372b8ed36aff145a10b257
Author: Alex Harui <ah...@apache.org>
AuthorDate: Fri Apr 5 10:44:51 2019 -0700
JBurgGenerator.java version 1.10 contributed by Adobe Inc and Tom Harwood. Permission to relicense granted in https://lists.apache.org/thread.html/ea55377e78d3124add309044dfd00470a16a52be16b97804ea4fa10c@%3Cdev.royale.apache.org%3E
-Significant amounts of the file was authored by Tom H. while an employee of Adobe. Consequently Adobe holds the copyright to that material,
-Per Tom Harwood, all other material was authored by him alone and is not subject to an obligation of assignment to or ownership interest of anyone else,
-Tom Harwood. has granted Adobe permission to submit all material in which he holds the copyright to the project under ALv2/per the terms of the Adobe CCLA
---
NOTICE | 5 +-
.../src/main/java/jburg/burg/JBurgGenerator.java | 3759 ++++++++++++++++++++
2 files changed, 3763 insertions(+), 1 deletion(-)
diff --git a/NOTICE b/NOTICE
index ee01330..a7a2fe9 100644
--- a/NOTICE
+++ b/NOTICE
@@ -5,9 +5,12 @@ This product includes software developed at
The Apache Software Foundation (http://www.apache.org/).
The Initial Developer of the Original Code, known as Adobe Flex
-and Adobe ASC 2.0, is Adobe Systems Incorporated (http://www.adobe.com/).
+and Adobe ASC 2.0 and JBurgGenerator.java, is Adobe Systems Incorporated
+(http://www.adobe.com/).
Copyright 2003 - 2012 Adobe Systems Incorporated. All Rights Reserved.
The flex-compiler-oem compiler contains code written by Jeff Dyer at:
Copyright Mountain View Compiler Company (1998-2003).
+Portions of JBurgGenerator.java contains code written by Tom Harwood
+ Copyright Tom Harwood (2003-2008).
diff --git a/compiler-jburg-types/src/main/java/jburg/burg/JBurgGenerator.java b/compiler-jburg-types/src/main/java/jburg/burg/JBurgGenerator.java
new file mode 100644
index 0000000..ac5dfd9
--- /dev/null
+++ b/compiler-jburg-types/src/main/java/jburg/burg/JBurgGenerator.java
@@ -0,0 +1,3759 @@
+/*
+ *
+ * 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)
+ {
+ return String.format("getCostForRule_%h", rule);
+ }
+
+ /**
+ * 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();
+ }
+
+ }
+}