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

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeGenerator {
  public class BruteForceCodeGen {

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

    private string solverTemplate = @"
namespace ?PROBLEMNAME? {
  private static class Grammar {
    ?GRAMMARCLASSCODE?
  }
  private sealed class PartiallyProcessedSeq {
    private PartiallyProcessedSeq parent;
    private int alt;
    private IEnumerable<string> remaining;
    public PartiallyProcessedSeq(IEnumerable<string> alternative) {
      this.remaining = alternative;
    }
    public PartiallyProcessedSeq CreateAlternative(int p, IEnumerable<string> alternative) {
      var child = new PartiallyProcessedSeq(alternative.Concat(remaining));
      child.parent = this;
    }
    public bool TryProcessToNextSymbolWithAlternatives(out string symbol) {
      remaining = remaining.SkipWhile(s=>Grammar.NumberOfAlternatives(s)==0);
      if(remaining.Any()) {
        symbol = remaining.First();
        remaining = remaining.Skip(1);
        return true;
      } else {
        symbol = null;
        return false;
      }
      
    }
    public IEnumerable<int> Path {
      get {
        var cur = this;
        var List<int> path = new List<int>();
        while(cur.parent!=null) {
          path.Append(cur.p);
          cur = cur.parent;
        }
        return path.Reverse();
      }
    }
  }
  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) { 
      ?MAXIMIZATION? ? a > b : a < b;
    }

    private IEnumerable<IEnumerator<int>> GeneratePaths() {
      var queue = new Queue<PartiallyProcessedSeq>();
      foreach(var alt in Grammar.GetAlternatives(Grammar.RootSymbol)) 
        queue.Enqueue(new PartiallyProcessedSeq(alt));

      while(queue.Count > 0) {
        var e = queue.Dequeue();
        string ntSöymbol;
        if(e.TryProcessToNextNtSymbol(out ntSymbol)) {
          int i=0;
          foreach(var alt in Grammar.GetAlternatives(symbol)) {
            queue.Enqueue(new e.CreateAlternative(i++, alt));
          }
        } else {
          yield return e.Path;
        }
      }
    }

    ?PATHGENERATORCODE?

    private void Start() {
      // generate possible paths through the grammar and evaluate each of them    
      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
      foreach(var path in GeneratePaths()) {
        currentPath = path;
        var f = Calculate();
        if(IsBetter(f, bestF)) bestF = f;
        Console.WriteLine(""{0}\t{1}"",bestF, f);
      }
    }

    private IEnumerator<int> currentPath;

    public double Calculate() {
      try {
        ?FITNESSFUNCTION?
      } catch(Exception e) {
        throw;
      }
    }

    ?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 to a file for debugging
      using (var stream = new StreamWriter(ast.Name + ".cs")) {
        stream.WriteLine(problemSourceCode.ToString());
      }
    }

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

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

    private string GenerateGrammarClassCode(GPDefNode ast) {
      var sb = new StringBuilder();
      // RootSymbol
      sb.AppendFormat("public static string RootSymbol {{ get {{ return {0}; }} }}", ast.Rules.First().NtSymbol).AppendLine();
      // GetAlternatives
      sb.AppendFormat("public static IEnumerable<IEnumerable<string>> GetAlternatives(string symbol) {{");
      sb.AppendFormat("switch(symbol) {{ ").AppendLine();
      foreach (var ntSymbol in ast.NonTerminals) {
        sb.AppendFormat("case {0}: {{ ").AppendLine();
        var rule = ast.Rules.Single(r => r.NtSymbol == ntSymbol.Ident);
        sb.AppendFormat("return new string[][] {{}}", rule.RuleExpr);
        sb.AppendLine("break;}}");
      }
      foreach (var tSymbol in ast.NonTerminals) {

      }
      sb.AppendFormat(" else {{ throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }}");
      sb.AppendLine("}}");
      sb.AppendFormat("}}").AppendLine();

      // NumberOfAlternatives
      sb.AppendFormat(
        "public static int NumberOfAlternatives(string symbol) {{ return GetAlternatives(symbol).Count(); }}").AppendLine();
      return sb.ToString();
    }

    // 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();
    }


    // generates code for a breath-first-search generating all possible paths through the grammar
    private string GeneratePathGeneratorCode(GPDefNode ast) {
      var sb = new StringBuilder();
      foreach (var s in ast.NonTerminals) {
        sb.Append(GeneratePathGeneratorCode(s));
      }
      foreach (var s in ast.Terminals) {
        sb.Append(GeneratePathGeneratorCode(s));
      }
      return sb.ToString();
    }

    // generates code for a breath-first-search generating all possible paths through the grammar
    private string GeneratePathGeneratorCode(SymbolNode s) {
      var sb = new StringBuilder();

      return sb.ToString();
    }

    private string GenerateInterpreterSource(GPDefNode definition) {
      var sb = new StringBuilder();
      // create a grammar instance based on the AST
      var g = new Grammar(definition.NonTerminals, definition.Terminals, definition.Rules);
      // find formal parameters of root node
      string formalParameter = definition.NonTerminals.Single(nt => nt.Ident == g.RootSymbol).FormalParameters;
      // actual parameter are the same as formalparameter only without type identifier
      var actualParameterEnumerable =
        Util.ExtractFormalParameters(formalParameter).Select(e => e.RefOrOut + " " + e.Identifier);
      string actualParameter = string.Empty;
      // generate a string of actual parameters beginning with: ', a0, a1, ...'
      if (actualParameterEnumerable.Any()) {
        foreach (var e in actualParameterEnumerable) {
          actualParameter += ", " + e;
        }
      }
      // 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}) {{ {0}(currentPath {2}); }}", g.RootSymbol, formalParameter, actualParameter).AppendLine();

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

    private string GenerateTerminalInterpreterMethod(TerminalNode s) {
      var sb = new StringBuilder();
      // if the terminal symbol has attributes then we must create values for these attributes
      if (!s.FormalParameters.Any())
        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
      else
        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);

      // each field must match a formal parameter, assign a value for each parameter
      foreach (var element in s.FieldDefinitions) {
        // read next symbol
        sb.AppendLine("path.MoveNext();");
        sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Identifier, s.Ident).AppendLine(";");
      }
      sb.AppendLine("}");
      return sb.ToString();
    }

    private string GenerateInterpreterMethod(Grammar g, SymbolNode s) {
      var sb = new StringBuilder();
      if (!s.FormalParameters.Any())
        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
      else
        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);
      // generate local definitions
      sb.AppendLine(g.GetLocalDefinitions(s.Ident));

      // read next symbol
      sb.AppendLine("path.MoveNext();");

      // if there are alternatives for this symbol -> choose alternative based on the path
      var alts = g.GetAlternatives(s.Ident);
      if (alts.Count() > 1) {
        int i = 0;
        sb.AppendLine("switch(path.Current) {");
        // generate a case for each alternative
        foreach (var l in alts) {
          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
          foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, i++)) {
            sb.AppendLine(GenerateSourceForAction(e));
          }
          sb.AppendLine("break;").AppendLine("}");
        }
        sb.AppendLine("} else throw new System.InvalidOperationException()").AppendLine();
      } else {
        foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, 0)) {
          sb.AppendLine(GenerateSourceForAction(e));
        }
      }
      sb.AppendLine("}");
      return sb.ToString();
    }

    // helper for generating calls to other symbol methods
    private string GenerateSourceForAction(RuleExprNode e) {
      var action = e as RuleActionNode;
      var call = e as CallSymbolNode;
      if (action != null) {
        return action.SrcCode + ";";
      } else if (call != null) {
        if (!call.ActualParameter.Any())
          return string.Format("{0}(path);", call.Ident);
        else
          return string.Format("{0}(path, {1});", call.Ident, call.ActualParameter);
      } else {
        throw new ArgumentException();
      }
    }
  }
}