source: branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs @ 10115

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using HeuristicLab.Grammars;
using Attribute = HeuristicLab.Grammars.Attribute;

namespace CodeGenerator {
  public class BruteForceCodeGen {

    private string usings = @"
using System.Collections.Generic;
using System.Linq;
using System;
";

    private string solverTemplate = @"
namespace ?PROBLEMNAME? {
  public sealed class ?IDENT?Solver {

    public static void Main(string[] args) {
      var solver = new ?IDENT?Solver();
      solver.Start();
    }

    public ?IDENT?Solver() { 
      Initialize();
    }    

    private void Initialize() {
      ?INITCODE?
    }

    private bool IsBetter(double a, double b) { 
      return ?MAXIMIZATION? ? a > b : a < b;
    }

    private class SearchTree {
      private SearchTree[] subTrees;
      public bool Done { get; private set; }
      private int nextAlternative;

      public SearchTree() {
        Done = false;
      }

      public SearchTree GetSubtree(int i) {
        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
        return subTrees[i];
      }

      public int GetNextAlternative() {
        System.Diagnostics.Debug.Assert(IsAlternativeNode);
        return nextAlternative;
      }

      public bool IsUninitialized {
        get { return subTrees == null; }
      }

      public void SetNumberOfSubtrees(int n) {
        this.subTrees = new SearchTree[n]; 
        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
        nextAlternative = 0;
      }

      public void UpdatePath() {
        System.Diagnostics.Debug.Assert(!Done);
        if (IsUninitialized) { return; }
        Count++;
        if (subTrees.Length == 0) {
          Done = true;
        }
        if (IsAlternativeNode) {
          // update only the active alternative and calculate a new alternative
          subTrees[nextAlternative].UpdatePath();

          do {
            nextAlternative = (nextAlternative + 1) % subTrees.Length;
          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
        } else {
          // for sequenceNodes update all sub-trees
          foreach (var t in subTrees) t.UpdatePath();
        }
        // set node to done if all nodes are non-null and done
        this.Done = true;
        foreach(var t in subTrees) {
          if(t == null || !t.Done) 
            { this.Done = false; break; }
        }        
      }

      public bool IsAlternativeNode { get; set; }
      public bool IsSequenceNode { get; set; }
      public int Count { get; private set; }
    }

    private SearchTree tree;
    private void Start() {
      // start with empty tree
      tree = new SearchTree();
      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
      int n = 0;
      var sw = new System.Diagnostics.Stopwatch();
      sw.Start();
      while (!tree.Done) {

        var f = Calculate();
        // do one more run through the tree to update the path
        tree.UpdatePath();

        n++;
        if (IsBetter(f, bestF)) bestF = f;
        if (n % 100 == 0) {
          sw.Stop();
          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
          sw.Reset();
          sw.Start();
        }
      }
    }

    public double Calculate() {
      ?FITNESSFUNCTION?
    }

    ?ADDITIONALCODE?

    ?INTERPRETERSOURCE?

    ?CONSTRAINTSSOURCE?
  }
}";


    /// <summary>
    /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
    /// </summary>
    /// <param name="ast">An abstract syntax tree for a GPDL file</param>
    public void Generate(GPDefNode ast) {
      var problemSourceCode = new StringBuilder();
      problemSourceCode.AppendLine(usings);

      GenerateProblem(ast, problemSourceCode);

      problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);

      // write the source file to disk
      using (var stream = new StreamWriter(ast.Name + ".cs")) {
        stream.WriteLine(problemSourceCode.ToString());
      }
    }

    private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
      var grammar = CreateGrammarFromAst(ast);
      var problemClassCode =
        solverTemplate
          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
          .Replace("?IDENT?", ast.Name)
          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
          .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
          .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
          ;

      problemSourceCode.AppendLine(problemClassCode).AppendLine();
    }

    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {

      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
      string startSymbolName = ast.Rules.First().NtSymbol;

      // create startSymbol
      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);

