in compiler-jburg-types/src/main/java/jburg/burg/JBurgGenerator.java [2674:3073]
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);
}