source: branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs @ 10418

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

namespace CodeGenerator {
  // code generator for problem class
  public class ProblemCodeGen {
    private const string usings = @"
using System.Collections.Generic;
using System.Linq;
using System;
using System.Text.RegularExpressions;
using System.Diagnostics;
";

    private const string problemTemplate = @"
namespace ?PROBLEMNAME? {
  public sealed class ?IDENT?Problem {
   
   public ?IDENT?Problem() { 
      Initialize();
    }    

    private void Initialize() {
      // the following is the source code from the INIT section of the problem definition 
#region INIT section
?INITSOURCE?
#endregion
    }

    private Tree _t;
    public double Evaluate(Tree _t) {
      this._t = _t;
#region objective function (MINIMIZE / MAXIMIZE section)
?FITNESSFUNCTION?
#endregion
    }
    public bool IsBetter(double a, double b) { 
      return ?MAXIMIZATION? ? a > b : a < b;
    }

// additional code from the problem definition (CODE section)
#region additional code
?ADDITIONALCODE?
#endregion

#region generated source for interpretation
?INTERPRETERSOURCE?
#endregion

#region generated code for the constraints for terminals
?CONSTRAINTSSOURCE?
#endregion
  }

#region class definitions for tree
  public class Tree {
    public int altIdx;
    public Tree[] subtrees;
    protected Tree() {
      // leave subtrees uninitialized
    }
    public Tree(int altIdx, Tree[] subtrees = null) {
      this.altIdx = altIdx;
      this.subtrees = subtrees;
    }
    public int GetSize() {
      if(subtrees==null) return 1;
      else return 1 + subtrees.Sum(t=>t.GetSize());
    }
    public int GetDepth() {
      if(subtrees==null) return 1;
      else return 1 + subtrees.Max(t=>t.GetDepth());
    }
    public virtual void PrintTree(int curState) {
      Console.Write(""{0} "", Grammar.symb[curState]);
      if(subtrees != null) {
        if(subtrees.Length==1) {
          subtrees[0].PrintTree(Grammar.transition[curState][altIdx]);
        } else {
          for(int i=0;i<subtrees.Length;i++) {
            subtrees[i].PrintTree(Grammar.transition[curState][i]);
          }
        }
      }
    }
  }