      // add all production rules
      foreach (var rule in ast.Rules) {
        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
          g.AddProductionRule(ntSymbol, alt);
        }
        // local initialization code
        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
      }
      return g;
    }

    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
      return (from fieldDef in Util.ExtractParameters(formalParameters)
              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
        ToList();
    }

    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
      foreach (var alt in altNode.Alternatives) {
        yield return GetSequence(alt.Sequence, allSymbols);
      }
    }

    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
      var l = new List<ISymbol>();
      foreach (var node in sequence) {
        var callSymbolNode = node as CallSymbolNode;
        var actionNode = node as RuleActionNode;
        if (callSymbolNode != null) {
          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
          // create a new symbol with actual parameters
          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
        } else if (actionNode != null) {
          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
        }
      }
      return new Sequence(l);
    }

    // produces helper methods for the attributes of all terminal nodes
    private string GenerateConstraintMethods(List<SymbolNode> symbols) {
      var sb = new StringBuilder();
      var terminals = symbols.OfType<TerminalNode>();
      foreach (var t in terminals) {
        sb.AppendLine(GenerateConstraintMethods(t));
      }
      return sb.ToString();
    }

    // generates helper methods for the attributes of a given terminal node
    private string GenerateConstraintMethods(TerminalNode t) {
      var sb = new StringBuilder();
      foreach (var c in t.Constraints) {
        var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
        if (c.Type == ConstraintNodeType.Range) {
          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
        } else if (c.Type == ConstraintNodeType.Set) {
          sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
        }
        sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
      }
      return sb.ToString();
    }

    private string GenerateInterpreterSource(AttributedGrammar grammar) {
      var sb = new StringBuilder();


      // get formal parameters of start symbol
      var attr = grammar.StartSymbol.Attributes;

      var formalParameter = grammar.StartSymbol.GetAttributeString();
      // actual parameter are the same as formalparameter only without type identifier
      string actualParameter;
      if (attr.Any())
        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
      else
        actualParameter = string.Empty;

      // generate entry method for evaluation. This is called from the min/max function
      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
      sb.AppendLine("}");

      // generate methods for all nonterminals and terminals using the grammar instance
      foreach (var s in grammar.NonTerminalSymbols) {
        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
      }
      foreach (var s in grammar.TerminalSymbols) {
        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
      }
      return sb.ToString();
    }

    private string GenerateTerminalInterpreterMethod(ISymbol s) {
      var sb = new StringBuilder();
      // if the terminal symbol has attributes then we must create values for these attributes
      if (!s.Attributes.Any())
        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
      else
        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());

      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
      // each field must match a formal parameter, assign a value for each parameter
      int i = 0;
      foreach (var element in s.Attributes) {
        // read next symbol
        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
      }
      sb.AppendLine("}");
      return sb.ToString();
    }

    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
      var sb = new StringBuilder();
      if (!s.Attributes.Any())
        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
      else
        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());

      // generate local definitions
      sb.AppendLine(g.GetLocalDefinitions(s));



      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
        .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();

      if (altsWithSemActions.Length > 1) {
        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);

        int i = 0;
        sb.AppendLine("switch(tree.GetNextAlternative()) {");
        // generate a case for each alternative
        foreach (var alt in altsWithSemActions) {
          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
          sb.AppendLine("SearchTree subtree = null; ");

          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
          // handling multiple non-terminals here would require a change in the structure of the search tree
          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
          foreach (var altSymb in alt) {
            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
            sb.AppendLine(GenerateSourceForAction(altSymb));
          }
          i++;
          sb.AppendLine("break;").AppendLine("}");
        }
        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
      } else {
        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
        int j = 0;
        sb.AppendLine("SearchTree subtree = null; ");
        foreach (var altSymb in altsWithSemActions.Single()) {
          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
          sb.AppendLine(GenerateSourceForAction(altSymb));
        }
      }
      sb.AppendLine("}");
      return sb.ToString();
    }

    // helper for generating calls to other symbol methods
    private string GenerateSourceForAction(ISymbol s) {
      var action = s as SemanticSymbol;
      if (action != null) {
        return action.Code + ";";
      } else {
        if (!s.Attributes.Any())
          return string.Format("{0}(subtree);", s.Name);
        else
          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
      }
    }
  }
}