Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10067


Ignore:
Timestamp:
10/18/13 21:33:56 (9 years ago)
Author:
gkronber
Message:

#2026 worked on brute force solver for GPDL problems.

Location:
branches/HeuristicLab.Problems.GPDL
Files:
1 added
16 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

    r10062 r10067  
    11using System;
    22using System.Collections.Generic;
     3using System.Diagnostics;
    34using System.IO;
    45using System.Linq;
    56using System.Text;
    67using System.Threading.Tasks;
     8using HeuristicLab.Grammars;
     9using Attribute = HeuristicLab.Grammars.Attribute;
    710
    811namespace CodeGenerator {
     
    1720    private string solverTemplate = @"
    1821namespace ?PROBLEMNAME? {
    19   private static class Grammar {
     22  internal static class Grammar {
    2023    ?GRAMMARCLASSCODE?
    2124  }
    22   private sealed class PartiallyProcessedSeq {
    23     private PartiallyProcessedSeq parent;
    24     private int alt;
     25  internal sealed class PartiallyProcessedSeq {
    2526    private IEnumerable<string> remaining;
    26     public PartiallyProcessedSeq(IEnumerable<string> alternative) {
    27       this.remaining = alternative;
    28     }
    29     public PartiallyProcessedSeq CreateAlternative(int p, IEnumerable<string> alternative) {
    30       var child = new PartiallyProcessedSeq(alternative.Concat(remaining));
    31       child.parent = this;
    32     }
    33     public bool TryProcessToNextSymbolWithAlternatives(out string symbol) {
    34       remaining = remaining.SkipWhile(s=>Grammar.NumberOfAlternatives(s)==0);
    35       if(remaining.Any()) {
    36         symbol = remaining.First();
    37         remaining = remaining.Skip(1);
    38         return true;
    39       } else {
    40         symbol = null;
    41         return false;
    42       }
    43      
     27    private IEnumerable<int> path;
     28    public PartiallyProcessedSeq(IEnumerable<string> remaining) : this (Enumerable.Empty<int>(), remaining) {
     29    }
     30    public PartiallyProcessedSeq(IEnumerable<int> path, IEnumerable<string> remaining) {
     31      this.path = path;
     32      this.remaining = remaining;
     33    }
     34
     35    public bool MoveNext() {
     36      if(!remaining.Any()) return false;
     37      else remaining = remaining.Skip(1);
     38      return true;
     39    }
     40
     41    public string Current {
     42      get {
     43        return remaining.FirstOrDefault();
     44      }
    4445    }
    4546    public IEnumerable<int> Path {
    4647      get {
    47         var cur = this;
    48         var List<int> path = new List<int>();
    49         while(cur.parent!=null) {
    50           path.Append(cur.p);
    51           cur = cur.parent;
    52         }
    53         return path.Reverse();
    54       }
    55     }
     48        return path;
     49      }
     50    }
     51    public IEnumerable<string> Remaining {
     52      get {
     53        return remaining;
     54      }
     55    }
     56    public override string ToString() {
     57      return path.Aggregate("""", (str, p) => str + "" "" + p) + "" >> "" +
     58             remaining.Aggregate("""", (str, r) => str + "" "" + r);
     59    }
     60
    5661  }
    5762  public sealed class ?IDENT?Solver {
     
    7176
    7277    private bool IsBetter(double a, double b) {
    73       ?MAXIMIZATION? ? a > b : a < b;
    74     }
    75 
    76     private IEnumerable<IEnumerator<int>> GeneratePaths() {
     78      return ?MAXIMIZATION? ? a > b : a < b;
     79    }
     80
     81    #region path generator (BFS in the grammar to generate solutions)
     82    ?PATHGENERATORCODE?
     83    #endregion
     84
     85    private IEnumerable<IEnumerable<int>> GeneratePaths() {
    7786      var queue = new Queue<PartiallyProcessedSeq>();
    78       foreach(var alt in Grammar.GetAlternatives(Grammar.RootSymbol))
    79         queue.Enqueue(new PartiallyProcessedSeq(alt));
    80 
    81       while(queue.Count > 0) {
     87      queue.Enqueue(new PartiallyProcessedSeq(new string[] { Grammar.RootSymbol }));
     88
     89      while (queue.Count > 0) {
    8290        var e = queue.Dequeue();
    83         string ntSöymbol;
    84         if(e.TryProcessToNextNtSymbol(out ntSymbol)) {
    85           int i=0;
    86           foreach(var alt in Grammar.GetAlternatives(symbol)) {
    87             queue.Enqueue(new e.CreateAlternative(i++, alt));
     91        var symb = e.Current; // the next symbol to generate paths for
     92        // Console.WriteLine(""Out: "" + e);
     93
     94        var lastSymbol = !e.MoveNext();
     95
     96        if (Grammar.IsTerminal(symb)) {
     97          // generate all paths for the terminal
     98          if (lastSymbol) {
     99            var pathsForSymb = GeneratePathsFor(symb);
     100            if (pathsForSymb.Any()) {
     101              foreach (var path in GeneratePathsFor(symb)) {
     102                yield return e.Path.Concat(path);
     103              }
     104            } else {
     105              yield return e.Path;
     106            }
     107          } else {
     108            var paths = GeneratePathsFor(symb);
     109            if(!paths.Any() || paths.Count() == 1) {
     110              yield return e.Path;
     111            } else {
     112              foreach (var path in paths) {
     113                var eAlt = new PartiallyProcessedSeq(e.Path.Concat(path), e.Remaining);
     114                queue.Enqueue(eAlt);
     115                // Console.WriteLine(""In: "" + eAlt);
     116              }
     117            }
    88118          }
    89119        } else {
    90           yield return e.Path;
    91         }
    92       }
    93     }
    94 
    95     ?PATHGENERATORCODE?
     120          // non-terminal -> generate alternatives if necessary
     121          var alts = Grammar.GetAlternatives(symb);
     122          if (alts.Count() == 1) {
     123              var eAlt = new PartiallyProcessedSeq(e.Path, alts.Single().Concat(e.Remaining));
     124              queue.Enqueue(eAlt);
     125              // Console.WriteLine(""In: "" + eAlt);
     126          } else {
     127            int i = 0;
     128            foreach (var alt in alts) {
     129              var eAlt = new PartiallyProcessedSeq(e.Path.Concat(new int[] { i++ }), alt.Concat(e.Remaining));
     130              queue.Enqueue(eAlt);
     131              // Console.WriteLine(""In: "" + eAlt);
     132            }
     133          }
     134        }
     135      }
     136    }
    96137
    97138    private void Start() {
    98139      // generate possible paths through the grammar and evaluate each of them   
    99140      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
     141      int n = 0;
    100142      foreach(var path in GeneratePaths()) {
     143        var length = path.Count();
    101144        currentPath = path;
    102145        var f = Calculate();
     146        n++;
    103147        if(IsBetter(f, bestF)) bestF = f;
    104         Console.WriteLine(""{0}\t{1}"",bestF, f);
    105       }
    106     }
    107 
    108     private IEnumerator<int> currentPath;
     148        if (n%1000 == 0) Console.WriteLine(""{0}\t{1}\t{2}\t{3}"",n, length, bestF, f);
     149      }
     150    }
     151
     152    private IEnumerable<int> currentPath;
    109153
    110154    public double Calculate() {
    111       try {
    112         ?FITNESSFUNCTION?
    113       } catch(Exception e) {
    114         throw;
    115       }
     155      ?FITNESSFUNCTION?
    116156    }
    117157
     
    137177      problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
    138178
    139       // write to a file for debugging
     179      // write the source file to disk
    140180      using (var stream = new StreamWriter(ast.Name + ".cs")) {
    141181        stream.WriteLine(problemSourceCode.ToString());
     
    144184
    145185    private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
     186      var grammar = CreateGrammarFromAst(ast);
    146187      var problemClassCode =
    147188        solverTemplate
    148           .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString())
    149           .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(ast))
     189          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
     190          .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(grammar))
    150191          .Replace("?IDENT?", ast.Name)
    151192          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
    152           .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(ast))
     193          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
    153194          .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
    154195          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
     
    160201    }
    161202
    162     private string GenerateGrammarClassCode(GPDefNode ast) {
     203    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
     204      string startSymbolName = ast.Rules.First().NtSymbol;
     205      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
     206      // create startSymbol
     207      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
     208      foreach (var rule in ast.Rules) {
     209        // create nt-symbol
     210        var ntSymbolName = rule.NtSymbol;
     211        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
     212        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
     213        var ntSymbol = new Symbol(ntSymbolName, attributes);
     214        foreach (var alt in GetAlternatives(rule.Alternatives)) {
     215          g.AddProductionRule(ntSymbol, alt);
     216        }
     217        // local initialization code
     218        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
     219      }
     220      return g;
     221    }
     222
     223    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
     224      return (from fieldDef in Util.ExtractParameters(formalParameters)
     225              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
     226        ToList();
     227    }
     228
     229    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
     230      foreach (var alt in altNode.Alternatives) {
     231        yield return GetSequence(alt.Sequence);
     232      }
     233    }
     234
     235    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
     236      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
     237      var l = new List<ISymbol>();
     238      foreach (var node in sequence) {
     239        var callSymbolNode = node as CallSymbolNode;
     240        var actionNode = node as RuleActionNode;
     241        if (callSymbolNode != null) {
     242          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
     243        } else if (actionNode != null) {
     244          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
     245        }
     246      }
     247      return new Sequence(l);
     248    }
     249
     250
     251    private string GenerateGrammarClassCode(IGrammar grammar) {
    163252      var sb = new StringBuilder();
    164253      // RootSymbol
    165       sb.AppendFormat("public static string RootSymbol {{ get {{ return {0}; }} }}", ast.Rules.First().NtSymbol).AppendLine();
     254      sb.AppendFormat("public static string RootSymbol {{ get {{ return \"{0}\"; }} }}", grammar.StartSymbol.Name).AppendLine();
     255      sb.AppendLine("public static HashSet<string> terminalSymbols = new HashSet<string>() {");
     256      sb.AppendFormat("{0}", grammar.TerminalSymbols.Aggregate("", (str, symb) => str + "\"" + symb.Name + "\", "));
     257      sb.AppendLine("};");
    166258      // GetAlternatives
    167259      sb.AppendFormat("public static IEnumerable<IEnumerable<string>> GetAlternatives(string symbol) {{");
    168260      sb.AppendFormat("switch(symbol) {{ ").AppendLine();
    169       foreach (var ntSymbol in ast.NonTerminals) {
    170         sb.AppendFormat("case {0}: {{ ").AppendLine();
    171         var rule = ast.Rules.Single(r => r.NtSymbol == ntSymbol.Ident);
    172         sb.AppendFormat("return new string[][] {{}}", rule.RuleExpr);
    173         sb.AppendLine("break;}}");
    174       }
    175       foreach (var tSymbol in ast.NonTerminals) {
    176 
    177       }
    178       sb.AppendFormat(" else {{ throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }}");
    179       sb.AppendLine("}}");
    180       sb.AppendFormat("}}").AppendLine();
    181 
     261      foreach (var ntSymbol in grammar.NonTerminalSymbols) {
     262        sb.AppendFormat("case \"{0}\": {{ ", ntSymbol.Name).AppendLine();
     263        sb.Append("return new string[][] { ").AppendLine();
     264        foreach (var alt in grammar.GetAlternatives(ntSymbol)) {
     265          sb.Append("new string[] { ")
     266            .Append(alt.Skip(1).Aggregate("\"" + alt.First().Name + "\"", (str, symb) => str + ", \"" + symb.Name + "\""))
     267            .AppendLine("},");
     268        }
     269        sb.Append("};");
     270        sb.AppendLine("}");
     271      }
     272      sb.AppendLine(" default: { throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }");
     273      sb.AppendLine("}");
     274      sb.AppendLine("}");
     275
     276      sb.AppendLine("public static bool IsTerminal(string symbol) {");
     277      sb.AppendFormat("return terminalSymbols.Contains(symbol);");
     278      sb.AppendLine("}");
    182279      // NumberOfAlternatives
    183       sb.AppendFormat(
    184         "public static int NumberOfAlternatives(string symbol) {{ return GetAlternatives(symbol).Count(); }}").AppendLine();
    185       return sb.ToString();
    186     }
     280      sb.AppendLine(
     281        "public static int NumberOfAlternatives(string symbol) { return GetAlternatives(symbol).Count(); }");
     282      return sb.ToString();
     283    }
     284
    187285
    188286    // produces helper methods for the attributes of all terminal nodes
     
    216314    private string GeneratePathGeneratorCode(GPDefNode ast) {
    217315      var sb = new StringBuilder();
    218       foreach (var s in ast.NonTerminals) {
     316      foreach (var s in ast.NonTerminals.OfType<NonTerminalNode>()) {
    219317        sb.Append(GeneratePathGeneratorCode(s));
    220318      }
    221       foreach (var s in ast.Terminals) {
    222         sb.Append(GeneratePathGeneratorCode(s));
    223       }
    224       return sb.ToString();
    225     }
    226 
    227     // generates code for a breath-first-search generating all possible paths through the grammar
    228     private string GeneratePathGeneratorCode(SymbolNode s) {
    229       var sb = new StringBuilder();
    230 
    231       return sb.ToString();
    232     }
    233 
    234     private string GenerateInterpreterSource(GPDefNode definition) {
    235       var sb = new StringBuilder();
    236       // create a grammar instance based on the AST
    237       var g = new Grammar(definition.NonTerminals, definition.Terminals, definition.Rules);
     319
     320      sb.Append(GeneratePathGeneratorCode(ast.Terminals.OfType<TerminalNode>()));
     321      return sb.ToString();
     322    }
     323
     324    private string GeneratePathGeneratorCode(NonTerminalNode s) {
     325      var sb = new StringBuilder();
     326
     327      return sb.ToString();
     328    }
     329
     330    // generates a method for the terminal that returns all an IEnumerable of int[] representing each possible combination of values for that terminal
     331    private string GeneratePathGeneratorCode(IEnumerable<TerminalNode> terminals) {
     332      var sb = new StringBuilder();
     333      sb.AppendLine("private IEnumerable<IEnumerable<int>> GeneratePathsFor(string tSymbol) {");
     334      sb.AppendLine("switch(tSymbol) {");
     335      foreach (var t in terminals) {
     336        sb.AppendFormat("case \"{0}\": {{", t.Ident).AppendLine();
     337        if (t.FieldDefinitions.Any()) {
     338          int i = 0;
     339          // open for loop for each field
     340          foreach (var f in t.FieldDefinitions) {
     341            sb.AppendFormat("for(int i{0}=0; i{0} < GetAllowed{1}_{2}().Length; i{0}++) {{", i++, t.Ident, f.Identifier)
     342              .
     343              AppendLine();
     344          }
     345          sb.AppendFormat("yield return new int[] {{ {0} }};",
     346                          Enumerable.Range(0, i).Select(ii => "i" + ii + ", ").Aggregate((str, e) => str + e));
     347          // close braces
     348          while (i-- > 0) {
     349            sb.AppendLine("}");
     350          }
     351          sb.AppendLine("break;");
     352        } else {
     353          sb.AppendLine("yield return Enumerable.Empty<int>();");
     354          sb.AppendLine("break;");
     355        }
     356        sb.AppendLine("}");
     357      }
     358      sb.AppendLine("} }");
     359      return sb.ToString();
     360    }
     361
     362    private string GenerateInterpreterSource(AttributedGrammar grammar) {
     363      var sb = new StringBuilder();
     364
     365
    238366      // find formal parameters of root node
    239       string formalParameter = definition.NonTerminals.Single(nt => nt.Ident == g.RootSymbol).FormalParameters;
     367      var attr = grammar.StartSymbol.Attributes;
     368
     369      var formalParameter = grammar.StartSymbol.GetAttributeString();
    240370      // actual parameter are the same as formalparameter only without type identifier
    241       var actualParameterEnumerable =
    242         Util.ExtractFormalParameters(formalParameter).Select(e => e.RefOrOut + " " + e.Identifier);
    243       string actualParameter = string.Empty;
    244       // generate a string of actual parameters beginning with: ', a0, a1, ...'
    245       if (actualParameterEnumerable.Any()) {
    246         foreach (var e in actualParameterEnumerable) {
    247           actualParameter += ", " + e;
    248         }
    249       }
     371      string actualParameter;
     372      if (attr.Any())
     373        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
     374      else
     375        actualParameter = string.Empty;
     376
    250377      // generate entry method for evaluation. This is called from the min/max function
    251378      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
    252       sb.AppendFormat("void {0}({1}) {{ {0}(currentPath {2}); }}", g.RootSymbol, formalParameter, actualParameter).AppendLine();
     379      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
     380      sb.AppendLine(" var path = currentPath.GetEnumerator();");
     381      sb.AppendFormat("{0}(path, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
     382      sb.AppendLine("if(path.MoveNext()) throw new InvalidOperationException(); // assert that the full path has been processed");
     383      sb.AppendLine("}");
    253384
    254385      // generate methods for all nonterminals and terminals using the grammar instance
    255       foreach (var s in definition.NonTerminals) {
    256         sb.AppendLine(GenerateInterpreterMethod(g, s));
    257       }
    258       foreach (var s in definition.Terminals) {
    259         sb.AppendLine(GenerateTerminalInterpreterMethod((TerminalNode)s));
    260       }
    261       return sb.ToString();
    262     }
    263 
    264     private string GenerateTerminalInterpreterMethod(TerminalNode s) {
     386      foreach (var s in grammar.NonTerminalSymbols) {
     387        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
     388      }
     389      foreach (var s in grammar.TerminalSymbols) {
     390        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
     391      }
     392      return sb.ToString();
     393    }
     394
     395    private string GenerateTerminalInterpreterMethod(ISymbol s) {
    265396      var sb = new StringBuilder();
    266397      // if the terminal symbol has attributes then we must create values for these attributes
    267       if (!s.FormalParameters.Any())
    268         sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
     398      if (!s.Attributes.Any())
     399        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
    269400      else
    270         sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);
     401        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
    271402
    272403      // each field must match a formal parameter, assign a value for each parameter
    273       foreach (var element in s.FieldDefinitions) {
     404      foreach (var element in s.Attributes) {
    274405        // read next symbol
    275406        sb.AppendLine("path.MoveNext();");
    276         sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Identifier, s.Ident).AppendLine(";");
    277       }
    278       sb.AppendLine("}");
    279       return sb.ToString();
    280     }
    281 
    282     private string GenerateInterpreterMethod(Grammar g, SymbolNode s) {
    283       var sb = new StringBuilder();
    284       if (!s.FormalParameters.Any())
    285         sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Ident);
     407        sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Name, s.Name).AppendLine(";");
     408      }
     409      sb.AppendLine("}");
     410      return sb.ToString();
     411    }
     412
     413    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
     414      var sb = new StringBuilder();
     415      if (!s.Attributes.Any())
     416        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
    286417      else
    287         sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Ident, s.FormalParameters);
     418        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
    288419      // generate local definitions
    289       sb.AppendLine(g.GetLocalDefinitions(s.Ident));
    290 
    291       // read next symbol
    292       sb.AppendLine("path.MoveNext();");
     420      sb.AppendLine(g.GetLocalDefinitions(s));
     421
    293422
    294423      // if there are alternatives for this symbol -> choose alternative based on the path
    295       var alts = g.GetAlternatives(s.Ident);
     424      var alts = g.GetAlternatives(s);
    296425      if (alts.Count() > 1) {
     426        // read next symbol
     427        sb.AppendLine("path.MoveNext();");
    297428        int i = 0;
    298429        sb.AppendLine("switch(path.Current) {");
     
    300431        foreach (var l in alts) {
    301432          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
    302           foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, i++)) {
    303             sb.AppendLine(GenerateSourceForAction(e));
     433          foreach (var altS in g.GetAlternativeWithSemanticActions(s, i++)) {
     434            sb.AppendLine(GenerateSourceForAction(altS));
    304435          }
    305436          sb.AppendLine("break;").AppendLine("}");
    306437        }
    307         sb.AppendLine("} else throw new System.InvalidOperationException()").AppendLine();
     438        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
    308439      } else {
    309         foreach (var e in g.GetSequenceWithSemanticActions(s.Ident, 0)) {
    310           sb.AppendLine(GenerateSourceForAction(e));
     440        foreach (var altS in g.GetAlternativeWithSemanticActions(s, 0)) {
     441          sb.AppendLine(GenerateSourceForAction(altS));
    311442        }
    312443      }
     
    316447
    317448    // helper for generating calls to other symbol methods
    318     private string GenerateSourceForAction(RuleExprNode e) {
    319       var action = e as RuleActionNode;
    320       var call = e as CallSymbolNode;
     449    private string GenerateSourceForAction(ISymbol s) {
     450      var action = s as SemanticSymbol;
    321451      if (action != null) {
    322         return action.SrcCode + ";";
    323       } else if (call != null) {
    324         if (!call.ActualParameter.Any())
    325           return string.Format("{0}(path);", call.Ident);
     452        return action.Code + ";";
     453      } else {
     454        if (!s.Attributes.Any())
     455          return string.Format("{0}(path);", s.Name);
    326456        else
    327           return string.Format("{0}(path, {1});", call.Ident, call.ActualParameter);
    328       } else {
    329         throw new ArgumentException();
     457          return string.Format("{0}(path, {1});", s.Name, s.GetAttributeString());
    330458      }
    331459    }
  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj

    r10062 r10067  
    3232  </PropertyGroup>
    3333  <ItemGroup>
     34    <Reference Include="System" />
    3435    <Reference Include="System.Core" />
    3536  </ItemGroup>
     
    3940  </ItemGroup>
    4041  <ItemGroup>
     42    <ProjectReference Include="..\HeuristicLab.Grammars\3.3\HeuristicLab.Grammars-3.3.csproj">
     43      <Project>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</Project>
     44      <Name>HeuristicLab.Grammars-3.3</Name>
     45    </ProjectReference>
    4146    <ProjectReference Include="..\HeuristicLab.Problems.GPDL\3.4\HeuristicLab.Problems.GPDL-3.4.csproj">
    4247      <Project>{E4EE5AFB-D552-447B-8A16-6CBE7938AF32}</Project>
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Attribute.cs

    r10063 r10067  
    2323
    2424namespace HeuristicLab.Grammars {
     25  public sealed class AttributeType {
     26    public static readonly AttributeType In = new AttributeType("");
     27    public static readonly AttributeType Out = new AttributeType("out");
     28    public static readonly AttributeType Ref = new AttributeType("ref");
     29    private string attributeType;
     30    private AttributeType(string attributeType) {
     31      this.attributeType = attributeType;
     32    }
     33
     34    public static AttributeType Parse(string attributeType) {
     35      if (string.IsNullOrEmpty(attributeType)) return In;
     36      else if (attributeType == "ref") return Ref;
     37      else if (attributeType == "out") return Out;
     38      else throw new ArgumentException("Unknown attribute type string.", attributeType);
     39    }
     40
     41    public override string ToString() {
     42      return attributeType;
     43    }
     44  };
     45
    2546  public class Attribute : IAttribute {
    2647    public AttributeType AttributeType { get; private set; }
    2748    public string Type { get; private set; }
    2849    public string Name { get; private set; }
     50
     51    public Attribute(string name, string type)
     52      : this(name, type, AttributeType.In) {
     53    }
     54
     55    public Attribute(string name, string type, AttributeType attributeType) {
     56      this.Name = name;
     57      this.Type = type;
     58      this.AttributeType = attributeType;
     59    }
     60
     61    public override string ToString() {
     62      return AttributeType + " " + Type + " " + Name;
     63    }
    2964  }
    3065}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/AttributedGrammar.cs

    r10051 r10067  
    2424using System.Diagnostics;
    2525using System.Linq;
    26 using System.Text.RegularExpressions;
    2726
    2827namespace HeuristicLab.Grammars {
    2928  public class AttributedGrammar : Grammar {
     29    private Dictionary<ISymbol, string> localDefinitions = new Dictionary<ISymbol, string>();
     30    private Dictionary<ISymbol, IList<Sequence>> alternatives = new Dictionary<ISymbol, IList<Sequence>>();
     31
    3032    public AttributedGrammar(ISymbol startSymbol)
    3133      : base(startSymbol) {
     
    3436    }
    3537
    36     private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*(?<formPar>\<\w+\>)+\s*->\s*(?<alternative>\w+\s*(?<actPar>\<\w+\>)+(?:\s+\w+\s*(?<actPar>\<\w+\>)+)*)(?:\s*\|\s*(?<alternative>\w+\s*(?<formPar>\<\w+\>)+(?:\s+\w+\s*(?<formPar>\<\w+\>)+)*))*");
    37     private static Regex empty = new Regex(@"^\s*$");
    38     public static Grammar FromString(string gStr) {
    39       var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
    40       lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
     38    public IEnumerable<Sequence> GetAlternativesWithSemanticActions(ISymbol ntSymbol) {
     39      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
     40      return alternatives[ntSymbol];
     41    }
     42    public Sequence GetAlternativeWithSemanticActions(ISymbol ntSymbol, int index) {
     43      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
     44      return alternatives[ntSymbol][index];
     45    }
    4146
    42       // first line is the rule for the start-symbol
    43       var m = ruleExpr.Match(lines.First());
    44       var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    45      
    46       var g = new Grammar(startSymbol);
    47       foreach (var alt in m.Groups["alternative"].Captures) {
    48         g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
     47    public override void AddProductionRule(ISymbol ntSymbol, Sequence production) {
     48      base.AddProductionRule(ntSymbol, new Sequence(production.Where(symb => !(symb is SemanticSymbol)).ToList()));
     49
     50      IList<Sequence> list;
     51      if (!alternatives.TryGetValue(ntSymbol, out list)) {
     52        list = new List<Sequence>();
     53        alternatives.Add(ntSymbol, list);
    4954      }
    50       foreach (var line in lines.Skip(1)) {
    51         m = ruleExpr.Match(line);
    52         var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    53         foreach (var alt in m.Groups["alternative"].Captures) {
    54           g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
    55         }
    56       }
     55      // make sure that there is not equivalent production registered already
     56      Debug.Assert(!list.Any(s => s.SequenceEqual(production)));
    5757
    58       return g;
     58      list.Add(production);
    5959    }
     60
     61    public void AddLocalDefinitions(ISymbol ntSymbol, string localDefCode) {
     62      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
     63      Debug.Assert(!localDefinitions.ContainsKey(ntSymbol));
     64
     65      localDefinitions.Add(ntSymbol, localDefCode);
     66    }
     67    public string GetLocalDefinitions(ISymbol ntSymbol) {
     68      string code;
     69      if (localDefinitions.TryGetValue(ntSymbol, out code)) return code;
     70      else return string.Empty;
     71    }
     72
     73
     74
     75    //private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*(?<formPar>\<\w+\>)+\s*->\s*(?<alternative>\w+\s*(?<actPar>\<\w+\>)+(?:\s+\w+\s*(?<actPar>\<\w+\>)+)*)(?:\s*\|\s*(?<alternative>\w+\s*(?<formPar>\<\w+\>)+(?:\s+\w+\s*(?<formPar>\<\w+\>)+)*))*");
     76    //private static Regex empty = new Regex(@"^\s*$");
     77    //public static Grammar FromString(string gStr) {
     78    //  var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
     79    //  lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
     80
     81    //  // first line is the rule for the start-symbol
     82    //  var m = ruleExpr.Match(lines.First());
     83    //  var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
     84
     85    //  var g = new Grammar(startSymbol);
     86    //  foreach (var alt in m.Groups["alternative"].Captures) {
     87    //    g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
     88    //  }
     89    //  foreach (var line in lines.Skip(1)) {
     90    //    m = ruleExpr.Match(line);
     91    //    var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
     92    //    foreach (var alt in m.Groups["alternative"].Captures) {
     93    //      g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
     94    //    }
     95    //  }
     96
     97    //  return g;
     98    //}
    6099  }
    61100}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

    r10051 r10067  
    5454    }
    5555
    56     public void AddProductionRule(ISymbol ntSymbol, Sequence production) {
     56    public virtual void AddProductionRule(ISymbol ntSymbol, Sequence production) {
    5757      Debug.Assert(ntSymbol != EmptySymbol);
    5858
     
    9696      var g = new Grammar(startSymbol);
    9797      foreach (var alt in m.Groups["alternative"].Captures) {
    98         g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
     98        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
    9999      }
    100100      foreach (var line in lines.Skip(1)) {
     
    102102        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    103103        foreach (var alt in m.Groups["alternative"].Captures) {
    104           g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
     104          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
    105105        }
    106106      }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj

    r10063 r10067  
    105105    <Compile Include="AttributedGrammar.cs" />
    106106    <Compile Include="Attribute.cs" />
     107    <Compile Include="SemanticSymbol.cs" />
    107108    <Compile Include="Sequence.cs" />
    108109    <Compile Include="Test.cs" />
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttribute.cs

    r10051 r10067  
    2020#endregion
    2121
     22using System;
     23
    2224namespace HeuristicLab.Grammars {
    23   public enum AttributeType { In, Out, Ref };
     25
    2426  public interface IAttribute {
    2527    AttributeType AttributeType { get; }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/ISymbol.cs

    r10051 r10067  
    2020#endregion
    2121
     22using System.Collections.Generic;
     23
    2224namespace HeuristicLab.Grammars {
    2325  public interface ISymbol {
    2426    string Name { get; }
    25     IAttribute Attribute { get; }
     27    IEnumerable<IAttribute> Attributes { get; }
     28    string GetAttributeString();
    2629  }
    2730}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Language.cs

    r10051 r10067  
    3131  public class Language : IEnumerable<IEnumerable<string>> {
    3232    private class PartiallyProcessedSequence {
    33       private Sequence terminalSeq;
     33      private List<ISymbol> terminalSeq;
    3434      private Sequence remainingSeq;
    3535      private IGrammar grammar;
     
    3838      private PartiallyProcessedSequence(PartiallyProcessedSequence parent) {
    3939        this.parent = parent;
    40         this.terminalSeq = new Sequence();
     40        this.terminalSeq = new List<ISymbol>();
    4141      }
    4242
    4343      public PartiallyProcessedSequence(Sequence seq, IGrammar g) {
    44         this.terminalSeq = new Sequence();
     44        this.terminalSeq = new List<ISymbol>();
    4545        this.remainingSeq = seq;
    4646        this.grammar = g;
     
    5959          ntSymbol = enumerator.Current;
    6060
    61           remainingSeq = new Sequence(remainingSeq.Skip(i + 1));
     61          remainingSeq = new Sequence(remainingSeq.Skip(i + 1).ToList());
    6262          return true;
    6363        }
     
    6666        var p = new PartiallyProcessedSequence(this);
    6767        p.grammar = grammar;
    68         p.remainingSeq = new Sequence(seq.Concat(remainingSeq));
     68        p.remainingSeq = new Sequence(seq.Concat(remainingSeq).ToList());
    6969        return p;
    7070      }
    71       public Sequence GetSequence() {
     71      public IList<ISymbol> GetSequence() {
    7272        if (parent == null) return terminalSeq;
    7373        else {
    74           return new Sequence(parent.GetSequence().Concat(terminalSeq));
     74          return new Sequence(parent.GetSequence().Concat(terminalSeq).ToList());
    7575        }
    7676      }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Sequence.cs

    r10063 r10067  
    2121
    2222using System.Collections.Generic;
     23using System.Collections.ObjectModel;
    2324using System.Linq;
    2425using System.Text;
    2526
    2627namespace HeuristicLab.Grammars {
    27   public class Sequence : List<ISymbol> {
    28     public Sequence()
    29       : base() {
    30     }
    31 
    32     public Sequence(IEnumerable<ISymbol> seq)
    33       : base() {
    34       this.AddRange(seq);
    35     }
    36     public IEnumerator<ISymbol> GetEnumerator() {
    37       return (IEnumerator<ISymbol>)base.GetEnumerator();
     28  public class Sequence : ReadOnlyCollection<ISymbol> {
     29    public Sequence(IList<ISymbol> seq)
     30      : base(seq) {
    3831    }
    3932
     
    5043
    5144    public override string ToString() {
    52       var b = new StringBuilder();
    53       ForEach(s => b.AppendFormat("{0} ", s));
    54       return b.ToString();
     45      return this.Aggregate("", (str, symb) => str + symb);
    5546    }
    5647  }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Symbol.cs

    r10063 r10067  
    2121
    2222using System;
     23using System.Collections.Generic;
     24using System.Linq;
     25
    2326namespace HeuristicLab.Grammars {
    24   public class Symbol : ISymbol, IEquatable<ISymbol> {
     27  public class Symbol : ISymbol {
    2528    public string Name { get; private set; }
    26     public IAttribute Attribute { get; private set; }
    27     public Symbol(string name, IAttribute attribute = null) {
     29    public IEnumerable<IAttribute> Attributes { get; private set; }
     30    public Symbol(string name, IEnumerable<IAttribute> attributes = null) {
    2831      this.Name = name;
    29       this.Attribute = attribute;
     32      if (attributes != null) this.Attributes = attributes;
     33      else this.Attributes = Enumerable.Empty<IAttribute>();
    3034    }
    3135
    32     public bool Equals(ISymbol other) {
    33       return Name == other.Name;
     36    public string GetAttributeString() {
     37      if (!Attributes.Any()) return string.Empty;
     38      return Attributes.Skip(1).Aggregate(Attributes.First().ToString(), (str, a) => str + ", " + a.ToString());
    3439    }
    3540
     
    3742      if (obj == null) return false;
    3843      if (obj == this) return true;
    39       var other = obj as ISymbol;
     44      var other = obj as Symbol;
    4045      if (other == null) return false;
    41       return Equals(other);
     46      return this.Name == other.Name; // compare names only
    4247    }
    4348
     
    4550      return Name.GetHashCode();
    4651    }
     52
     53    public override string ToString() {
     54      return Name + "<" + GetAttributeString() + ">";
     55    }
    4756  }
    4857}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/AST.cs

    r9842 r10067  
    118118  public string NtSymbol { get; set; }
    119119  public string LocalCode { get; set; }
    120   public RuleExprNode RuleExpr { get; set; }
     120  public AlternativesNode Alternatives { get; set; }
    121121}
    122122
     
    124124
    125125public class AlternativesNode : RuleExprNode {
    126   private List<RuleExprNode> alt;
    127   public IEnumerable<RuleExprNode> Alternatives { get { return alt; } }
     126  private List<SequenceNode> alt;
     127  public IEnumerable<SequenceNode> Alternatives { get { return alt; } }
    128128  public AlternativesNode() {
    129     this.alt = new List<RuleExprNode>();
     129    this.alt = new List<SequenceNode>();
    130130  }
    131   public void Add(RuleExprNode expr) {
     131  public void Add(SequenceNode expr) {
    132132    alt.Add(expr);
    133133  }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/GPDef.atg

    r10049 r10067  
    148148                                                                                         myTNode.Ident = identStr;
    149149                                                                                         myTNode.FormalParameters = src;
    150                                                                                          myTNode.FieldDefinitions = Util.ExtractFormalParameters(src);
     150                                                                                         myTNode.FieldDefinitions = Util.ExtractParameters(src);
    151151                                                                                  .)
    152152  [ "CONSTRAINTS" ConstraintDef<out constraints>
     
    188188  /******************************************************/
    189189  RuleDef<out RuleNode rule> =                                                    (.
    190                                                                                      RuleExprNode expr = null;
     190                                                                                     AlternativesNode alternatives = null;
    191191                                                                                     string identStr = null;
    192192                                                                                     RuleNode myRule = null;
     
    204204                                                                                  .)
    205205  ]
    206   SynExpr<out expr> '.'                                                          (.
    207                                                                                     myRule.RuleExpr = expr;
    208                                                                                  .)
    209   .
    210 
    211   /******************************************************/
    212   SynExpr<out RuleExprNode expr > =                                               (.
    213                                                                                     expr = null;
    214                                                                                     AlternativesNode alt = null;
    215                                                                                   .)
    216   SynTerm<out expr>                                                               (.
     206  SynExpr<out alternatives> '.'                                                  (.
     207                                                                                    myRule.Alternatives = alternatives;
     208                                                                                 .)
     209  .
     210
     211  /******************************************************/
     212  SynExpr<out AlternativesNode alt > =                                            (.
    217213                                                                                    alt = new AlternativesNode();
    218                                                                                     alt.Add(expr);
     214                                                                                    SequenceNode seq = null;
     215                                                                                  .)
     216  SynTerm<out seq>                                                                (.
     217                                                                                    alt.Add(seq);
    219218                                                                                  .)
    220219  {
    221     '|' SynTerm<out expr>                                                         (. alt.Add(expr); expr = alt; .)
     220    '|' SynTerm<out seq>                                                          (. alt.Add(seq); .)
    222221  }
    223222  .
    224223
    225224  /******************************************************/
    226   SynTerm<out RuleExprNode expr> =                                               (. SequenceNode seq = null; expr = null; .)
     225  SynTerm<out SequenceNode seq> =                                                (. seq = new SequenceNode(); RuleExprNode expr = null; .)
    227226  SynFact<out expr>                                                              (.
    228                                                                                    seq = new SequenceNode();
    229227                                                                                   seq.Add(expr);
    230228                                                                                 .)
    231229  {
    232     SynFact<out expr>                                                            (. seq.Add(expr); expr = seq; .)
     230    SynFact<out expr>                                                            (. seq.Add(expr); .)
    233231  }
    234232  .
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/HeuristicLab.Problems.GPDL-3.4.csproj

    r10065 r10067  
    106106  <ItemGroup>
    107107    <Compile Include="AST.cs" />
    108     <Compile Include="Grammar.cs" />
    109108    <Compile Include="Parser.cs" />
    110109    <Compile Include="Scanner.cs" />
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/Parser.cs

    r10065 r10067  
    216216    myTNode.Ident = identStr;
    217217    myTNode.FormalParameters = src;
    218     myTNode.FieldDefinitions = Util.ExtractFormalParameters(src);
     218    myTNode.FieldDefinitions = Util.ExtractParameters(src);
    219219   
    220220    if (la.kind == 15) {
     
    227227
    228228  void RuleDef(out RuleNode rule) {
    229     RuleExprNode expr = null;
     229    AlternativesNode alternatives = null;
    230230    string identStr = null;
    231231    RuleNode myRule = null;
     
    249249     
    250250    }
    251     SynExpr(out expr);
     251    SynExpr(out alternatives);
    252252    Expect(13);
    253     myRule.RuleExpr = expr;
     253    myRule.Alternatives = alternatives;
    254254   
    255255  }
     
    304304  }
    305305
    306   void SynExpr(out RuleExprNode expr ) {
    307     expr = null;
    308     AlternativesNode alt = null;
    309    
    310     SynTerm(out expr);
     306  void SynExpr(out AlternativesNode alt ) {
    311307    alt = new AlternativesNode();
    312     alt.Add(expr);
     308    SequenceNode seq = null;
     309   
     310    SynTerm(out seq);
     311    alt.Add(seq);
    313312   
    314313    while (la.kind == 22) {
    315314      Get();
    316       SynTerm(out expr);
    317       alt.Add(expr); expr = alt;
    318     }
    319   }
    320 
    321   void SynTerm(out RuleExprNode expr) {
    322     SequenceNode seq = null; expr = null;
     315      SynTerm(out seq);
     316      alt.Add(seq);
     317    }
     318  }
     319
     320  void SynTerm(out SequenceNode seq) {
     321    seq = new SequenceNode(); RuleExprNode expr = null;
    323322    SynFact(out expr);
    324     seq = new SequenceNode();
    325323    seq.Add(expr);
    326324   
    327325    while (la.kind == 1 || la.kind == 14) {
    328326      SynFact(out expr);
    329       seq.Add(expr); expr = seq;
     327      seq.Add(expr);
    330328    }
    331329  }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/Util.cs

    r9872 r10067  
    2525
    2626public class Util {
    27   private static Regex formalParameterExpr = new Regex(@"\s*,?\s*((?<refOrOut>(out|ref))\s+)?(?<type>[_\w]*)\s+(?<id>[_\w]*)\s*");
    28   public static IEnumerable<TerminalNode.FieldDefinition> ExtractFormalParameters(string formalParameterSrc) {
    29     var match = formalParameterExpr.Match(formalParameterSrc);
     27  // simplistic regex for formal parameters, any string of non-whitespace and not comma characters is allowed as a type name
     28  private static string refOrOutGroup = @"(?:(?<refOrOut>(out|ref))\s+)"; // "ref " | "out "
     29  private static string typeGroup = @"(?:(?<type>[^ ,\f\n\r\t\v]*)\s+)";
     30  private static string identGroup = @"(?<id>[\w]+)\s*";
     31  private static Regex formalParameterExpr = new Regex(@"\s*,?\s*" + refOrOutGroup + "?" + typeGroup + "?" + identGroup, RegexOptions.ECMAScript);
     32  public static IEnumerable<TerminalNode.FieldDefinition> ExtractParameters(string formalParameterSrc) {
     33
    3034    var matches = formalParameterExpr.Matches(formalParameterSrc);
    3135
Note: See TracChangeset for help on using the changeset viewer.