  ?TERMINALNODECLASSDEFINITIONS?
#endregion

#region helper class for the grammar representation
  public class Grammar {
    public static readonly Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
?TRANSITIONTABLE?
    };
    public static readonly Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
       { -1, 0 }, // terminals
?SUBTREECOUNTTABLE?
    };
    public static readonly string[] symb = new string[] { ?SYMBOLNAMES? };
    
  }  
#endregion
}";


    /// <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 SourceBuilder();
      problemSourceCode.AppendLine(usings);

      GenerateProblemSource(ast, problemSourceCode);
      GenerateSolvers(ast, problemSourceCode);

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

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

    private void GenerateProblemSource(GPDefNode ast, SourceBuilder problemSourceCode) {
      var grammar = CreateGrammarFromAst(ast);
      problemSourceCode
        .AppendLine(problemTemplate)
        .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
        .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
        .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
        .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
        .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
        .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
        .Replace("?TERMINALNODECLASSDEFINITIONS?", GenerateTerminalNodeClassDefinitions(ast.Terminals.OfType<TerminalNode>()))
        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
       ;
    }

    private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
      var grammar = CreateGrammarFromAst(ast);
      // var randomSearchCodeGen = new RandomSearchCodeGen();
      // randomSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
      // var bruteForceSearchCodeGen = new BruteForceCodeGen();
      // bruteForceSearchCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
      var mctsCodeGen = new MonteCarloTreeSearchCodeGen();
      mctsCodeGen.Generate(grammar, ast.Terminals.OfType<TerminalNode>(), ast.FitnessFunctionNode.Maximization, solverSourceCode);
    }

    #region create grammar instance from AST
    // should be refactored so that we can directly query the AST
    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);
    }
    #endregion

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


    // generates helper methods for the attributes of a given terminal node
    private void GenerateConstraintMethods(TerminalNode t, SourceBuilder sb) {
      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 IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
        }
      }
    }
    #endregion

    private string GenerateTerminalNodeClassDefinitions(IEnumerable<TerminalNode> terminals) {
      var sb = new SourceBuilder();

      foreach (var terminal in terminals) {
        GenerateTerminalNodeClassDefinitions(terminal, sb);
      }
      return sb.ToString();
    }

    private void GenerateTerminalNodeClassDefinitions(TerminalNode terminal, SourceBuilder sb) {
      sb.AppendFormat("public class {0}Tree : Tree {{", terminal.Ident).BeginBlock();
      foreach (var att in terminal.FieldDefinitions) {
        sb.AppendFormat("public {0} {1};", att.Type, att.Identifier).AppendLine();
      }
      sb.AppendFormat(" public {0}Tree() : base() {{ }}", terminal.Ident).AppendLine();
      sb.AppendLine(@"
          public override void PrintTree(int curState) {
            Console.Write(""{0} "", Grammar.symb[curState]);");
      foreach (var att in terminal.FieldDefinitions) {
        sb.AppendFormat("Console.Write(\"{{0}} \", {0});", att.Identifier).AppendLine();
      }

      sb.AppendLine("}");

      sb.AppendLine("}");
    }

    private string GenerateInterpreterSource(AttributedGrammar grammar) {
      var sb = new SourceBuilder();
      GenerateInterpreterStart(grammar, sb);

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

    private void GenerateInterpreterStart(AttributedGrammar grammar, SourceBuilder sb) {
      var s = grammar.StartSymbol;
      // create the method which can be called from the fitness function
      if (!s.Attributes.Any())
        sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
      else
        sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();

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

      // 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;
      sb.AppendFormat("{0}(_t, {1});", s.Name, actualParameter).AppendLine();
      sb.AppendLine("}").EndBlock();
    }

    private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
      if (!s.Attributes.Any())
        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
      else
        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();

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

      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();

      if (altsWithSemActions.Length > 1) {
        GenerateSwitchStatement(altsWithSemActions, sb);
      } else {
        int i = 0;
        foreach (var altSymb in altsWithSemActions.Single()) {
          GenerateSourceForAction(i, altSymb, sb);
          if (!(altSymb is SemanticSymbol)) i++;
        }
      }
      sb.Append("}").EndBlock();
    }

    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
      sb.Append("switch(_t.altIdx) {").BeginBlock();
      // generate a case for each alternative
      int altIdx = 0;
      foreach (var alt in alts) {
        sb.AppendFormat("case {0}: {{ ", altIdx).BeginBlock();

        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols)!
        // a 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) {
          GenerateSourceForAction(0, altSymb, sb); // index is always 0 because of the assertion above
        }
        altIdx++;
        sb.AppendLine("break;").Append("}").EndBlock();
      }
      sb.AppendLine("default: throw new System.InvalidOperationException();").Append("}").EndBlock();
    }

    // helper for generating calls to other symbol methods
    private void GenerateSourceForAction(int idx, ISymbol s, SourceBuilder sb) {
      var action = s as SemanticSymbol;
      if (action != null)
        sb.Append(action.Code + ";");
      else if (!s.Attributes.Any())
        sb.AppendFormat("{1}(_t.subtrees[{0}]);", idx, s.Name);
      else sb.AppendFormat("{1}(_t.subtrees[{0}], {2}); ", idx, s.Name, s.GetAttributeString());
      sb.AppendLine();
    }

    private void GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
      // if the terminal symbol has attributes then we must samples values for these attributes
      if (!s.Attributes.Any())
        sb.AppendFormat("private void {0}(Tree _t) {{", s.Name).BeginBlock();
      else
        sb.AppendFormat("private void {0}(Tree _t, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();

      // each field must match a formal parameter, assign a value for each parameter
      int i = 0;
      foreach (var element in s.Attributes) {
        sb.AppendFormat("{0} = (_t as {1}Tree).{0};", element.Name, s.Name).AppendLine();
      }
      sb.Append("}").EndBlock();
    }



    private string GenerateTransitionTable(IGrammar grammar) {
      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
      var sb = new SourceBuilder();

      // state idx = idx of the corresponding symbol in the grammar
      var allSymbols = grammar.Symbols.ToList();
      foreach (var s in grammar.Symbols) {
        var targetStates = new List<int>();
        if (grammar.IsTerminal(s)) {
        } else {
          if (grammar.NumberOfAlternatives(s) > 1) {
            foreach (var alt in grammar.GetAlternatives(s)) {
              // only single-symbol alternatives are supported
              Debug.Assert(alt.Count() == 1);
              targetStates.Add(allSymbols.IndexOf(alt.Single()));
            }
          } else {
            // rule is a sequence of symbols
            var seq = grammar.GetAlternatives(s).Single();
            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
          }
        }

        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");

        var idxOfSourceState = allSymbols.IndexOf(s);
        sb.AppendFormat("// {0}", s).AppendLine();
        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
      }
      return sb.ToString();
    }
    private string GenerateSubtreeCountTable(IGrammar grammar) {
      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
      var sb = new SourceBuilder();

      // state idx = idx of the corresponding symbol in the grammar
      var allSymbols = grammar.Symbols.ToList();
      foreach (var s in grammar.Symbols) {
        int subtreeCount = 0;
        if (grammar.IsTerminal(s)) {
        } else {
          if (grammar.NumberOfAlternatives(s) > 1) {
            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
            subtreeCount = 1;
          } else {
            subtreeCount = grammar.GetAlternative(s, 0).Count();
          }
        }

        sb.AppendFormat("// {0}", s).AppendLine();
        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
      }

      return sb.ToString();
    }

  }
}