context: /*
   * GrGen: graph rewrite generator tool -- release GrGen.NET 4.4
   * Copyright (C) 2003-2015 Universitaet Karlsruhe, Institut fuer Programmstrukturen und Datenorganisation, LS Goos; and free programmers
   * licensed under LGPL v3 (see LICENSE.txt included in the packaging of this file)
   * www.grgen.net
   */
  
  // by Moritz Kroll, Edgar Jakumeit
  
  #define MONO_MULTIDIMARRAY_WORKAROUND       // must be equally set to the same flag in lgspGraphStatistics.cs!
  //#define RANDOM_LOOKUP_LIST_START      // currently broken
  //#define DUMP_SCHEDULED_SEARCH_PLAN
  //#define DUMP_SEARCHPROGRAMS
  
  using System;
  using System.Collections.Generic;
  using System.Text;
  
  using de.unika.ipd.grGen.lgsp;
  using de.unika.ipd.grGen.expression;
  using System.IO;
  using de.unika.ipd.grGen.libGr;
  using System.Diagnostics;
  using Microsoft.CSharp;
  using System.CodeDom.Compiler;
  using System.Reflection;
  
  
  namespace de.unika.ipd.grGen.lgsp
  {
      /// <summary>
      /// Class generating matcher programs out of rules.
      /// A PatternGraphAnalyzer must run before the matcher generator is used,
      /// so that the analysis data is written the pattern graphs of the matching patterns to generate code for.
      /// </summary>
      public class LGSPMatcherGenerator
      {
          /// <summary>
          /// The model for which the matcher functions shall be generated.
          /// </summary>
          private IGraphModel model;
  
          /// <summary>
          /// If true, the generated matcher functions are commented to improve understanding the source code.
          /// </summary>
          public bool CommentSourceCode = false;
  
          /// <summary>
          /// If true, the source code of dynamically generated matcher functions are dumped to a file in the current directory.
          /// </summary>
          public bool DumpDynSourceCode = false;
  
          /// <summary>
          /// If true, generated search plans are dumped in VCG and TXT files in the current directory.
          /// </summary>
          public bool DumpSearchPlan = false;
  
          /// <summary>
          /// If true, the negatives, independents, and evaluations are inserted at the end of the schedule
          /// instead of as early as possible; this is likely less efficient but allows to use checks 
          /// which require that they are only called after a structural match was found
          /// </summary>
          public bool LazyNegativeIndependentConditionEvaluation = false;
  
          /// <summary>
          /// If true, the independents are to be inlined
          /// </summary>
          public bool InlineIndependents = true;
  
          /// <summary>
          /// If true, profiling information is to be collected, i.e. some statistics about search steps executed
          /// </summary>
          public bool Profile = false;
  
          /// <summary>
          /// Instantiates a new instance of LGSPMatcherGenerator with the given graph model.
          /// A PatternGraphAnalyzer must run before the matcher generator is used,
          /// so that the analysis data is written the pattern graphs of the matching patterns to generate code for.
          /// </summary>
          /// <param name="model">The model for which the matcher functions shall be generated.</param>
          public LGSPMatcherGenerator(IGraphModel model)
          {
              this.model = model;
          }
  
          /// <summary>
          /// Builds a pattern graph out of the graph.
          /// The pattern graph retains links to the original graph elements and uses them for attribute comparison.
          /// </summary>
          /// <param name="graph">The graph which is to be transfered into a pattern</param>
          /// <returns></returns>
          public PatternGraph BuildPatternGraph(LGSPGraph graph)
          {
              int numNodes = graph.NumNodes;
              int numEdges = graph.NumEdges;
  
              int count = 0;
              PatternNode[] nodes = new PatternNode[numNodes];
              INode[] correspondingNodes = new INode[numNodes];
              foreach(INode node in graph.Nodes)
              {
                  LGSPNode n = (LGSPNode)node;
                  nodes[count] = new PatternNode(
                      n.Type.TypeID, n.Type, n.Type.PackagePrefixedName,
                      graph.Name+"_node_"+count, "node_"+count,
                      null, null,
                      1.0f, -1, false,
                      null, null, null, null, null,
                      null, false, null
                  );
                  correspondingNodes[count] = node;
                  ++count;
              }
  
              count = 0;
              PatternEdge[] edges = new PatternEdge[numEdges];
              IEdge[] correspondingEdges = new IEdge[numEdges];
              foreach(IEdge edge in graph.Edges)
              {
                  LGSPEdge e = (LGSPEdge)edge;
                  edges[count] = new PatternEdge(
                      true,
                      e.Type.TypeID, e.Type, e.Type.PackagePrefixedName,
                      graph.Name+"_edge_"+count, "edge_"+count,
                      null, null,
                      1.0f, -1, false,
                      null, null, null, null, null,
                      null, false, null
                  );
                  correspondingEdges[count] = edge;
                  ++count;
              }
  
              bool[,] homNodes = new bool[numNodes, numNodes];
              for(int i = 0; i < numNodes; ++i)
                  for(int j = 0; j < numNodes; ++j)
                      homNodes[i, j] = false;
  
              bool[,] homEdges = new bool[numEdges, numEdges];
              for(int i = 0; i < numEdges; ++i)
                  for(int j = 0; j < numEdges; ++j)
                      homEdges[i, j] = false;
              
              bool[,] homNodesGlobal = new bool[numNodes, numNodes];
              for(int i = 0; i < numNodes; ++i)
                  for(int j = 0; j < numNodes; ++j)
                      homNodesGlobal[i, j] = false;
  
              bool[,] homEdgesGlobal = new bool[numEdges, numEdges];
              for(int i = 0; i < numEdges; ++i)
                  for(int j = 0; j < numEdges; ++j)
                      homEdgesGlobal[i, j] = false;
  
              bool[] totallyHomNodes = new bool[numNodes];
              for(int i = 0; i < numNodes; ++i)
                  totallyHomNodes[i] = false;
  
              bool[] totallyHomEdges = new bool[numEdges];
              for(int i = 0; i < numEdges; ++i)
                  totallyHomEdges[i] = false;
  
              List<PatternCondition> pcs = new List<PatternCondition>();
              for(int i = 0; i < numNodes; ++i)
              {
                  if(nodes[i].Type.NumAttributes > 0)
                      pcs.Add(new PatternCondition(new expression.AreAttributesEqual(correspondingNodes[i], nodes[i]),
                          new string[] { nodes[i].name }, new string[] { }, new string[] { }, new VarType[] { }));
              }
              for(int i = 0; i < numEdges; ++i)
              {
                  if(edges[i].Type.NumAttributes > 0)
                      pcs.Add(new PatternCondition(new expression.AreAttributesEqual(correspondingEdges[i], edges[i]),
                          new string[] { }, new string[] { edges[i].name }, new string[] { }, new VarType[] { }));
              }
              PatternCondition[] patternConditions = pcs.ToArray();
  
              PatternGraph patternGraph = new PatternGraph(
                  graph.Name, "",
                  null, graph.Name,
                  false, false,
                  nodes, edges, new PatternVariable[0],
                  new PatternGraphEmbedding[0], new Alternative[0], new Iterated[0],
                  new PatternGraph[0], new PatternGraph[0],
                  patternConditions, new PatternYielding[0],
                  homNodes, homEdges,
                  homNodesGlobal, homEdgesGlobal,
                  totallyHomNodes, totallyHomEdges
              );
              foreach(PatternNode node in nodes)
                  node.pointOfDefinition = patternGraph;
              foreach(PatternEdge edge in edges)
                  edge.pointOfDefinition = patternGraph;
              patternGraph.correspondingNodes = correspondingNodes;
              patternGraph.correspondingEdges = correspondingEdges;
  
              foreach(IEdge edge in graph.Edges)
              {
                  int edgeIndex = Array.IndexOf<IEdge>(correspondingEdges, edge);
                  int sourceIndex = Array.IndexOf<INode>(correspondingNodes, edge.Source);
                  int targetIndex = Array.IndexOf<INode>(correspondingNodes, edge.Target);
                  patternGraph.edgeToSourceNode.Add(edges[edgeIndex], nodes[sourceIndex]);
                  patternGraph.edgeToTargetNode.Add(edges[edgeIndex], nodes[targetIndex]);
              }
  
              PatternGraphAnalyzer.PrepareInline(patternGraph);
  
              return patternGraph;
          }
  
          /// <summary>
          /// Generate plan graph for given pattern graph with costs from the analyzed host graph.
          /// Plan graph contains nodes representing the pattern elements (nodes and edges)
          /// and edges representing the matching operations to get the elements by.
          /// Edges in plan graph are given in the nodes by incoming list, as needed for MSA computation.
          /// </summary>
          public PlanGraph GeneratePlanGraph(LGSPGraphStatistics graphStatistics, PatternGraph patternGraph,
              bool isNegativeOrIndependent, bool isSubpatternLike, 
              IDictionary<PatternElement, SetValueType> presetsFromIndependentInlining)
          {
              // 
              // If you change this method, chances are high you also want to change GenerateStaticPlanGraph in LGSPGrGen
              // look there for version without ifdef junk
              // todo: unify it with GenerateStaticPlanGraph in LGSPGrGen
              // 
  
              // Create root node
              // Create plan graph nodes for all pattern graph nodes and all pattern graph edges
              // Create "lookup" plan graph edge from root node to each plan graph node
              // Create "implicit source" plan graph edge from each plan graph node originating with a pattern edge 
              //     to the plan graph node created by the source node of the pattern graph edge
              // Create "implicit target" plan graph edge from each plan graph node originating with a pattern edge 
              //     to the plan graph node created by the target node of the pattern graph edge
              // Create "incoming" plan graph edge from each plan graph node originating with a pattern node
              //     to a plan graph node created by one of the incoming edges of the pattern node
              // Create "outgoing" plan graph edge from each plan graph node originating with a pattern node
              //     to a plan graph node created by one of the outgoing edges of the pattern node
              // Ensured: there's no plan graph edge with a preset element as target besides the lookup,
              //     so presets are only search operation sources
              // Create "pick from storage" plan graph edge for plan graph nodes which are to be picked from a storage,
              //     from root node on, instead of lookup, no other plan graph edge having this node as target
              // Create "pick from storage attribute" plan graph edge from storage attribute owner to storage picking result,
              //     no lookup, no other plan graph edge having this node as target
              // Create "map" by storage plan graph edge from accessor to storage mapping result
              //     no lookup, no other plan graph edge having this node as target
              // Create "pick from index" plan graph edge for plan graph nodes which are to be picked from an index,
              //     from root node on, instead of lookup, no other plan graph edge having this node as target
              // Create "pick from index depending" plan graph edge from node the index expressions depend on,
              //     no lookup, no other plan graph edge having this node as target
              // Create "cast" plan graph edge from element before casting to cast result,
              //     no lookup, no other plan graph edge having this node as target
  
              int numNodes = patternGraph.nodesPlusInlined.Length;
              if(InlineIndependents && !isNegativeOrIndependent)
                  numNodes += LGSPMatcherGenerator.NumNodesInIndependentsMatchedThere(patternGraph);
              int numEdges = patternGraph.edgesPlusInlined.Length;
              if(InlineIndependents && !isNegativeOrIndependent)
                  numEdges += LGSPMatcherGenerator.NumEdgesInIndependentsMatchedThere(patternGraph);
              PlanNode[] planNodes = new PlanNode[numNodes + numEdges];
              List<PlanEdge> planEdges = new List<PlanEdge>(numNodes + 5 * numEdges); // upper bound for num of edges (lookup nodes + lookup edges + impl. tgt + impl. src + incoming + outgoing)
  
              Dictionary<PatternNode, PatternNode> originalToInlinedIndependent = new Dictionary<PatternNode, PatternNode>();
  
              int nodesIndex = 0;
              float zeroCost = 1;
  
              PlanNode planRoot = new PlanNode("root");
  
              // create plan nodes and lookup plan edges for all pattern graph nodes
              for(int i = 0; i < patternGraph.nodesPlusInlined.Length; i++)
              {
                  PatternNode node = patternGraph.nodesPlusInlined[i];
  
                  PlanNode planNode;
                  PlanEdge rootToNodePlanEdge;
                  CreatePlanNodeAndLookupPlanEdge(node, i + 1, 
                      graphStatistics, patternGraph, isNegativeOrIndependent, isSubpatternLike, planRoot, zeroCost,
                      originalToInlinedIndependent, presetsFromIndependentInlining,
                      out planNode, out rootToNodePlanEdge);
  
                  planNodes[nodesIndex] = planNode;
                  if(rootToNodePlanEdge != null)
                  {
                      planEdges.Add(rootToNodePlanEdge);
                      planNode.IncomingEdges.Add(rootToNodePlanEdge);
                  }
  
                  node.TempPlanMapping = planNode;
                  ++nodesIndex;
              }
              if(InlineIndependents && !isNegativeOrIndependent) // independent inlining only if not in negative/independent
              {
                  foreach(PatternGraph independent in patternGraph.independentPatternGraphsPlusInlined)
                  {
                      foreach(PatternNode nodeOriginal in LGSPMatcherGenerator.NodesInIndependentMatchedThere(independent))
                      {
                          PatternNode node = new PatternNode(nodeOriginal, "_inlined_" + independent.name);
                          originalToInlinedIndependent.Add(nodeOriginal, node);
  
                          PlanNode planNode;
                          PlanEdge rootToNodePlanEdge;
                          CreatePlanNodeAndLookupPlanEdge(node, -1,
                              graphStatistics, patternGraph, isNegativeOrIndependent, isSubpatternLike, planRoot, zeroCost,
                              originalToInlinedIndependent, presetsFromIndependentInlining,
                              out planNode, out rootToNodePlanEdge);
  
                          planNodes[nodesIndex] = planNode;
                          if(rootToNodePlanEdge != null)
                          {
                              planEdges.Add(rootToNodePlanEdge);
                              planNode.IncomingEdges.Add(rootToNodePlanEdge);
                          }
  
                          node.TempPlanMapping = planNode;
                          ++nodesIndex;
                      }
                  }
              }
  
              // create plan nodes and lookup plus incidence handling plan edges for all pattern graph edges
              for(int i = 0; i < patternGraph.edgesPlusInlined.Length; ++i)
              {
                  PatternEdge edge = patternGraph.edgesPlusInlined[i];
  
                  bool isPreset;
                  PlanNode planNode;
                  PlanEdge rootToNodePlanEdge;
                  CreatePlanNodeAndLookupPlanEdge(edge, i + 1, 
                      graphStatistics, patternGraph, isNegativeOrIndependent, isSubpatternLike, planRoot, zeroCost,
                      originalToInlinedIndependent, presetsFromIndependentInlining,
                      out isPreset, out planNode, out rootToNodePlanEdge);
  
                  planNodes[nodesIndex] = planNode;
                  if(rootToNodePlanEdge != null)
                  {
                      planEdges.Add(rootToNodePlanEdge);
                      planNode.IncomingEdges.Add(rootToNodePlanEdge);
                  }
  
                  CreateSourceTargetIncomingOutgoingPlanEdges(edge, planNode, planEdges,
                      originalToInlinedIndependent, graphStatistics, patternGraph, isPreset, zeroCost);
  
                  edge.TempPlanMapping = planNode;
                  ++nodesIndex;
              }
              if(InlineIndependents && !isNegativeOrIndependent) // independent inlining only if not in negative/independent
              {
                  foreach(PatternGraph independent in patternGraph.independentPatternGraphsPlusInlined)
                  {
                      foreach(PatternEdge edgeOriginal in LGSPMatcherGenerator.EdgesInIndependentMatchedThere(independent))
                      {
                          PatternEdge edge = new PatternEdge(edgeOriginal, "_inlined_" + independent.name);
  
                          bool isPreset;
                          PlanNode planNode;
                          PlanEdge rootToNodePlanEdge;
                          CreatePlanNodeAndLookupPlanEdge(edge, -1,
                              graphStatistics, patternGraph, isNegativeOrIndependent, isSubpatternLike, planRoot, zeroCost,
                              originalToInlinedIndependent, presetsFromIndependentInlining,
                              out isPreset, out planNode, out rootToNodePlanEdge);
  
                          planNodes[nodesIndex] = planNode;
                          if(rootToNodePlanEdge != null)
                          {
                              planEdges.Add(rootToNodePlanEdge);
                              planNode.IncomingEdges.Add(rootToNodePlanEdge);
                          }
  
                          CreateSourceTargetIncomingOutgoingPlanEdges(edge, planNode, planEdges,
                              originalToInlinedIndependent, graphStatistics, patternGraph, isPreset, zeroCost);
  
                          edge.TempPlanMapping = planNode;
                          ++nodesIndex;
                      }
                  }
              }
  
              ////////////////////////////////////////////////////////////////////////////
              // second run handling dependent storage and index picking (can't be done in first run due to dependencies between elements)
  
              // create map/pick/cast/assign plan edges for all pattern graph nodes
              for(int i = 0; i < patternGraph.nodesPlusInlined.Length; ++i)
              {
                  PatternNode node = patternGraph.nodesPlusInlined[i];
  
                  if(node.PointOfDefinition == patternGraph && !presetsFromIndependentInlining.ContainsKey(node))
                      CreatePickMapCastAssignPlanEdges(node, planEdges, zeroCost);
              }
  
              // create map/pick/cast/assign plan edges for all pattern graph edges
              for(int i = 0; i < patternGraph.edgesPlusInlined.Length; ++i)
              {
                  PatternEdge edge = patternGraph.edgesPlusInlined[i];
  
                  if(edge.PointOfDefinition == patternGraph && !presetsFromIndependentInlining.ContainsKey(edge))
                      CreatePickMapCastAssignPlanEdges(edge, planEdges, zeroCost);
              }
  
              return new PlanGraph(planRoot, planNodes, planEdges.ToArray());
          }
  
          private static void CreatePlanNodeAndLookupPlanEdge(PatternNode node, int elemId, 
              LGSPGraphStatistics graphStatistics, PatternGraph patternGraph, bool isNegativeOrIndependent, bool isSubpatternLike, PlanNode planRoot, float zeroCost,
              IDictionary<PatternNode, PatternNode> originalToInlinedIndependent, IDictionary<PatternElement, SetValueType> presetsFromIndependentInlining,
              out PlanNode planNode, out PlanEdge rootToNodePlanEdge)
          {
              float cost;
              bool isPreset;
              SearchOperationType searchOperationType;
              if(node.DefToBeYieldedTo)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = SearchOperationType.DefToBeYieldedTo;
              }
              else if(node.PointOfDefinition == null)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = isSubpatternLike ? SearchOperationType.SubPreset : SearchOperationType.ActionPreset;
              }
              else if(node.PointOfDefinition != patternGraph && node.OriginalIndependentElement == null)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = isNegativeOrIndependent ? SearchOperationType.NegIdptPreset : SearchOperationType.SubPreset;
              }
              else if(presetsFromIndependentInlining.ContainsKey(node))
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = SearchOperationType.NegIdptPreset;
                  node.PresetBecauseOfIndependentInlining = true;
              }
              else if(node.Storage != null)
              {
                  if(node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickFromStorage; // pick from storage instead of lookup from graph
                  }
              }
              else if(node.IndexAccess != null)
              {
                  if(node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickFromIndex; // pick from index instead of lookup from graph
                  }
              }
              else if(node.NameLookup != null)
              {
                  if(node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickByName; // pick by name instead of lookup from graph
                  }
              }
              else if(node.UniqueLookup != null)
              {
                  if(node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickByUnique; // pick by unique instead of lookup from graph
                  }
              }
              else if(node.ElementBeforeCasting != null)
              {
                  cost = zeroCost;
                  isPreset = false;
                  searchOperationType = SearchOperationType.Void; // the element before casting is needed, so there is no lookup like operation
              }
              else
              {
                  cost = graphStatistics.nodeCounts[node.TypeID];
                  cost = CostIncreaseForInlinedIndependent(node, cost);
                  isPreset = false;
                  searchOperationType = SearchOperationType.Lookup;
              }
  
              planNode = new PlanNode(node, elemId, isPreset);
              rootToNodePlanEdge = null;
              if(searchOperationType != SearchOperationType.Void)
                  rootToNodePlanEdge = new PlanEdge(searchOperationType, planRoot, planNode, cost);
          }
  
          private static void CreatePlanNodeAndLookupPlanEdge(PatternEdge edge, int elemId, 
              LGSPGraphStatistics graphStatistics, PatternGraph patternGraph, bool isNegativeOrIndependent, bool isSubpatternLike, PlanNode planRoot, float zeroCost,
              IDictionary<PatternNode, PatternNode> originalToInlinedIndependent, IDictionary<PatternElement, SetValueType> presetsFromIndependentInlining,
              out bool isPreset, out PlanNode planNode, out PlanEdge rootToNodePlanEdge)
          {
              float cost;
              SearchOperationType searchOperationType;
              if(edge.DefToBeYieldedTo)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = SearchOperationType.DefToBeYieldedTo;
              }
              else if(edge.PointOfDefinition == null)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = isSubpatternLike ? SearchOperationType.SubPreset : SearchOperationType.ActionPreset;
              }
              else if(edge.PointOfDefinition != patternGraph && edge.OriginalIndependentElement == null)
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = isNegativeOrIndependent ? SearchOperationType.NegIdptPreset : SearchOperationType.SubPreset;
              }
              else if(presetsFromIndependentInlining.ContainsKey(edge))
              {
                  cost = zeroCost;
                  isPreset = true;
                  searchOperationType = SearchOperationType.NegIdptPreset;
                  edge.PresetBecauseOfIndependentInlining = true;
              }
              else if(edge.Storage != null)
              {
                  if(edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickFromStorage; // pick from storage instead of lookup from graph
                  }
              }
              else if(edge.IndexAccess != null)
              {
                  if(edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickFromIndex; // pick from index instead of lookup from graph
                  }
              }
              else if(edge.NameLookup != null)
              {
                  if(edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickByName; // pick by name instead of lookup from graph
                  }
              }
              else if(edge.UniqueLookup != null)
              {
                  if(edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.Void; // the element we depend on is needed, so there is no lookup like operation
                  }
                  else
                  {
                      cost = zeroCost;
                      isPreset = false;
                      searchOperationType = SearchOperationType.PickByUnique; // pick by unique instead of lookup from graph
                  }
              }
              else if(edge.ElementBeforeCasting != null)
              {
                  cost = zeroCost;
                  isPreset = false;
                  searchOperationType = SearchOperationType.Void; // the element before casting is needed, so there is no lookup like operation
              }
              else
              {
                  cost = graphStatistics.edgeCounts[edge.TypeID];
                  cost = CostIncreaseForInlinedIndependent(edge, cost);
  
                  isPreset = false;
                  searchOperationType = SearchOperationType.Lookup;
              }
  
              PatternNode source = GetSourcePlusInlined(edge, patternGraph, originalToInlinedIndependent);
              PatternNode target = GetTargetPlusInlined(edge, patternGraph, originalToInlinedIndependent);
              planNode = new PlanNode(edge, elemId, isPreset,
                  source != null ? source.TempPlanMapping : null,
                  target != null ? target.TempPlanMapping : null);
              rootToNodePlanEdge = null;
              if(searchOperationType != SearchOperationType.Void)
                  rootToNodePlanEdge = new PlanEdge(searchOperationType, planRoot, planNode, cost);
          }
  
          private void CreateSourceTargetIncomingOutgoingPlanEdges(PatternEdge edge, PlanNode planNode, 
              List<PlanEdge> planEdges, IDictionary<PatternNode, PatternNode> originalToInlinedIndependent,
              LGSPGraphStatistics graphStatistics, PatternGraph patternGraph, bool isPreset, float zeroCost)
          {
              // only add implicit source operation if edge source is needed and the edge source is 
              // not a preset node and not a storage node and not an index node and not a cast node
              PatternNode source = GetSourcePlusInlined(edge, patternGraph, originalToInlinedIndependent);
              if(source != null
                  && !source.TempPlanMapping.IsPreset
                  && source.Storage == null
                  && source.IndexAccess == null
                  && source.NameLookup == null
                  && source.UniqueLookup == null
                  && source.ElementBeforeCasting == null)
              {
                  SearchOperationType operation = edge.fixedDirection ?
                      SearchOperationType.ImplicitSource : SearchOperationType.Implicit;
                  PlanEdge implSrcPlanEdge = new PlanEdge(operation, planNode,
                      source.TempPlanMapping, zeroCost);
                  planEdges.Add(implSrcPlanEdge);
                  source.TempPlanMapping.IncomingEdges.Add(implSrcPlanEdge);
              }
              // only add implicit target operation if edge target is needed and the edge target is
              // not a preset node and not a storage node and not an index node and not a cast node
              PatternNode target = GetTargetPlusInlined(edge, patternGraph, originalToInlinedIndependent);
              if(target != null
                  && !target.TempPlanMapping.IsPreset
                  && target.Storage == null
                  && target.IndexAccess == null
                  && target.NameLookup == null
                  && target.UniqueLookup == null
                  && target.ElementBeforeCasting == null)
              {
                  SearchOperationType operation = edge.fixedDirection ?
                      SearchOperationType.ImplicitTarget : SearchOperationType.Implicit;
                  PlanEdge implTgtPlanEdge = new PlanEdge(operation, planNode,
                      target.TempPlanMapping, zeroCost);
                  planEdges.Add(implTgtPlanEdge);
                  target.TempPlanMapping.IncomingEdges.Add(implTgtPlanEdge);
              }
  
              // edge must only be reachable from other nodes if it's not a preset and not storage determined and not index determined and not a cast
              if(!isPreset
                  && edge.Storage == null
                  && edge.IndexAccess == null
                  && edge.NameLookup == null
                  && edge.UniqueLookup == null
                  && edge.ElementBeforeCasting == null)
              {
                  // no outgoing on source node if no source
                  if(source != null)
                  {
                      int targetTypeID;
                      if(target != null) targetTypeID = target.TypeID;
                      else targetTypeID = model.NodeModel.RootType.TypeID;
                      // cost of walking along edge
  #if MONO_MULTIDIMARRAY_WORKAROUND
                      float normCost = graphStatistics.vstructs[((source.TypeID * graphStatistics.dim1size + edge.TypeID) * graphStatistics.dim2size
                          + targetTypeID) * 2 + (int)LGSPDirection.Out];
                      if(!edge.fixedDirection)
                      {
                          normCost += graphStatistics.vstructs[((source.TypeID * graphStatistics.dim1size + edge.TypeID) * graphStatistics.dim2size
                              + targetTypeID) * 2 + (int)LGSPDirection.In];
                      }
  #else
                      float normCost = graph.statistics.vstructs[source.TypeID, edge.TypeID, targetTypeID, (int) LGSPDirection.Out];
                      if (!edge.fixedDirection) {
                          normCost += graph.statistics.vstructs[source.TypeID, edge.TypeID, targetTypeID, (int) LGSPDirection.In];
                      }
  #endif
                      if(graphStatistics.nodeCounts[source.TypeID] != 0)
                          normCost /= graphStatistics.nodeCounts[source.TypeID];
                      normCost = CostIncreaseForInlinedIndependent(edge, normCost);
                      SearchOperationType operation = edge.fixedDirection ?
                          SearchOperationType.Outgoing : SearchOperationType.Incident;
                      PlanEdge outPlanEdge = new PlanEdge(operation, source.TempPlanMapping,
                          planNode, normCost);
                      planEdges.Add(outPlanEdge);
                      planNode.IncomingEdges.Add(outPlanEdge);
                  }
  
                  // no incoming on target node if no target
                  if(target != null)
                  {
                      int sourceTypeID;
                      if(source != null) sourceTypeID = source.TypeID;
                      else sourceTypeID = model.NodeModel.RootType.TypeID;
                      // cost of walking in opposite direction of edge
  #if MONO_MULTIDIMARRAY_WORKAROUND
                      float revCost = graphStatistics.vstructs[((target.TypeID * graphStatistics.dim1size + edge.TypeID) * graphStatistics.dim2size
                          + sourceTypeID) * 2 + (int)LGSPDirection.In];
                      if(!edge.fixedDirection)
                      {
                          revCost += graphStatistics.vstructs[((target.TypeID * graphStatistics.dim1size + edge.TypeID) * graphStatistics.dim2size
                              + sourceTypeID) * 2 + (int)LGSPDirection.Out];
                      }
  #else
                      float revCost = graph.statistics.vstructs[target.TypeID, edge.TypeID, sourceTypeID, (int) LGSPDirection.In];
                      if (!edge.fixedDirection) {
                          revCost += graph.statistics.vstructs[target.TypeID, edge.TypeID, sourceTypeID, (int) LGSPDirection.Out];
                      }
  #endif
                      if(graphStatistics.nodeCounts[target.TypeID] != 0)
                          revCost /= graphStatistics.nodeCounts[target.TypeID];
                      revCost = CostIncreaseForInlinedIndependent(edge, revCost); 
                      SearchOperationType operation = edge.fixedDirection ?
                          SearchOperationType.Incoming : SearchOperationType.Incident;
                      PlanEdge inPlanEdge = new PlanEdge(operation, target.TempPlanMapping,
                          planNode, revCost);
                      planEdges.Add(inPlanEdge);
                      planNode.IncomingEdges.Add(inPlanEdge);
                  }
              }
          }
  
          public static void CreatePickMapCastAssignPlanEdges(PatternNode node, List<PlanEdge> planEdges, float zeroCost)
          {
              if(node.Storage != null && node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge storAccessPlanEdge = new PlanEdge(
                      node.StorageIndex != null ? SearchOperationType.MapWithStorageDependent : SearchOperationType.PickFromStorageDependent,
                      node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(storAccessPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(storAccessPlanEdge);
              }
              else if(node.IndexAccess != null && node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge indexAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickFromIndexDependent,
                      node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(indexAccessPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(indexAccessPlanEdge);
              }
              else if(node.NameLookup != null && node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge nameAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickByNameDependent,
                      node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(nameAccessPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(nameAccessPlanEdge);
              }
              else if(node.UniqueLookup != null && node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge uniqueAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickByUniqueDependent,
                      node.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(uniqueAccessPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(uniqueAccessPlanEdge);
              }
              else if(node.ElementBeforeCasting != null)
              {
                  PlanEdge castPlanEdge = new PlanEdge(SearchOperationType.Cast,
                      node.ElementBeforeCasting.TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(castPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(castPlanEdge);
              }
              else if(node.AssignmentSource != null)
              {
                  PlanEdge assignPlanEdge = new PlanEdge(SearchOperationType.Assign,
                      node.AssignmentSource.TempPlanMapping, node.TempPlanMapping, zeroCost);
                  planEdges.Add(assignPlanEdge);
                  node.TempPlanMapping.IncomingEdges.Add(assignPlanEdge);
  
                  if(!node.AssignmentSource.TempPlanMapping.IsPreset)
                  {
                      PlanEdge assignPlanEdgeOpposite = new PlanEdge(SearchOperationType.Assign,
                          node.TempPlanMapping, node.AssignmentSource.TempPlanMapping, zeroCost);
                      planEdges.Add(assignPlanEdgeOpposite);
                      node.AssignmentSource.TempPlanMapping.IncomingEdges.Add(assignPlanEdgeOpposite);
                  }
              }
          }
  
          public static void CreatePickMapCastAssignPlanEdges(PatternEdge edge, List<PlanEdge> planEdges, float zeroCost)
          {
              if(edge.Storage != null && edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge storAccessPlanEdge = new PlanEdge(
                      edge.StorageIndex != null ? SearchOperationType.MapWithStorageDependent : SearchOperationType.PickFromStorageDependent,
                      edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(storAccessPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(storAccessPlanEdge);
              }
              else if(edge.IndexAccess != null && edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge indexAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickFromIndexDependent,
                      edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(indexAccessPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(indexAccessPlanEdge);
              }
              else if(edge.NameLookup != null && edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge nameAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickByNameDependent,
                      edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(nameAccessPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(nameAccessPlanEdge);
              }
              else if(edge.UniqueLookup != null && edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness() != null)
              {
                  PlanEdge uniqueAccessPlanEdge = new PlanEdge(
                      SearchOperationType.PickByUniqueDependent,
                      edge.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness().TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(uniqueAccessPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(uniqueAccessPlanEdge);
              }
              else if(edge.ElementBeforeCasting != null)
              {
                  PlanEdge castPlanEdge = new PlanEdge(SearchOperationType.Cast,
                      edge.ElementBeforeCasting.TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(castPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(castPlanEdge);
              }
              else if(edge.AssignmentSource != null)
              {
                  PlanEdge assignPlanEdge = new PlanEdge(SearchOperationType.Assign,
                      edge.AssignmentSource.TempPlanMapping, edge.TempPlanMapping, zeroCost);
                  planEdges.Add(assignPlanEdge);
                  edge.TempPlanMapping.IncomingEdges.Add(assignPlanEdge);
  
                  if(!edge.AssignmentSource.TempPlanMapping.IsPreset)
                  {
                      PlanEdge assignPlanEdgeOpposite = new PlanEdge(SearchOperationType.Assign,
                          edge.TempPlanMapping, edge.AssignmentSource.TempPlanMapping, zeroCost);
                      planEdges.Add(assignPlanEdgeOpposite);
                      edge.AssignmentSource.TempPlanMapping.IncomingEdges.Add(assignPlanEdge);
                  }
              }
          }
  
          public static IEnumerable<PatternNode> NodesInIndependentMatchedThere(PatternGraph independent)
          {
              foreach(PatternNode node in independent.nodesPlusInlined)
              {
                  if(node.PointOfDefinition == independent && !node.defToBeYieldedTo)
                      yield return node;
              }
          }
  
          public static int NumNodesInIndependentsMatchedThere(PatternGraph patternGraph)
          {
              int sum = 0;
              
              foreach(PatternGraph independent in patternGraph.independentPatternGraphsPlusInlined)
              {
                  foreach(PatternNode node in independent.nodesPlusInlined)
                  {
                      if(node.PointOfDefinition == independent && !node.defToBeYieldedTo)
                          ++sum;
                  }
              }
              
              return sum;
          }
  
          public static IEnumerable<PatternEdge> EdgesInIndependentMatchedThere(PatternGraph independent)
          {
              foreach(PatternEdge edge in independent.edgesPlusInlined)
              {
                  if(edge.PointOfDefinition == independent && !edge.defToBeYieldedTo)
                      yield return edge;
              }
          }
  
          public static int NumEdgesInIndependentsMatchedThere(PatternGraph patternGraph)
          {
              int sum = 0;
              
              foreach(PatternGraph independent in patternGraph.independentPatternGraphsPlusInlined)
              {
                  foreach(PatternEdge edge in independent.edgesPlusInlined)
                  {
                      if(edge.PointOfDefinition == independent && !edge.defToBeYieldedTo)
                          ++sum;
                  }
              }
  
              return sum;
          }
  
          public static PatternNode GetSourcePlusInlined(PatternEdge edge, PatternGraph patternGraph, IDictionary<PatternNode, PatternNode> originalToInlinedIndependent)
          {
              PatternNode source = patternGraph.GetSourcePlusInlined(edge);
              if(edge.OriginalIndependentElement != null && source == null)
              {
                  PatternNode sourceOriginal = edge.OriginalIndependentElement.pointOfDefinition.GetSourcePlusInlined((PatternEdge)edge.OriginalIndependentElement);
                  if(originalToInlinedIndependent.ContainsKey(sourceOriginal))
                      source = originalToInlinedIndependent[sourceOriginal];
                  else
                      source = sourceOriginal; // not declared in independent itself, but in some parent
              }
              return source;
          }
  
          public static PatternNode GetTargetPlusInlined(PatternEdge edge, PatternGraph patternGraph, IDictionary<PatternNode, PatternNode> originalToInlinedIndependent)
          {
              PatternNode target = patternGraph.GetTargetPlusInlined(edge);
              if(edge.OriginalIndependentElement != null && target == null)
              {
                  PatternNode targetOriginal = edge.OriginalIndependentElement.pointOfDefinition.GetTargetPlusInlined((PatternEdge)edge.OriginalIndependentElement);
                  if(originalToInlinedIndependent.ContainsKey(targetOriginal))
                      target = originalToInlinedIndependent[targetOriginal];
                  else
                      target = targetOriginal; // not declared in independent itself, but in some parent
              }
              return target;
          }
  
          public static float CostIncreaseForInlinedIndependent(PatternElement elem, float cost)
          {
              // use costs a bit higher for elements from independent patterns, so they are not chosen unless they bring a real advantage
              if(elem.OriginalIndependentElement != null)
                  cost = (cost + 0.1F) * 1.1F * (cost < 10.0F ? 1.1F : 1.0F);
              return cost;
          }
  
          public static void CostDecreaseForLeavingInlinedIndependent(SearchPlanEdge planEdge)
          {
              // considerably lower the costs for operations leaving the inlined independent part, so this is done early
              if(planEdge.Target is SearchPlanEdgeNode) // we may leave the independent part only with an edge
              {
                  if(planEdge.Source.PatternElement.OriginalIndependentElement != null) // when the start is a node from an inlined independent
                  {
                      SearchPlanEdgeNode edge = (SearchPlanEdgeNode)planEdge.Target;
                      if(edge.PatternEdgeSource.PatternElement.OriginalIndependentElement != null && edge.PatternEdgeTarget.PatternElement.OriginalIndependentElement == null
                          || edge.PatternEdgeSource.PatternElement.OriginalIndependentElement == null && edge.PatternEdgeTarget.PatternElement.OriginalIndependentElement != null)
                      { // and the edge is incident to elements inside and outside of the inlined independent
                          planEdge.Cost = (float)Math.Sqrt(Math.Sqrt(planEdge.Cost));
                      }
                  }
              }
          }
  
          /// <summary>
          /// Marks the minimum spanning arborescence of a plan graph by setting the IncomingMSAEdge
          /// fields for all nodes
          /// </summary>
          /// <param name="planGraph">The plan graph to be marked</param>
          /// <param name="dumpName">Names the dump targets if dump compiler flags are set</param>
          public void MarkMinimumSpanningArborescence(PlanGraph planGraph, String dumpName)
          {
              if(DumpSearchPlan)
                  DumpPlanGraph(planGraph, dumpName, "initial");
  
              // nodes not already looked at
              Dictionary<PlanNode, bool> leftNodes = new Dictionary<PlanNode, bool>(planGraph.Nodes.Length);
              foreach(PlanNode node in planGraph.Nodes)
                  leftNodes.Add(node, true);
  
              // epoch = search run
              Dictionary<PlanPseudoNode, bool> epoch = new Dictionary<PlanPseudoNode, bool>();
              LinkedList<PlanSuperNode> superNodeStack = new LinkedList<PlanSuperNode>();
  
              // work left ?
              while(leftNodes.Count > 0)
              {
                  // get first remaining node
                  Dictionary<PlanNode, bool>.Enumerator enumerator = leftNodes.GetEnumerator();
                  enumerator.MoveNext();
                  PlanPseudoNode curNode = enumerator.Current.Key;
  
                  // start a new search run
                  epoch.Clear();
                  do
                  {
                      // next node in search run
                      epoch.Add(curNode, true);
                      if(curNode is PlanNode) leftNodes.Remove((PlanNode) curNode);
  
                      // cheapest incoming edge of current node
                      float cost;
                      PlanEdge cheapestEdge = curNode.GetCheapestIncoming(curNode, out cost);
                      if(cheapestEdge == null)
                          break;
                      curNode.IncomingMSAEdge = cheapestEdge;
  
                      // cycle found ?
                      while(epoch.ContainsKey(cheapestEdge.Source.TopNode))
                      {
                          // contract the cycle to a super node
                          PlanSuperNode superNode = new PlanSuperNode(cheapestEdge.Source.TopNode);
                          superNodeStack.AddFirst(superNode);
                          epoch.Add(superNode, true);
                          if(superNode.IncomingMSAEdge == null)
                              goto exitSecondLoop;
                          // continue with new super node as current node
                          curNode = superNode;
                          cheapestEdge = curNode.IncomingMSAEdge;
                      }
                      curNode = cheapestEdge.Source.TopNode;
                  }
                  while(true);
  exitSecondLoop: ;
              }
  
              if(DumpSearchPlan)
              {
                  DumpPlanGraph(planGraph, dumpName, "contracted");
                  DumpContractedPlanGraph(planGraph, dumpName);
              }
  
              // breaks all cycles represented by setting the incoming msa edges of the 
              // representative nodes to the incoming msa edges according to the supernode
              /*no, not equivalent:
              foreach(PlanSuperNode superNode in superNodeStack)
                  superNode.Child.IncomingMSAEdge = superNode.IncomingMSAEdge;*/
              foreach (PlanSuperNode superNode in superNodeStack)
              {
                  PlanPseudoNode curNode = superNode.IncomingMSAEdge.Target;
                  while (curNode.SuperNode != superNode) curNode = curNode.SuperNode;
                  curNode.IncomingMSAEdge = superNode.IncomingMSAEdge;
                  if(curNode.IncomingMSAEdge == null) throw new Exception();
              }
  
              if(DumpSearchPlan)
                  DumpFinalPlanGraph(planGraph, dumpName);
          }
  
  #region Dump functions
          private String GetDumpName(PlanNode node)
          {
              if(node.NodeType == PlanNodeType.Root) return "root";
              else if(node.NodeType == PlanNodeType.Node) return "node_" + node.PatternElement.Name;
              else return "edge_" + node.PatternElement.Name;
          }
  
          public void DumpPlanGraph(PlanGraph planGraph, String dumpname, String namesuffix)
          {
              StreamWriter sw = new StreamWriter(dumpname + "-plangraph-" + namesuffix + ".vcg", false);
  
              sw.WriteLine("graph:{\ninfoname 1: \"Attributes\"\ndisplay_edge_labels: no\nport_sharing: no\nsplines: no\n"
                  + "\nmanhattan_edges: no\nsmanhattan_edges: no\norientation: bottom_to_top\nedges: yes\nnodes:yes\nclassname 1: \"normal\"");
              sw.WriteLine("node:{title:\"root\" label:\"ROOT\"}\n");
  
              sw.WriteLine("graph:{{title:\"pattern\" label:\"{0}\" status:clustered color:lightgrey", dumpname);
  
              foreach(PlanNode node in planGraph.Nodes)
              {
                  DumpNode(sw, node);
              }
              foreach(PlanEdge edge in planGraph.Edges)
              {
                  DumpEdge(sw, edge, true);
              }
              sw.WriteLine("}\n}\n");
              sw.Close();
          }
  
          private void DumpNode(StreamWriter sw, PlanNode node)
          {
              if(node.NodeType == PlanNodeType.Edge)
                  sw.WriteLine("node:{{title:\"{0}\" label:\"{1} : {2}\" shape:ellipse}}",
                      GetDumpName(node), node.PatternElement.TypeID, node.PatternElement.Name);
              else
                  sw.WriteLine("node:{{title:\"{0}\" label:\"{1} : {2}\"}}",
                      GetDumpName(node), node.PatternElement.TypeID, node.PatternElement.Name);
          }
  
          private void DumpEdge(StreamWriter sw, PlanEdge edge, bool markRed)
          {
              String typeStr = " #";
              switch(edge.Type)
              {
                  case SearchOperationType.Outgoing: typeStr = "--"; break;
                  case SearchOperationType.Incoming: typeStr = "->"; break;
                  case SearchOperationType.Incident: typeStr = "<->"; break;
                  case SearchOperationType.ImplicitSource: typeStr = "IS"; break;
                  case SearchOperationType.ImplicitTarget: typeStr = "IT"; break;
                  case SearchOperationType.Implicit: typeStr = "IM"; break;
                  case SearchOperationType.Lookup: typeStr = " *"; break;
                  case SearchOperationType.ActionPreset: typeStr = " p"; break;
                  case SearchOperationType.NegIdptPreset: typeStr = "np"; break;
                  case SearchOperationType.SubPreset: typeStr = "sp"; break;
              }
  
              sw.WriteLine("edge:{{sourcename:\"{0}\" targetname:\"{1}\" label:\"{2} / {3:0.00} ({4:0.00}) \"{5}}}",
                  GetDumpName(edge.Source), GetDumpName(edge.Target), typeStr, edge.mstCost, edge.Cost,
                  markRed ? " color:red" : "");
          }
  
          private void DumpSuperNode(StreamWriter sw, PlanSuperNode superNode, Dictionary<PlanSuperNode, bool> dumpedSuperNodes)
          {
              PlanPseudoNode curNode = superNode.Child;
              sw.WriteLine("graph:{title:\"super node\" label:\"super node\" status:clustered color:lightgrey");
              dumpedSuperNodes.Add(superNode, true);
              do
              {
                  if(curNode is PlanSuperNode)
                  {
                      DumpSuperNode(sw, (PlanSuperNode) curNode, dumpedSuperNodes);
                      DumpEdge(sw, curNode.IncomingMSAEdge, true);
                  }
                  else
                  {
                      DumpNode(sw, (PlanNode) curNode);
                      DumpEdge(sw, curNode.IncomingMSAEdge, false);
                  }
                  curNode = curNode.IncomingMSAEdge.Source;
                  while(curNode.SuperNode != null && curNode.SuperNode != superNode)
                      curNode = curNode.SuperNode;
              }
              while(curNode != superNode.Child);
              sw.WriteLine("}");
          }
  
          private void DumpContractedPlanGraph(PlanGraph planGraph, String dumpname)
          {
              StreamWriter sw = new StreamWriter(dumpname + "-contractedplangraph.vcg", false);
  
              sw.WriteLine("graph:{\ninfoname 1: \"Attributes\"\ndisplay_edge_labels: no\nport_sharing: no\nsplines: no\n"
                  + "\nmanhattan_edges: no\nsmanhattan_edges: no\norientation: bottom_to_top\nedges: yes\nnodes:yes\nclassname 1: \"normal\"");
              sw.WriteLine("node:{title:\"root\" label:\"ROOT\"}\n");
  
              sw.WriteLine("graph:{{title:\"pattern\" label:\"{0}\" status:clustered color:lightgrey", dumpname);
  
              Dictionary<PlanSuperNode, bool> dumpedSuperNodes = new Dictionary<PlanSuperNode, bool>();
  
              foreach(PlanNode node in planGraph.Nodes)
              {
                  PlanSuperNode superNode = node.TopSuperNode;
                  if(superNode != null)
                  {
                      if(dumpedSuperNodes.ContainsKey(superNode)) continue;
                      DumpSuperNode(sw, superNode, dumpedSuperNodes);
                      DumpEdge(sw, superNode.IncomingMSAEdge, true);
                  }
                  else
                  {
                      DumpNode(sw, node);
                      DumpEdge(sw, node.IncomingMSAEdge, false);
                  }
              }
  
              sw.WriteLine("}\n}");
              sw.Close();
          }
  
          private void DumpFinalPlanGraph(PlanGraph planGraph, String dumpname)
          {
              StreamWriter sw = new StreamWriter(dumpname + "-finalplangraph.vcg", false);
  
              sw.WriteLine("graph:{\ninfoname 1: \"Attributes\"\ndisplay_edge_labels: no\nport_sharing: no\nsplines: no\n"
                  + "\nmanhattan_edges: no\nsmanhattan_edges: no\norientation: bottom_to_top\nedges: yes\nnodes:yes\nclassname 1: \"normal\"");
              sw.WriteLine("node:{title:\"root\" label:\"ROOT\"}\n");
  
              sw.WriteLine("graph:{{title:\"pattern\" label:\"{0}\" status:clustered color:lightgrey", dumpname);
  
              foreach(PlanNode node in planGraph.Nodes)
              {
                  DumpNode(sw, node);
                  DumpEdge(sw, node.IncomingMSAEdge, false);
              }
  
              sw.WriteLine("}\n}");
              sw.Close();
          }
  
          private String GetDumpName(SearchPlanNode node)
          {
              if(node.NodeType == PlanNodeType.Root) return "root";
              else if(node.NodeType == PlanNodeType.Node) return "node_" + node.PatternElement.Name;
              else return "edge_" + node.PatternElement.Name;
          }
  
          private void DumpNode(StreamWriter sw, SearchPlanNode node)
          {
              if(node.NodeType == PlanNodeType.Edge)
                  sw.WriteLine("node:{{title:\"{0}\" label:\"{1} : {2}\" shape:ellipse}}",
                      GetDumpName(node), node.PatternElement.TypeID, node.PatternElement.Name);
              else
                  sw.WriteLine("node:{{title:\"{0}\" label:\"{1} : {2}\"}}",
                      GetDumpName(node), node.PatternElement.TypeID, node.PatternElement.Name);
          }
  
          private void DumpEdge(StreamWriter sw, SearchOperationType opType, SearchPlanNode source, SearchPlanNode target, float cost, bool markRed)
          {
              String typeStr = " #";
              switch(opType)
              {
                  case SearchOperationType.Outgoing: typeStr = "--"; break;
                  case SearchOperationType.Incoming: typeStr = "->"; break;
                  case SearchOperationType.Incident: typeStr = "<->"; break;
                  case SearchOperationType.ImplicitSource: typeStr = "IS"; break;
                  case SearchOperationType.ImplicitTarget: typeStr = "IT"; break;
                  case SearchOperationType.Implicit: typeStr = "IM"; break;
                  case SearchOperationType.Lookup: typeStr = " *"; break;
                  case SearchOperationType.ActionPreset: typeStr = " p"; break;
                  case SearchOperationType.NegIdptPreset: typeStr = "np"; break;
                  case SearchOperationType.SubPreset: typeStr = "sp"; break;
              }
  
              sw.WriteLine("edge:{{sourcename:\"{0}\" targetname:\"{1}\" label:\"{2} / {3:0.00}\"{4}}}",
                  GetDumpName(source), GetDumpName(target), typeStr, cost, markRed ? " color:red" : "");
          }
  
          private void DumpScheduledSearchPlan(ScheduledSearchPlan ssp, String dumpname)
          {
              StreamWriter sw = new StreamWriter(dumpname + "-scheduledsp.txt", false);
              SourceBuilder sb = new SourceBuilder();
              ssp.Explain(sb, model);
              sb.Append("\n");
              sw.WriteLine(sb.ToString());
              sw.Close();
  
  /*            StreamWriter sw = new StreamWriter(dumpname + "-scheduledsp.vcg", false);
  
              sw.WriteLine("graph:{\ninfoname 1: \"Attributes\"\ndisplay_edge_labels: no\nport_sharing: no\nsplines: no\n"
                  + "\nmanhattan_edges: no\nsmanhattan_edges: no\norientation: bottom_to_top\nedges: yes\nnodes: yes\nclassname 1: \"normal\"");
              sw.WriteLine("node:{title:\"root\" label:\"ROOT\"}\n");
              SearchPlanNode root = new SearchPlanNode("root");
  
              sw.WriteLine("graph:{{title:\"pattern\" label:\"{0}\" status:clustered color:lightgrey", dumpname);
  
              foreach(SearchOperation op in ssp.Operations)
              {
                  switch(op.Type)
                  {
                      case SearchOperationType.Lookup:
                      case SearchOperationType.Incoming:
                      case SearchOperationType.Outgoing:
                      case SearchOperationType.ImplicitSource:
                      case SearchOperationType.ImplicitTarget:
                      {
                          SearchPlanNode spnode = (SearchPlanNode) op.Element;
                          DumpNode(sw, spnode);
                          SearchPlanNode src;
                          switch(op.Type)
                          {
                              case SearchOperationType.Lookup:
                              case SearchOperationType.ActionPreset:
                              case SearchOperationType.NegPreset:
                                  src = root;
                                  break;
                              default:
                                  src = op.SourceSPNode;
                                  break;
                          }
                          DumpEdge(sw, op.Type, src, spnode, op.CostToEnd, false);
                          break;
                      }
                      case SearchOperationType.Condition:
                          sw.WriteLine("node:{title:\"Condition\" label:\"CONDITION\"}\n");
                          break;
                      case SearchOperationType.NegativePattern:
                          sw.WriteLine("node:{title:\"NAC\" label:\"NAC\"}\n");
                          break;
                  }
              }*/
          }
  #endregion Dump functions
  
          /// <summary>
          /// Generate search plan graph out of the plan graph,
          /// search plan graph only contains edges chosen by the MSA algorithm.
          /// Edges in search plan graph are given in the nodes by outgoing list, as needed for scheduling,
          /// in contrast to incoming list in plan graph, as needed for MSA computation.
          /// </summary>
          /// <param name="planGraph">The source plan graph</param>
          /// <returns>A new search plan graph</returns>
          public SearchPlanGraph GenerateSearchPlanGraph(PlanGraph planGraph)
          {
              SearchPlanNode searchPlanRoot = new SearchPlanNode("search plan root");
              SearchPlanNode[] searchPlanNodes = new SearchPlanNode[planGraph.Nodes.Length];
              SearchPlanEdge[] searchPlanEdges = new SearchPlanEdge[planGraph.Nodes.Length - 1 + 1]; // +1 for root
              Dictionary<PlanNode, SearchPlanNode> planToSearchPlanNode = // for generating edges
                  new Dictionary<PlanNode, SearchPlanNode>(planGraph.Nodes.Length);
              planToSearchPlanNode.Add(planGraph.Root, searchPlanRoot);
  
              // generate the search plan graph nodes, same as plan graph nodes,
              // representing pattern graph nodes and edges
              int i = 0;
              foreach(PlanNode planNode in planGraph.Nodes)
              {
                  if(planNode.NodeType == PlanNodeType.Edge)
                      searchPlanNodes[i] = new SearchPlanEdgeNode(planNode, null, null);
                  else
                      searchPlanNodes[i] = new SearchPlanNodeNode(planNode);
                  planToSearchPlanNode.Add(planNode, searchPlanNodes[i]);
  
                  ++i;
              }
  
              // generate the search plan graph edges, 
              // that are the plan graph edges chosen by the MSA algorithm, in reversed direction
              // and add references to originating pattern elements
              i = 0;
              foreach(PlanNode planNode in planGraph.Nodes)
              {
                  PlanEdge planEdge = planNode.IncomingMSAEdge;
                  searchPlanEdges[i] = new SearchPlanEdge(planEdge.Type, planToSearchPlanNode[planEdge.Source], planToSearchPlanNode[planEdge.Target], planEdge.Cost);
                  planToSearchPlanNode[planEdge.Source].OutgoingEdges.Add(searchPlanEdges[i]);
  
                  if(planNode.NodeType == PlanNodeType.Edge)
                  {
                      SearchPlanEdgeNode searchPlanEdgeNode = (SearchPlanEdgeNode) planToSearchPlanNode[planNode];
                      SearchPlanNode patElem;
                      if(planEdge.Target.PatternEdgeSource != null 
                          && planToSearchPlanNode.TryGetValue(planEdge.Target.PatternEdgeSource, out patElem))
                      {
                          searchPlanEdgeNode.PatternEdgeSource = (SearchPlanNodeNode) patElem;
                          searchPlanEdgeNode.PatternEdgeSource.OutgoingPatternEdges.Add(searchPlanEdgeNode);
                      }
                      if(planEdge.Target.PatternEdgeTarget != null 
                          && planToSearchPlanNode.TryGetValue(planEdge.Target.PatternEdgeTarget, out patElem))
                      {
                          searchPlanEdgeNode.PatternEdgeTarget = (SearchPlanNodeNode) patElem;
                          searchPlanEdgeNode.PatternEdgeTarget.IncomingPatternEdges.Add(searchPlanEdgeNode);
                      }
                  }
  
                  ++i;
              }
  
              return new SearchPlanGraph(searchPlanRoot, searchPlanNodes, searchPlanEdges);
          }
  
          /// <summary>
          /// Generates a scheduled search plan for a given search plan graph
          /// </summary>
          public ScheduledSearchPlan ScheduleSearchPlan(SearchPlanGraph spGraph,
              PatternGraph patternGraph, bool isNegativeOrIndependent)
          {
              // the schedule
              List<SearchOperation> operations = new List<SearchOperation>();
              
              // a set of search plan edges representing the currently reachable not yet visited elements
              PriorityQueue<SearchPlanEdge> activeEdges = new PriorityQueue<SearchPlanEdge>();
  
              // first schedule all preset elements
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Target.IsPreset && edge.Type != SearchOperationType.DefToBeYieldedTo)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPresetElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPresetElement);
  
                      // note: here a normal preset is converted into a neg/idpt preset operation if in negative/independent pattern
                      SearchOperation newOp = new SearchOperation(
                          isNegativeOrIndependent ? SearchOperationType.NegIdptPreset : edge.Type,
                          edge.Target, spGraph.Root, 0);
                      operations.Add(newOp);
                  }
              }
  
              // then schedule the initialization of all def to be yielded to elements and variables,
              // must come after the preset elements, as they may be used in the def initialization
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.DefToBeYieldedTo
                      && (!isNegativeOrIndependent || (edge.Target.PatternElement.pointOfDefinition == patternGraph && edge.Target.PatternElement.originalElement==null)))
                  {
                      SearchOperation newOp = new SearchOperation(
                          SearchOperationType.DefToBeYieldedTo,
                          edge.Target, spGraph.Root, 0);
                      newOp.Expression = edge.Target.PatternElement.Initialization;
                      operations.Add(newOp);
                  }
              }
              foreach(PatternVariable var in patternGraph.variablesPlusInlined)
              {
                  if(var.defToBeYieldedTo
                      && (!isNegativeOrIndependent || var.pointOfDefinition == patternGraph && var.originalVariable == null))
                  {
                      SearchOperation newOp = new SearchOperation(
                          SearchOperationType.DefToBeYieldedTo,
                          var, spGraph.Root, 0);
                      newOp.Expression = var.initialization;
                      operations.Add(newOp);
                  }
              }
  
              // then schedule all map with storage / pick from index / pick from storage / pick from name index elements not depending on other elements
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.MapWithStorage)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPickedElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPickedElement);
  
                      SearchOperation newOp = new SearchOperation(edge.Type,
                          edge.Target, spGraph.Root, 0);
                      newOp.Storage = edge.Target.PatternElement.Storage;
                      newOp.StorageIndex = edge.Target.PatternElement.StorageIndex;
                      operations.Add(newOp);
                  }
              }
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.PickFromStorage)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPickedElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPickedElement);
  
                      SearchOperation newOp = new SearchOperation(edge.Type,
                          edge.Target, spGraph.Root, 0);
                      newOp.Storage = edge.Target.PatternElement.Storage;
                      operations.Add(newOp);
                  }
              }
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.PickFromIndex)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPickedElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPickedElement);
  
                      SearchOperation newOp = new SearchOperation(edge.Type,
                          edge.Target, spGraph.Root, 0);
                      newOp.IndexAccess = edge.Target.PatternElement.IndexAccess;
                      operations.Add(newOp);
                  }
              }
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.PickByName)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPickedElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPickedElement);
  
                      SearchOperation newOp = new SearchOperation(edge.Type,
                          edge.Target, spGraph.Root, 0);
                      newOp.NameLookup = edge.Target.PatternElement.NameLookup;
                      operations.Add(newOp);
                  }
              }
              foreach(SearchPlanEdge edge in spGraph.Root.OutgoingEdges)
              {
                  if(edge.Type == SearchOperationType.PickByUnique)
                  {
                      foreach(SearchPlanEdge edgeOutgoingFromPickedElement in edge.Target.OutgoingEdges)
                          activeEdges.Add(edgeOutgoingFromPickedElement);
  
                      SearchOperation newOp = new SearchOperation(edge.Type,
                          edge.Target, spGraph.Root, 0);
                      newOp.UniqueLookup = edge.Target.PatternElement.UniqueLookup;
                      operations.Add(newOp);
                  }
              }
  
              // iterate over all reachable elements until the whole graph has been scheduled(/visited),
              // choose next cheapest operation, update the reachable elements and the search plan costs
              SearchPlanNode lastNode = spGraph.Root;
              for(int i = 0; i < spGraph.Nodes.Length - spGraph.NumPresetElements - spGraph.NumIndependentStorageIndexElements; ++i)
              {
                  foreach(SearchPlanEdge edge in lastNode.OutgoingEdges)
                  {
                      if(edge.Target.IsPreset)
                          continue;
                      if(edge.Target.PatternElement.Storage != null 
                          && edge.Target.PatternElement.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness()==null)
                          continue;
                      if(edge.Target.PatternElement.IndexAccess != null
                          && edge.Target.PatternElement.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness()==null)
                          continue;
                      if(edge.Target.PatternElement.NameLookup != null
                          && edge.Target.PatternElement.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness()==null)
                          continue;
                      if(edge.Target.PatternElement.UniqueLookup != null
                          && edge.Target.PatternElement.GetPatternElementThisElementDependsOnOutsideOfGraphConnectedness()==null)
                          continue;
                      CostDecreaseForLeavingInlinedIndependent(edge);
                      activeEdges.Add(edge);
                  }
  
                  SearchPlanEdge minEdge = activeEdges.DequeueFirst();
                  lastNode = minEdge.Target;
  
                  SearchOperation newOp = new SearchOperation(minEdge.Type,
                      lastNode, minEdge.Source, minEdge.Cost);
                  newOp.Storage = minEdge.Target.PatternElement.Storage;
                  newOp.StorageIndex = minEdge.Target.PatternElement.StorageIndex;
                  newOp.IndexAccess = minEdge.Target.PatternElement.IndexAccess;
                  newOp.NameLookup = minEdge.Target.PatternElement.NameLookup;
                  newOp.UniqueLookup = minEdge.Target.PatternElement.UniqueLookup;
  
                  foreach(SearchOperation op in operations)
                      op.CostToEnd += minEdge.Cost;
  
                  operations.Add(newOp);
              }
  
              // remove the elements stemming from inlined independents
              // they were added in the hope that they might help in matching this pattern,
              // they don't if they are matched after the elements of this pattern (in fact they only increase the costs then)
              RemoveInlinedIndependentElementsAtEnd(operations);
  
              // insert inlined element identity check into the schedule in case neither of the possible assignments was scheduled
              InsertInlinedElementIdentityCheckIntoSchedule(patternGraph, operations);
  
              // insert inlined variable assignments into the schedule
              InsertInlinedVariableAssignmentsIntoSchedule(patternGraph, operations);
  
              // insert conditions into the schedule
              InsertConditionsIntoSchedule(patternGraph.ConditionsPlusInlined, operations);
  
              float cost = operations.Count > 0 ? operations[0].CostToEnd : 0;
              return new ScheduledSearchPlan(patternGraph, operations.ToArray(), cost);
          }
  
          private void RemoveInlinedIndependentElementsAtEnd(List<SearchOperation> operations)
          {
              while(operations.Count > 0 &&
                  IsOperationAnInlinedIndependentElement(operations[operations.Count - 1]))
              {
                  foreach(SearchOperation op in operations)
                      op.CostToEnd -= operations[operations.Count - 1].CostToEnd;
  
                  operations.RemoveAt(operations.Count-1);
              }
          }
  
          private bool IsOperationAnInlinedIndependentElement(SearchOperation so)
          {
              if(so.Element is SearchPlanNode)
                  if(((SearchPlanNode)so.Element).PatternElement.OriginalIndependentElement != null)
                      return true;
  
              return false;
          }
  
          private void InsertInlinedElementIdentityCheckIntoSchedule(PatternGraph patternGraph, List<SearchOperation> operations)
          {
              for(int i = 0; i < operations.Count; ++i)
              {
                  PatternElement assignmentSource = null;
                  if(operations[i].Element is SearchPlanNode)
                      assignmentSource = ((SearchPlanNode)operations[i].Element).PatternElement.AssignmentSource;
                  if(assignmentSource != null && operations[i].Type != SearchOperationType.Identity)
                  {
                      for(int j = 0; j < operations.Count; ++j)
                      {
                          SearchPlanNode binder = null;
                          if(operations[j].Element is SearchPlanNode)
                              binder = (SearchPlanNode)operations[j].Element;
                          if(binder != null 
                              && binder.PatternElement == assignmentSource
                              && operations[j].Type != SearchOperationType.Identity)
                          {
                              if(operations[i].Type != SearchOperationType.Assign 
                                  && operations[j].Type != SearchOperationType.Assign)
                              {
                                  int indexOfSecond = Math.Max(i, j);
                                  SearchOperation so = new SearchOperation(SearchOperationType.Identity,
                                      operations[i].Element, binder, operations[indexOfSecond].CostToEnd);
                                  operations.Insert(indexOfSecond + 1, so);
                                  break;
                              }
                          }
                      }
                  }
              }
          }
  
          /// <summary>
          /// Appends homomorphy information to each operation of the scheduled search plan
          /// </summary>
          public void AppendHomomorphyInformation(ScheduledSearchPlan ssp)
          {
              // no operation -> nothing which could be homomorph
              if(ssp.Operations.Length == 0)
              {
                  return;
              }
  
              // iterate operations of the search plan to append homomorphy checks
              for(int i = 0; i < ssp.Operations.Length; ++i)
              {
                  if(ssp.Operations[i].Type == SearchOperationType.Condition
                      || ssp.Operations[i].Type == SearchOperationType.AssignVar
                      || ssp.Operations[i].Type == SearchOperationType.DefToBeYieldedTo
                      || ssp.Operations[i].Type == SearchOperationType.InlinedIndependentCheckForDuplicateMatch)
                  {
                      continue;
                  }
  
                  if(ssp.Operations[i].Type == SearchOperationType.NegativePattern)
                  {
                      AppendHomomorphyInformation((ScheduledSearchPlan)ssp.Operations[i].Element);
                      continue;
                  }
  
                  if(ssp.Operations[i].Type == SearchOperationType.IndependentPattern)
                  {
                      AppendHomomorphyInformation((ScheduledSearchPlan)ssp.Operations[i].Element);
                      continue;
                  }
  
                  DetermineAndAppendHomomorphyChecks(ssp, i);
              }
          }
  
          /// <summary>
          /// Determines which homomorphy check operations are necessary 
          /// at the operation of the given position within the scheduled search plan
          /// and appends them.
          /// </summary>
          public void DetermineAndAppendHomomorphyChecks(ScheduledSearchPlan ssp, int j)
          {
              // take care of global homomorphy
              FillInGlobalHomomorphyPatternElements(ssp, j);
          
              ///////////////////////////////////////////////////////////////////////////
              // first handle special case pure homomorphy
  
              SearchPlanNode spn_j = (SearchPlanNode)ssp.Operations[j].Element;
  
              if(spn_j.ElementID == -1)
              {
                  // inlined from independent for better matching, independent from the rest
                  return;
              }
  
              bool homToAll = true;
              if(spn_j.NodeType == PlanNodeType.Node)
              {
                  for(int i = 0; i < ssp.PatternGraph.nodesPlusInlined.Length; ++i)
                  {
                      if(!ssp.PatternGraph.homomorphicNodes[spn_j.ElementID - 1, i])
                      {
                          homToAll = false;
                          break;
                      }
                  }
              }
              else //(spn_j.NodeType == PlanNodeType.Edge)
              {
                  for(int i = 0; i < ssp.PatternGraph.edgesPlusInlined.Length; ++i)
                  {
                      if(!ssp.PatternGraph.homomorphicEdges[spn_j.ElementID - 1, i])
                      {
                          homToAll = false;
                          break;
                      }
                  }
              }
  
              if(homToAll)
              {
                  // operation is allowed to be homomorph with everything
                  // no checks for isomorphy or restricted homomorphy needed at all
                  return;
              }
  
              ///////////////////////////////////////////////////////////////////////////
              // no pure homomorphy, so we have restricted homomorphy or isomorphy
              // and need to inspect the operations before, together with the homomorphy matrix 
              // for determining the necessary homomorphy checks
  
              GrGenType[] types;
              bool[,] hom;
  
              if(spn_j.NodeType == PlanNodeType.Node) {
                  types = model.NodeModel.Types;
                  hom = ssp.PatternGraph.homomorphicNodes;
              }
              else { // (spn_j.NodeType == PlanNodeType.Edge)
                  types = model.EdgeModel.Types;
                  hom = ssp.PatternGraph.homomorphicEdges;
              }
  
              // order operation to check against all elements it's not allowed to be homomorph to
  
              // iterate through the operations before our position
              bool homomorphyPossibleAndAllowed = false;
              for(int i = 0; i < j; ++i)
              {
                  // only check operations computing nodes or edges
                  if(ssp.Operations[i].Type == SearchOperationType.Condition
                      || ssp.Operations[i].Type == SearchOperationType.NegativePattern
                      || ssp.Operations[i].Type == SearchOperationType.IndependentPattern
                      || ssp.Operations[i].Type == SearchOperationType.Assign
                      || ssp.Operations[i].Type == SearchOperationType.AssignVar
                      || ssp.Operations[i].Type == SearchOperationType.DefToBeYieldedTo
                      || ssp.Operations[i].Type == SearchOperationType.InlinedIndependentCheckForDuplicateMatch)
                  {
                      continue;
                  }
  
                  SearchPlanNode spn_i = (SearchPlanNode)ssp.Operations[i].Element;
  
                  // don't compare nodes with edges
                  if(spn_i.NodeType != spn_j.NodeType)
                  {
                      continue;
                  }
  
                  if(spn_i.ElementID == -1)
                  {
                      // inlined from independent for better matching, independent from the rest
                      continue;
                  }
                  
                  // find out whether element types are disjoint
                  GrGenType type_i = types[spn_i.PatternElement.TypeID];
                  GrGenType type_j = types[spn_j.PatternElement.TypeID];
                  bool disjoint = true;
                  foreach(GrGenType subtype_i in type_i.SubOrSameTypes)
                  {
                      if(type_j.IsA(subtype_i) || subtype_i.IsA(type_j)) // IsA==IsSuperTypeOrSameType
                      {
                          disjoint = false;
                          break;
                      }
                  }
  
                  // don't check elements if their types are disjoint
                  if(disjoint)
                  {
                      continue;
                  }
  
                  // at this position we found out that spn_i and spn_j 
                  // might get matched to the same host graph element, i.e. homomorphy is possible
                  
                  // if that's ok we don't need to insert checks to prevent this from happening
                  if(hom[spn_i.ElementID - 1, spn_j.ElementID - 1])
                  {
                      homomorphyPossibleAndAllowed = true;
                      continue;
                  }
  
                  // otherwise the generated matcher code has to check 
                  // that pattern element j doesn't get bound to the same graph element
                  // the pattern element i is already bound to 
                  if(ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst == null) {
                      ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst = new List<SearchPlanNode>();
                  }
                  ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst.Add(spn_i);
  
                  // if spn_j might get matched to the same host graph element as spn_i and this is not allowed
                  // make spn_i set the is-matched-bit so that spn_j can detect this situation
                  ssp.Operations[i].Isomorphy.SetIsMatchedBit = true;
              }
  
              // only if elements, the operation must be isomorph to, were matched before
              // (otherwise there were only elements, the operation is allowed to be homomorph to,
              //  matched before, so no check needed here)
              if(ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst != null
                  && ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst.Count > 0)
              {
                  // order operation to check whether the is-matched-bit is set
                  ssp.Operations[j].Isomorphy.CheckIsMatchedBit = true;
              }
  
              // if no check for isomorphy was skipped due to homomorphy being allowed
              // pure isomorphy is to be guaranteed - simply check the is-matched-bit and be done
              // the pattern elements to check against are only needed 
              // if spn_j is allowed to be homomorph to some elements but must be isomorph to some others
              if(ssp.Operations[j].Isomorphy.CheckIsMatchedBit && !homomorphyPossibleAndAllowed)
              {
                  ssp.Operations[j].Isomorphy.PatternElementsToCheckAgainst = null;
              }
          }
  
          /// <summary>
          /// fill in globally homomorphic elements as exception to global isomorphy check
          /// </summary>
          public void FillInGlobalHomomorphyPatternElements(ScheduledSearchPlan ssp, int j)
          {
              SearchPlanNode spn_j = (SearchPlanNode)ssp.Operations[j].Element;
  
              if(spn_j.NodeType == PlanNodeType.Node)
              {
                  if(spn_j.ElementID == -1 // inlined from independent for better matching, independent from the rest
                      || ssp.PatternGraph.totallyHomomorphicNodes[spn_j.ElementID - 1])
                  {
                      ssp.Operations[j].Isomorphy.TotallyHomomorph = true;
                      return; // iso-exceptions to totally hom are handled with non-global iso checks
                  }
              }
              else
              {
                  if(spn_j.ElementID == -1 // inlined from independent for better matching, independent from the rest
                      || ssp.PatternGraph.totallyHomomorphicEdges[spn_j.ElementID - 1])
                  {
                      ssp.Operations[j].Isomorphy.TotallyHomomorph = true;
                      return; // iso-exceptions to totally hom are handled with non-global iso checks
                  }
              }
  
              bool[,] homGlobal;
              if(spn_j.NodeType == PlanNodeType.Node) {
                  homGlobal = ssp.PatternGraph.homomorphicNodesGlobal;
              }
              else { // (spn_j.NodeType == PlanNodeType.Edge)
                  homGlobal = ssp.PatternGraph.homomorphicEdgesGlobal;
              }
  
              // iterate through the operations before our position
              for(int i = 0; i < j; ++i)
              {
                  // only check operations computing nodes or edges
                  if(ssp.Operations[i].Type == SearchOperationType.Condition
                      || ssp.Operations[i].Type == SearchOperationType.NegativePattern
                      || ssp.Operations[i].Type == SearchOperationType.IndependentPattern
                      || ssp.Operations[i].Type == SearchOperationType.Assign 
                      || ssp.Operations[i].Type == SearchOperationType.AssignVar
                      || ssp.Operations[i].Type == SearchOperationType.DefToBeYieldedTo
                      || ssp.Operations[i].Type == SearchOperationType.InlinedIndependentCheckForDuplicateMatch)
                  {
                      continue;
                  }
  
                  SearchPlanNode spn_i = (SearchPlanNode)ssp.Operations[i].Element;
  
                  // don't compare nodes with edges
                  if(spn_i.NodeType != spn_j.NodeType)
                  {
                      continue;
                  }
  
                  if(spn_i.ElementID == -1)
                  {
                      // inlined from independent for better matching, independent from the rest
                      continue;
                  }
             
                  // in global isomorphy check at current position 
                  // allow globally homomorphic elements as exception
                  // if they were already defined(preset)
                  if(homGlobal[spn_j.ElementID - 1, spn_i.ElementID - 1])
                  {
                      if(ssp.Operations[j].Isomorphy.GloballyHomomorphPatternElements == null)
                      {
                          ssp.Operations[j].Isomorphy.GloballyHomomorphPatternElements = new List<SearchPlanNode>();
                      }
                      ssp.Operations[j].Isomorphy.GloballyHomomorphPatternElements.Add(spn_i);
                  }
              }
          }
  
          /// <summary>
          /// Negative/Independent schedules are merged as an operation into their enclosing schedules,
          /// at a position determined by their costs but not before all of their needed elements were computed
          /// </summary>
          public void MergeNegativeAndIndependentSchedulesIntoEnclosingSchedules(PatternGraph patternGraph)
          {
              foreach(PatternGraph neg in patternGraph.negativePatternGraphsPlusInlined)
              {
                  MergeNegativeAndIndependentSchedulesIntoEnclosingSchedules(neg);
              }
  
              foreach(PatternGraph idpt in patternGraph.independentPatternGraphsPlusInlined)
              {
                  MergeNegativeAndIndependentSchedulesIntoEnclosingSchedules(idpt);
              }
  
              foreach(Alternative alt in patternGraph.alternativesPlusInlined)
              {
                  foreach(PatternGraph altCase in alt.alternativeCases)
                  {
                      MergeNegativeAndIndependentSchedulesIntoEnclosingSchedules(altCase);
                  }
              }
  
              foreach(Iterated iter in patternGraph.iteratedsPlusInlined)
              {
                  MergeNegativeAndIndependentSchedulesIntoEnclosingSchedules(iter.iteratedPattern);
              }
  
              InsertNegativesAndIndependentsIntoSchedule(patternGraph);
          }
  
          /// <summary>
          /// Inserts schedules of negative and independent pattern graphs into the schedule of the enclosing pattern graph
          /// </summary>
          public void InsertNegativesAndIndependentsIntoSchedule(PatternGraph patternGraph)
          {
              for(int i=0; i<patternGraph.schedules.Length; ++i)
              {
                  InsertNegativesAndIndependentsIntoSchedule(patternGraph, i);
              }
          }
  
          /// <summary>
          /// Inserts schedules of negative and independent pattern graphs into the schedule of the enclosing pattern graph
          /// for the schedule with the given array index
          /// </summary>
          public void InsertNegativesAndIndependentsIntoSchedule(PatternGraph patternGraph, int index)
          {
              // todo: erst implicit node, dann negative/independent, auch wenn negative/independent mit erstem implicit moeglich wird
              patternGraph.schedulesIncludingNegativesAndIndependents[index] = null; // an explain might have filled this
  
              List<SearchOperation> operations = new List<SearchOperation>();
              for(int i = 0; i < patternGraph.schedules[index].Operations.Length; ++i)
                  operations.Add(patternGraph.schedules[index].Operations[i]);
  
              // nested patterns on the way to an enclosed patternpath modifier 
              // must get matched after all local nodes and edges, because they require 
              // all outer elements to be known in order to lock them for patternpath processing
              if(patternGraph.patternGraphsOnPathToEnclosedPatternpath
                  .Contains(patternGraph.pathPrefix + patternGraph.name))
              {
                  operations.Add(new SearchOperation(SearchOperationType.LockLocalElementsForPatternpath, null, null,
                      patternGraph.schedules[index].Operations.Length!=0 ? patternGraph.schedules[index].Operations[patternGraph.schedules[index].Operations.Length-1].CostToEnd : 0));
              }
  
              // iterate over all negative scheduled search plans (TODO: order?)
              for(int i = 0; i < patternGraph.negativePatternGraphsPlusInlined.Length; ++i)
              {
                  ScheduledSearchPlan negSchedule = patternGraph.negativePatternGraphsPlusInlined[i].schedulesIncludingNegativesAndIndependents[0];
                  int bestFitIndex = operations.Count;
                  float bestFitCostToEnd = 0;
  
                  // find best place in scheduled search plan for current negative pattern 
                  // during search from end of schedule forward until the first element the negative pattern is dependent on is found
                  for(int j = operations.Count - 1; j >= 0; --j)
                  {
                      SearchOperation op = operations[j];
                      if(op.Type == SearchOperationType.Condition
                          || op.Type == SearchOperationType.NegativePattern
                          || op.Type == SearchOperationType.IndependentPattern
                          || op.Type == SearchOperationType.AssignVar)
                      {
                          continue;
                      }
  
                      if(LazyNegativeIndependentConditionEvaluation)
                      {
                          break;
                      }
  
                      if(op.Type == SearchOperationType.LockLocalElementsForPatternpath
                          || op.Type == SearchOperationType.DefToBeYieldedTo)
                      {
                          break; // LockLocalElementsForPatternpath and DefToBeYieldedTo are barriers for neg/idpt
                      }
  
                      if(patternGraph.negativePatternGraphsPlusInlined[i].neededNodes.ContainsKey(((SearchPlanNode)op.Element).PatternElement.Name)
                          || patternGraph.negativePatternGraphsPlusInlined[i].neededEdges.ContainsKey(((SearchPlanNode)op.Element).PatternElement.Name))
                      {
                          break;
                      }
  
                      if(negSchedule.Cost <= op.CostToEnd)
                      {
                          // best fit as CostToEnd is monotonously growing towards operation[0]
                          bestFitIndex = j;
                          bestFitCostToEnd = op.CostToEnd;
                      }
                  }
  
                  // insert pattern at best position
                  operations.Insert(bestFitIndex, new SearchOperation(SearchOperationType.NegativePattern,
                      negSchedule, null, bestFitCostToEnd + negSchedule.Cost));
  
                  // update costs of operations before best position
                  for(int j = 0; j < bestFitIndex; ++j)
                      operations[j].CostToEnd += negSchedule.Cost;
              }
  
              // iterate over all independent scheduled search plans (TODO: order?)
              for(int i = 0; i < patternGraph.independentPatternGraphsPlusInlined.Length; ++i)
              {
                  ScheduledSearchPlan idptSchedule = patternGraph.independentPatternGraphsPlusInlined[i].schedulesIncludingNegativesAndIndependents[0];
                  int bestFitIndex = operations.Count;
                  float bestFitCostToEnd = 0;
  
                  IDictionary<PatternElement, SetValueType> presetsFromIndependentInlining = ExtractOwnElements(patternGraph.schedules[index], patternGraph.independentPatternGraphsPlusInlined[i]);
  
                  // find best place in scheduled search plan for current independent pattern 
                  // during search from end of schedule forward until the first element the independent pattern is dependent on is found
                  for(int j = operations.Count - 1; j >= 0; --j)
                  {
                      SearchOperation op = operations[j];
                      if(op.Type == SearchOperationType.Condition
                          || op.Type == SearchOperationType.NegativePattern
                          || op.Type == SearchOperationType.IndependentPattern
                          || op.Type == SearchOperationType.AssignVar)
                      {
                          continue;
                      }
  
                      if(LazyNegativeIndependentConditionEvaluation)
                      {
                          break;
                      }
  
                      if(op.Type == SearchOperationType.LockLocalElementsForPatternpath
                          || op.Type == SearchOperationType.DefToBeYieldedTo)
                      {
                          break; // LockLocalElementsForPatternpath and DefToBeYieldedTo are barriers for neg/idpt
                      }
  
                      PatternElement pe = ((SearchPlanNode)op.Element).PatternElement;
                      if(patternGraph.independentPatternGraphsPlusInlined[i].neededNodes.ContainsKey(pe.Name)
                          || patternGraph.independentPatternGraphsPlusInlined[i].neededEdges.ContainsKey(pe.Name))
                      {
                          break;
                      }
  
                      if(pe.OriginalIndependentElement != null 
                          && presetsFromIndependentInlining.ContainsKey(pe.OriginalIndependentElement))
                      {
                          break;
                      }
  
                      if(idptSchedule.Cost <= op.CostToEnd)
                      {
                          // best fit as CostToEnd is monotonously growing towards operation[0]
                          bestFitIndex = j;
                          bestFitCostToEnd = op.CostToEnd;
                      }
                  }
  
                  // insert pattern at best position
                  operations.Insert(bestFitIndex, new SearchOperation(SearchOperationType.IndependentPattern,
                      idptSchedule, null, bestFitCostToEnd + idptSchedule.Cost));
  
                  // update costs of operations before best position
                  for(int j = 0; j < bestFitIndex; ++j)
                      operations[j].CostToEnd += idptSchedule.Cost;
              }
  
              InsertInlinedIndependentCheckForDuplicateMatch(operations);
  
              float cost = operations.Count > 0 ? operations[0].CostToEnd : 0;
              patternGraph.schedulesIncludingNegativesAndIndependents[index] =
                  new ScheduledSearchPlan(patternGraph, operations.ToArray(), cost);
          }
  
          private void InsertInlinedIndependentCheckForDuplicateMatch(List<SearchOperation> operations)
          {
              bool isInlinedIndependentElementExisting = false;
              foreach(SearchOperation op in operations)
              {
                  if(IsOperationAnInlinedIndependentElement(op))
                  {
                      isInlinedIndependentElementExisting = true;
                      break;
                  }
              }
  
              if(isInlinedIndependentElementExisting)
              {
                  // insert at end of schedule, just moved ahead over negatives and independents
                  // TODO: if we can estimate condition overhead, it makes sense to move ahead over conditions, too
                  int i = operations.Count - 1;
                  while((operations[i].Type == SearchOperationType.NegativePattern
                          || operations[i].Type == SearchOperationType.IndependentPattern) && i > 0)
                  {
                      --i;
                  }
  
                  SearchOperation so = new SearchOperation(SearchOperationType.InlinedIndependentCheckForDuplicateMatch,
                      null, null, operations[i].CostToEnd);
                  operations.Insert(i + 1, so);
              }
          }
  
          /// <summary>
          /// Inserts conditions into the schedule given by the operations list at their earliest possible position
          /// todo: set/map operations are potentially expensive, 
          /// they shouldn't be insertes asap, but depending an weight, 
          /// derived from statistics over set/map size for graph elements, quiet well known for anonymous rule sets
          /// </summary>
          public void InsertConditionsIntoSchedule(PatternCondition[] conditions, List<SearchOperation> operations)
          {
              // get needed (in order to evaluate it) elements of each condition 
              Dictionary<String, bool>[] neededElements = new Dictionary<String, bool>[conditions.Length];
              for(int i = 0; i < conditions.Length; ++i)
              {
                  neededElements[i] = new Dictionary<string, bool>();
                  foreach(String neededNode in conditions[i].NeededNodes)
                      neededElements[i][neededNode] = true;
                  foreach(String neededEdge in conditions[i].NeededEdges)
                      neededElements[i][neededEdge] = true;
                  foreach(String neededVariable in conditions[i].NeededVariables)
                      neededElements[i][neededVariable] = true;
              }
  
              // iterate over all conditions
              for(int i = 0; i < conditions.Length; ++i)
              {
                  int j;
                  float costToEnd = 0;
  
                  // find leftmost place in scheduled search plan for current condition
                  // by search from end of schedule forward until the first element the condition is dependent on is found
                  for(j = operations.Count - 1; j >= 0; --j)
                  {
                      SearchOperation op = operations[j];
                      if(op.Type == SearchOperationType.Condition
                          || op.Type == SearchOperationType.NegativePattern
                          || op.Type == SearchOperationType.IndependentPattern
                          || op.Type == SearchOperationType.DefToBeYieldedTo)
                      {
                          continue;
                      }
  
                      if(LazyNegativeIndependentConditionEvaluation)
                      {
                          break;
                      }
  
                      if(op.Type == SearchOperationType.AssignVar)
                      {
                          if(neededElements[i].ContainsKey(((PatternVariable)op.Element).Name))
                          {
                              costToEnd = op.CostToEnd;
                              break;
                          }
                          continue;
                      }
  
                      if(neededElements[i].ContainsKey(((SearchPlanNode)op.Element).PatternElement.Name))
                      {
                          costToEnd = op.CostToEnd;
                          break;
                      }
                  }
  
                  operations.Insert(j + 1, new SearchOperation(SearchOperationType.Condition,
                      conditions[i], null, costToEnd));
              }
          }
  
          /// <summary>
          /// Inserts inlined variable assignments into the schedule given by the operations list at their earliest possible position
          /// </summary>
          public void InsertInlinedVariableAssignmentsIntoSchedule(PatternGraph patternGraph, List<SearchOperation> operations)
          {
              // compute the number of inlined parameter variables
              int numInlinedParameterVariables = 0;
              foreach(PatternVariable var in patternGraph.variablesPlusInlined)
              {
                  if(var.AssignmentSource != null && patternGraph.WasInlinedHere(var.originalSubpatternEmbedding))
                      ++numInlinedParameterVariables;
              }
  
              if(numInlinedParameterVariables == 0)
                  return;
  
              // get the inlined parameter variables and the elements needed in order to compute their defining expression
              Dictionary<String, bool>[] neededElements = new Dictionary<String, bool>[numInlinedParameterVariables];
              PatternVariable[] inlinedParameterVariables = new PatternVariable[numInlinedParameterVariables];
              int curInlParamVar = 0;
              foreach(PatternVariable var in patternGraph.variablesPlusInlined)
              {
                  if(var.AssignmentSource == null)
                      continue;
                  if(!patternGraph.WasInlinedHere(var.originalSubpatternEmbedding))
                      continue;
  
                  neededElements[curInlParamVar] = new Dictionary<string, bool>();
                  foreach(String neededNode in var.AssignmentDependencies.neededNodes)
                      neededElements[curInlParamVar][neededNode] = true;
                  foreach(String neededEdge in var.AssignmentDependencies.neededEdges)
                      neededElements[curInlParamVar][neededEdge] = true;
                  inlinedParameterVariables[curInlParamVar] = var;
                  
                  ++curInlParamVar;
              }
  
              // iterate over all inlined parameter variables
              for(int i = 0; i < inlinedParameterVariables.Length; ++i)
              {
                  int j;
                  float costToEnd = 0;
  
                  // find leftmost place in scheduled search plan for current assignment
                  // by search from end of schedule forward until the first element the expression assigned is dependent on is found
                  for(j = operations.Count - 1; j >= 0; --j)
                  {
                      SearchOperation op = operations[j];
                      if(op.Type == SearchOperationType.Condition
                          || op.Type == SearchOperationType.Assign
                          || op.Type == SearchOperationType.AssignVar
                          || op.Type == SearchOperationType.NegativePattern
                          || op.Type == SearchOperationType.IndependentPattern
                          || op.Type == SearchOperationType.DefToBeYieldedTo)
                      {
                          continue;
                      }
  
                      if(neededElements[i].ContainsKey(((SearchPlanNode)op.Element).PatternElement.Name))
                      {
                          costToEnd = op.CostToEnd;
                          break;
                      }
                  }
  
                  SearchOperation so = new SearchOperation(SearchOperationType.AssignVar,
                      inlinedParameterVariables[i], null, costToEnd);
                  so.Expression = inlinedParameterVariables[i].AssignmentSource;
                  operations.Insert(j + 1, so);
              }
          }
  
          /// <summary>
          /// Parallelize the scheduled search plan if it is to be parallelized.
          /// An action to be parallelized is split at the first loop into a header part and a body part,
          /// all subpatterns and nested patterns to be parallelized are switched to non- is-matched-flag-based isomorphy checking.
          /// </summary>
          public void ParallelizeAsNeeded(LGSPMatchingPattern matchingPattern)
          {
              if(matchingPattern.patternGraph.branchingFactor < 2)
                  return;
  
              if(matchingPattern is LGSPRulePattern)
              {
                  bool parallelizableLoopFound = false;
                  foreach(SearchOperation so in matchingPattern.patternGraph.schedulesIncludingNegativesAndIndependents[0].Operations)
                  {
                      if(so.Type == SearchOperationType.Lookup || so.Type == SearchOperationType.Incident
                          || so.Type == SearchOperationType.Incoming || so.Type == SearchOperationType.Outgoing
                          || so.Type == SearchOperationType.PickFromStorage || so.Type == SearchOperationType.PickFromStorageDependent
                          || so.Type == SearchOperationType.PickFromIndex || so.Type == SearchOperationType.PickFromIndexDependent)
                      {
                          parallelizableLoopFound = true;
                          break;
                      }
                  }
                  if(parallelizableLoopFound)
                      ParallelizeHeadBody((LGSPRulePattern)matchingPattern);
                  else {
                      matchingPattern.patternGraph.branchingFactor = 1;
                      Console.Error.WriteLine("Warning: " + matchingPattern.patternGraph.Name + " not parallelized as no parallelizable loop was found.");
                  }
              }
              else
              {
                  Parallelize(matchingPattern);
              }
          }
  
          /// <summary>
          /// Parallelize the scheduled search plan to the branching factor,
          /// splitting it at the first loop into a header part and a body part
          /// </summary>
          public void ParallelizeHeadBody(LGSPRulePattern rulePattern)
          {
              Debug.Assert(rulePattern.patternGraph.schedulesIncludingNegativesAndIndependents.Length == 1);
              ScheduledSearchPlan ssp = rulePattern.patternGraph.schedulesIncludingNegativesAndIndependents[0];
              
              int indexToSplitAt = 0;
              for(int i = 0; i < ssp.Operations.Length; ++i)
              {
                  SearchOperation so = ssp.Operations[i];
                  if(so.Type == SearchOperationType.Lookup || so.Type == SearchOperationType.Incident
                      || so.Type == SearchOperationType.Incoming || so.Type == SearchOperationType.Outgoing
                      || so.Type == SearchOperationType.PickFromStorage || so.Type == SearchOperationType.PickFromStorageDependent
                      || so.Type == SearchOperationType.PickFromIndex || so.Type == SearchOperationType.PickFromIndexDependent)
                  {
                      indexToSplitAt = i;
                      break;
                  }
              }
  
              rulePattern.patternGraph.parallelizedSchedule = new ScheduledSearchPlan[2];
              List<SearchOperation> headOperations = new List<SearchOperation>();
              List<SearchOperation> bodyOperations = new List<SearchOperation>();
              for(int i = 0; i < rulePattern.Inputs.Length; ++i)
              {
                  if(rulePattern.Inputs[i] is VarType) // those don't appear in the schedule, they are only extracted into the search program
                  {
                      VarType varType = (VarType)rulePattern.Inputs[i];
                      String varName = rulePattern.InputNames[i];
                      PatternVariable dummy = new PatternVariable(varType, varName, varName, i, false, null);
                      headOperations.Add(new SearchOperation(SearchOperationType.WriteParallelPresetVar,
                          dummy, null, 0));
                      bodyOperations.Add(new SearchOperation(SearchOperationType.ParallelPresetVar,
                          dummy, null, 0));
                  }
              }
              for(int i = 0; i < ssp.Operations.Length; ++i)
              {
                  SearchOperation so = ssp.Operations[i];
                  if(i < indexToSplitAt)
                  {
                      SearchOperation clone = (SearchOperation)so.Clone();
                      clone.Isomorphy.Parallel = true;
                      clone.Isomorphy.LockForAllThreads = true;
                      headOperations.Add(clone);
                      switch(so.Type)
                      {
                              // the target binding looping operations can't appear in the header, so we don't treat them here
                              // the non-target binding operations are completely handled by just adding them, happended already above
                              // the target binding non-looping operations are handled below,
                              // by parallel preset writing in the header and reading in the body
                              // with exception of def, its declaration and initializion is just re-executed in the body
                              // some presets can't appear in an action header, they are thus not taken care of
                          case SearchOperationType.ActionPreset:
                          case SearchOperationType.MapWithStorage:
                          case SearchOperationType.MapWithStorageDependent:
                          case SearchOperationType.Cast:
                          case SearchOperationType.Assign:
                          case SearchOperationType.Identity:
                          case SearchOperationType.ImplicitSource:
                          case SearchOperationType.ImplicitTarget:
                          case SearchOperationType.Implicit:
                              headOperations.Add(new SearchOperation(SearchOperationType.WriteParallelPreset,
                                  (SearchPlanNode)so.Element, so.SourceSPNode, 0));
                              bodyOperations.Add(new SearchOperation(SearchOperationType.ParallelPreset, 
                                  (SearchPlanNode)so.Element, so.SourceSPNode, 0));
                              break;
                          case SearchOperationType.AssignVar:
                              headOperations.Add(new SearchOperation(SearchOperationType.WriteParallelPresetVar,
                                  (PatternVariable)so.Element, so.SourceSPNode, 0));
                              bodyOperations.Add(new SearchOperation(SearchOperationType.ParallelPresetVar,
                                  (PatternVariable)so.Element, so.SourceSPNode, 0));
                              break;
                          case SearchOperationType.DefToBeYieldedTo:
                              bodyOperations.Add((SearchOperation)so.Clone());
                              break;
                      }                    
                  }
                  else if(i == indexToSplitAt)
                  {
                      SearchOperation cloneHead = (SearchOperation)so.Clone();
                      headOperations.Add(cloneHead);
                      SearchOperation cloneBody = (SearchOperation)so.Clone();
                      cloneBody.Isomorphy.Parallel = true;
                      bodyOperations.Add(cloneBody);
                      switch(so.Type)
                      {
                          case SearchOperationType.Lookup:
                              cloneHead.Type = SearchOperationType.SetupParallelLookup;
                              cloneBody.Type = SearchOperationType.ParallelLookup;
                              break;
                          case SearchOperationType.Incident:
                              cloneHead.Type = SearchOperationType.SetupParallelIncident;
                              cloneBody.Type = SearchOperationType.ParallelIncident;
                              break;
                          case SearchOperationType.Incoming:
                              cloneHead.Type = SearchOperationType.SetupParallelIncoming;
                              cloneBody.Type = SearchOperationType.ParallelIncoming;
                              break;
                          case SearchOperationType.Outgoing:
                              cloneHead.Type = SearchOperationType.SetupParallelOutgoing;
                              cloneBody.Type = SearchOperationType.ParallelOutgoing;
                              break;
                          case SearchOperationType.PickFromStorage:
                              cloneHead.Type = SearchOperationType.SetupParallelPickFromStorage;
                              cloneBody.Type = SearchOperationType.ParallelPickFromStorage;
                              break;
                          case SearchOperationType.PickFromStorageDependent:
                              cloneHead.Type = SearchOperationType.SetupParallelPickFromStorageDependent;
                              cloneBody.Type = SearchOperationType.ParallelPickFromStorageDependent;
                              break;
                          case SearchOperationType.PickFromIndex:
                              cloneHead.Type = SearchOperationType.SetupParallelPickFromIndex;
                              cloneBody.Type = SearchOperationType.ParallelPickFromIndex;
                              break;
                          case SearchOperationType.PickFromIndexDependent:
                              cloneHead.Type = SearchOperationType.SetupParallelPickFromIndexDependent;
                              cloneBody.Type = SearchOperationType.ParallelPickFromIndexDependent;
                              break;
                      }
                  }
                  else
                  {
                      SearchOperation clone = (SearchOperation)so.Clone();
                      clone.Isomorphy.Parallel = true;
                      bodyOperations.Add(clone);
                      if(clone.Element is PatternCondition)
                          SetNeedForParallelizedVersion((clone.Element as PatternCondition).ConditionExpression);
                  }
              }
              ScheduledSearchPlan headSsp = new ScheduledSearchPlan(
                  rulePattern.patternGraph, headOperations.ToArray(), headOperations.Count > 0 ? headOperations[0].CostToEnd : 0);
              rulePattern.patternGraph.parallelizedSchedule[0] = headSsp;
              ScheduledSearchPlan bodySsp = new ScheduledSearchPlan(
                  rulePattern.patternGraph, bodyOperations.ToArray(), bodyOperations.Count > 0 ? bodyOperations[0].CostToEnd : 0);
              rulePattern.patternGraph.parallelizedSchedule[1] = bodySsp;
              ParallelizeNegativeIndependent(bodySsp);
              ParallelizeAlternativeIterated(rulePattern.patternGraph);
              ParallelizeYielding(rulePattern.patternGraph);
          }
  
          /// <summary>
          /// Parallelize the scheduled search plan for usage from a parallelized matcher
          /// (non- is-matched-flag-based isomorphy checking)
          /// </summary>
          public void Parallelize(LGSPMatchingPattern matchingPattern)
          {
              Debug.Assert(matchingPattern.patternGraph.schedulesIncludingNegativesAndIndependents.Length == 1);
              ScheduledSearchPlan ssp = matchingPattern.patternGraph.schedulesIncludingNegativesAndIndependents[0];
              matchingPattern.patternGraph.parallelizedSchedule = new ScheduledSearchPlan[1];
              List<SearchOperation> operations = new List<SearchOperation>(ssp.Operations.Length);
              for(int i = 0; i < ssp.Operations.Length; ++i)
              {
                  SearchOperation so = ssp.Operations[i];
                  SearchOperation clone = (SearchOperation)so.Clone();
                  clone.Isomorphy.Parallel = true;
                  operations.Add(clone);
                  if(clone.Element is PatternCondition)
                      SetNeedForParallelizedVersion((clone.Element as PatternCondition).ConditionExpression);
              }
              ScheduledSearchPlan clonedSsp = new ScheduledSearchPlan(
                  matchingPattern.patternGraph, operations.ToArray(), operations.Count > 0 ? operations[0].CostToEnd : 0);
              matchingPattern.patternGraph.parallelizedSchedule[0] = clonedSsp;
              ParallelizeNegativeIndependent(clonedSsp);
              ParallelizeAlternativeIterated(matchingPattern.patternGraph);
              ParallelizeYielding(matchingPattern.patternGraph);
          }
  
          /// <summary>
          /// Non- is-matched-flag-based isomorphy checking for nested alternative cases/iterateds
          /// </summary>
          public void ParallelizeAlternativeIterated(PatternGraph patternGraph)
          {
              foreach(Alternative alt in patternGraph.alternativesPlusInlined)
              {
                  foreach(PatternGraph altCase in alt.alternativeCases)
                  {
                      ScheduledSearchPlan ssp = altCase.schedulesIncludingNegativesAndIndependents[0];
                      altCase.parallelizedSchedule = new ScheduledSearchPlan[1];
                      List<SearchOperation> operations = new List<SearchOperation>(ssp.Operations.Length);
                      for(int i = 0; i < ssp.Operations.Length; ++i)
                      {
                          SearchOperation so = ssp.Operations[i];
                          SearchOperation clone = (SearchOperation)so.Clone();
                          clone.Isomorphy.Parallel = true;
                          operations.Add(clone);
                          if(clone.Element is PatternCondition)
                              SetNeedForParallelizedVersion((clone.Element as PatternCondition).ConditionExpression);
                      }
                      ScheduledSearchPlan clonedSsp = new ScheduledSearchPlan(
                          altCase, operations.ToArray(), operations.Count > 0 ? operations[0].CostToEnd : 0);
                      altCase.parallelizedSchedule[0] = clonedSsp;
  
                      ParallelizeNegativeIndependent(clonedSsp);
                      ParallelizeAlternativeIterated(altCase);
                      ParallelizeYielding(altCase);
                  }
              }
              foreach(Iterated iter in patternGraph.iteratedsPlusInlined)
              {
                  ScheduledSearchPlan ssp = iter.iteratedPattern.schedulesIncludingNegativesAndIndependents[0];
                  iter.iteratedPattern.parallelizedSchedule = new ScheduledSearchPlan[1];
                  List<SearchOperation> operations = new List<SearchOperation>(ssp.Operations.Length);
                  for(int i = 0; i < ssp.Operations.Length; ++i)
                  {
                      SearchOperation so = ssp.Operations[i];
                      SearchOperation clone = (SearchOperation)so.Clone();
                      clone.Isomorphy.Parallel = true;
                      operations.Add(clone);
                      if(clone.Element is PatternCondition)
                          SetNeedForParallelizedVersion((clone.Element as PatternCondition).ConditionExpression);
                  }
                  ScheduledSearchPlan clonedSsp = new ScheduledSearchPlan(
                          iter.iteratedPattern, operations.ToArray(), operations.Count > 0 ? operations[0].CostToEnd : 0);
                  iter.iteratedPattern.parallelizedSchedule[0] = clonedSsp;
  
                  ParallelizeNegativeIndependent(clonedSsp);
                  ParallelizeAlternativeIterated(iter.iteratedPattern);
                  ParallelizeYielding(iter.iteratedPattern);
              }
          }
  
          /// <summary>
          /// Non- is-matched-flag-based isomorphy checking for nested negatives/independents, 
          /// patch into already cloned parallel ssp
          /// </summary>
          public void ParallelizeNegativeIndependent(ScheduledSearchPlan ssp)
          {
              foreach(SearchOperation so in ssp.Operations)
              {
                  so.Isomorphy.Parallel = true;
  
                  if(so.Type == SearchOperationType.NegativePattern
                      || so.Type == SearchOperationType.IndependentPattern)
                  {
                      ScheduledSearchPlan nestedSsp = (ScheduledSearchPlan)so.Element;
                      List<SearchOperation> operations = new List<SearchOperation>(nestedSsp.Operations.Length);
                      for(int i = 0; i < nestedSsp.Operations.Length; ++i)
                      {
                          SearchOperation nestedSo = nestedSsp.Operations[i];
                          SearchOperation clone = (SearchOperation)nestedSo.Clone();
                          operations.Add(clone);
                          if(clone.Element is PatternCondition)
                              SetNeedForParallelizedVersion((clone.Element as PatternCondition).ConditionExpression);
                      }
                      Debug.Assert(nestedSsp.PatternGraph.parallelizedSchedule == null); // may fire in case explain was used before, ignore it then
                      nestedSsp.PatternGraph.parallelizedSchedule = new ScheduledSearchPlan[1];
                      ScheduledSearchPlan clonedSsp = new ScheduledSearchPlan(
                          nestedSsp.PatternGraph, operations.ToArray(), operations.Count > 0 ? operations[0].CostToEnd : 0);
                      nestedSsp.PatternGraph.parallelizedSchedule[0] = clonedSsp;
                      so.Element = clonedSsp;
  
                      ParallelizeNegativeIndependent(clonedSsp);
                      ParallelizeAlternativeIterated(nestedSsp.PatternGraph);
                      if(so.Type == SearchOperationType.IndependentPattern)
                          ParallelizeYielding(nestedSsp.PatternGraph);
                  }
              }
          }
  
          public void ParallelizeYielding(PatternGraph patternGraph)
          {
              patternGraph.parallelizedYieldings = new PatternYielding[patternGraph.YieldingsPlusInlined.Length];
              for(int i = 0; i < patternGraph.YieldingsPlusInlined.Length; ++i)
              {
                  patternGraph.parallelizedYieldings[i] = (PatternYielding)patternGraph.YieldingsPlusInlined[i].Clone();
                  for(int j = 0; j < patternGraph.parallelizedYieldings[i].ElementaryYieldings.Length; ++j)
                  {
                      SetNeedForParallelizedVersion(patternGraph.parallelizedYieldings[i].ElementaryYieldings[j]);
                  }
              }
          }
  
          public void SetNeedForParallelizedVersion(ExpressionOrYielding expyield)
          {
              expyield.SetNeedForParallelizedVersion(true);
              foreach(ExpressionOrYielding child in expyield)
              {
                  SetNeedForParallelizedVersion(child);
              }
          }
  
          public static void SetNeedForProfiling(ExpressionOrYielding expyield)
          {
              expyield.SetNeedForProfiling(true);
              foreach(ExpressionOrYielding child in expyield)
              {
                  SetNeedForProfiling(child);
              }
          }
  
          /// <summary>
          /// Generates the action interface plus action implementation including the matcher source code 
          /// for the given rule pattern into the given source builder
          /// </summary>
          public void GenerateActionAndMatcher(SourceBuilder sb,
              LGSPMatchingPattern matchingPattern, bool isInitialStatic)
          {
              // generate the search program out of the schedule(s) within the pattern graph of the rule
              SearchProgram searchProgram = GenerateSearchProgram(matchingPattern);
  
              // generate the parallelized search program out of the parallelized schedule(s) within the pattern graph of the rule
              SearchProgram searchProgramParallelized = GenerateParallelizedSearchProgramAsNeeded(matchingPattern);
  
              // emit matcher class head, body, tail; body is source code representing search program
              if(matchingPattern is LGSPRulePattern) {
                  GenerateActionInterface(sb, (LGSPRulePattern)matchingPattern); // generate the exact action interface
                  GenerateMatcherClassHeadAction(sb, (LGSPRulePattern)matchingPattern, isInitialStatic, searchProgram);
                  searchProgram.Emit(sb);
                  if(searchProgramParallelized != null)
                      searchProgramParallelized.Emit(sb);
                  GenerateActionImplementation(sb, (LGSPRulePattern)matchingPattern);
                  GenerateMatcherClassTail(sb, matchingPattern.PatternGraph.Package != null);
              } else {
                  GenerateMatcherClassHeadSubpattern(sb, matchingPattern, isInitialStatic);
                  searchProgram.Emit(sb);
                  if(searchProgramParallelized != null)
                      searchProgramParallelized.Emit(sb);
                  GenerateMatcherClassTail(sb, matchingPattern.PatternGraph.Package != null);
              }
  
              // finally generate matcher source for all the nested alternatives or iterateds of the pattern graph
              // nested inside the alternatives,iterateds,negatives,independents
              foreach(Alternative alt in matchingPattern.patternGraph.alternativesPlusInlined)
              {
                  GenerateActionAndMatcherOfAlternative(sb, matchingPattern, alt, isInitialStatic);
              }
              foreach (Iterated iter in matchingPattern.patternGraph.iteratedsPlusInlined)
              {
                  GenerateActionAndMatcherOfIterated(sb, matchingPattern, iter.iteratedPattern, isInitialStatic);
              }
              foreach (PatternGraph neg in matchingPattern.patternGraph.negativePatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, neg, isInitialStatic);
              }
              foreach (PatternGraph idpt in matchingPattern.patternGraph.independentPatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, idpt, isInitialStatic);
              }
          }
  
          /// <summary>
          /// Generates the action interface plus action implementation including the matcher source code 
          /// for the given alternative into the given source builder
          /// </summary>
          public void GenerateActionAndMatcherOfAlternative(SourceBuilder sb,
              LGSPMatchingPattern matchingPattern, Alternative alt, bool isInitialStatic)
          {
              // generate the search program out of the schedules within the pattern graphs of the alternative cases
              SearchProgram searchProgram = GenerateSearchProgramAlternative(matchingPattern, alt);
  
              // generate the parallelized search program out of the parallelized schedules within the pattern graphs of the alternative cases
              SearchProgram searchProgramParallelized = GenerateParallelizedSearchProgramAlternativeAsNeeded(matchingPattern, alt);
  
              // emit matcher class head, body, tail; body is source code representing search program
              GenerateMatcherClassHeadAlternative(sb, matchingPattern, alt, isInitialStatic);
              searchProgram.Emit(sb);
              if(searchProgramParallelized != null)
                  searchProgramParallelized.Emit(sb);
              GenerateMatcherClassTail(sb, matchingPattern.PatternGraph.Package != null);
  
              // handle alternatives or iterateds nested in the alternative cases
              foreach (PatternGraph altCase in alt.alternativeCases)
              {
                  // nested inside the alternatives,iterateds,negatives,independents
                  foreach (Alternative nestedAlt in altCase.alternativesPlusInlined)
                  {
                      GenerateActionAndMatcherOfAlternative(sb, matchingPattern, nestedAlt, isInitialStatic);
                  }
                  foreach (Iterated iter in altCase.iteratedsPlusInlined)
                  {
                      GenerateActionAndMatcherOfIterated(sb, matchingPattern, iter.iteratedPattern, isInitialStatic);
                  }
                  foreach (PatternGraph neg in altCase.negativePatternGraphsPlusInlined)
                  {
                      GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, neg, isInitialStatic);
                  }
                  foreach (PatternGraph idpt in altCase.independentPatternGraphsPlusInlined)
                  {
                      GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, idpt, isInitialStatic);
                  }
              }
          }
  
          /// <summary>
          /// Generates the action interface plus action implementation including the matcher source code 
          /// for the given iterated pattern into the given source builder
          /// </summary>
          public void GenerateActionAndMatcherOfIterated(SourceBuilder sb,
              LGSPMatchingPattern matchingPattern, PatternGraph iter, bool isInitialStatic)
          {
              // generate the search program out of the schedule within the pattern graph of the iterated pattern
              SearchProgram searchProgram = GenerateSearchProgramIterated(matchingPattern, iter);
  
              // generate the parallelized search program out of the parallelized schedule within the pattern graph of the iterated pattern
              SearchProgram searchProgramParallelized = GenerateParallelizedSearchProgramIteratedAsNeeded(matchingPattern, iter);
  
              // emit matcher class head, body, tail; body is source code representing search program
              GenerateMatcherClassHeadIterated(sb, matchingPattern, iter, isInitialStatic);
              searchProgram.Emit(sb);
              if(searchProgramParallelized != null)
                  searchProgramParallelized.Emit(sb);
              GenerateMatcherClassTail(sb, matchingPattern.PatternGraph.Package != null);
  
              // finally generate matcher source for all the nested alternatives or iterateds of the iterated pattern graph
              // nested inside the alternatives,iterateds,negatives,independents
              foreach (Alternative alt in iter.alternativesPlusInlined)
              {
                  GenerateActionAndMatcherOfAlternative(sb, matchingPattern, alt, isInitialStatic);
              }
              foreach (Iterated nestedIter in iter.iteratedsPlusInlined)
              {
                  GenerateActionAndMatcherOfIterated(sb, matchingPattern, nestedIter.iteratedPattern, isInitialStatic);
              }
              foreach (PatternGraph neg in iter.negativePatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, neg, isInitialStatic);
              }
              foreach (PatternGraph idpt in iter.independentPatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, idpt, isInitialStatic);
              }
          }
  
          /// <summary>
          /// Generates the action interface plus action implementation including the matcher source code 
          /// for the alternatives/iterateds nested within the given negative/independent pattern graph into the given source builder
          /// </summary>
          public void GenerateActionAndMatcherOfNestedPatterns(SourceBuilder sb,
              LGSPMatchingPattern matchingPattern, PatternGraph negOrIdpt, bool isInitialStatic)
          {
              // nothing to do locally ..
  
              // .. just move on to the nested alternatives or iterateds
              foreach (Alternative alt in negOrIdpt.alternativesPlusInlined)
              {
                  GenerateActionAndMatcherOfAlternative(sb, matchingPattern, alt, isInitialStatic);
              }
              foreach (Iterated iter in negOrIdpt.iteratedsPlusInlined)
              {
                  GenerateActionAndMatcherOfIterated(sb, matchingPattern, iter.iteratedPattern, isInitialStatic);
              }
              foreach (PatternGraph nestedNeg in negOrIdpt.negativePatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, nestedNeg, isInitialStatic);
              }
              foreach (PatternGraph nestedIdpt in negOrIdpt.independentPatternGraphsPlusInlined)
              {
                  GenerateActionAndMatcherOfNestedPatterns(sb, matchingPattern, nestedIdpt, isInitialStatic);
              }
          }
  
          /// <summary>
          // generate the exact action interface
          /// </summary>
          void GenerateActionInterface(SourceBuilder sb, LGSPRulePattern matchingPattern)
          {
              String actionInterfaceName = "IAction_"+matchingPattern.name;
              String outParameters = "";
              String refParameters = "";
              String allParameters = "";
              for(int i = 0; i < matchingPattern.Outputs.Length; ++i)
              {
                  outParameters += ", out " + TypesHelper.TypeName(matchingPattern.Outputs[i]) + " output_"+i;
                  refParameters += ", ref " + TypesHelper.TypeName(matchingPattern.Outputs[i]) + " output_"+i;
                  allParameters += ", List<" + TypesHelper.TypeName(matchingPattern.Outputs[i]) + "> output_"+i;
              }
   
              String inParameters = "";
              for(int i=0; i<matchingPattern.Inputs.Length; ++i) {
                  inParameters += ", " + TypesHelper.TypeName(matchingPattern.Inputs[i]) + " " + matchingPattern.InputNames[i];
              }
              String matchingPatternClassName = matchingPattern.GetType().Name;
              String patternName = matchingPattern.name;
              String matchType = matchingPatternClassName + "." + NamesOfEntities.MatchInterfaceName(patternName);
              String matchesType = "GRGEN_LIBGR.IMatchesExact<" + matchType + ">" ;
  
              if(matchingPattern.PatternGraph.Package != null)
              {
                  sb.AppendFrontFormat("namespace {0}\n", matchingPattern.PatternGraph.Package);
                  sb.AppendFront("{\n");
                  sb.Indent();
              }
  
              sb.AppendFront("/// <summary>\n");
              sb.AppendFront("/// An object representing an executable rule - same as IAction, but with exact types and distinct parameters.\n");
              sb.AppendFront("/// </summary>\n");
              sb.AppendFrontFormat("public interface {0}\n", actionInterfaceName);
              sb.AppendFront("{\n");
              sb.Indent();
              sb.AppendFront("/// <summary> same as IAction.Match, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("{0} Match(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv, int maxMatches{1});\n", matchesType, inParameters);
  
              sb.AppendFront("/// <summary> same as IAction.Modify, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("void Modify(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv, {0} match{1});\n", matchType, outParameters);
  
              sb.AppendFront("/// <summary> same as IAction.ModifyAll, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("void ModifyAll(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv, {0} matches{1});\n", matchesType, allParameters);
  
              sb.AppendFront("/// <summary> same as IAction.Apply, but with exact types and distinct parameters; returns true if applied </summary>\n");
              sb.AppendFrontFormat("bool Apply(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv{0}{1});\n", inParameters, refParameters);
  
              sb.AppendFront("/// <summary> same as IAction.ApplyAll, but with exact types and distinct parameters; returns the number of matches found/applied. </summary>\n");
              sb.AppendFrontFormat("int ApplyAll(int maxMatches, GRGEN_LIBGR.IActionExecutionEnvironment actionEnv{0}{1});\n", inParameters, allParameters);
  
              sb.AppendFront("/// <summary> same as IAction.ApplyStar, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("bool ApplyStar(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv{0});\n", inParameters);
  
              sb.AppendFront("/// <summary> same as IAction.ApplyPlus, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("bool ApplyPlus(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv{0});\n", inParameters);
  
              sb.AppendFront("/// <summary> same as IAction.ApplyMinMax, but with exact types and distinct parameters. </summary>\n");
              sb.AppendFrontFormat("bool ApplyMinMax(GRGEN_LIBGR.IActionExecutionEnvironment actionEnv, int min, int max{0});\n", inParameters);
              sb.Unindent();
              sb.AppendFront("}\n");
              
              if(matchingPattern.PatternGraph.Package != null)
              {
                  sb.Unindent();
                  sb.AppendFront("}\n");
              }
  
              sb.AppendFront("\n");
          }
  
          /// <summary>
          // generate implementation of the exact action interface,
          // delegate calls of the inexact action interface IAction to the exact action interface
          /// </summary>
          void GenerateActionImplementation(SourceBuilder sb, LGSPRulePattern matchingPattern)
          {
              StringBuilder sbInParameters = new StringBuilder();
              StringBuilder sbInArguments = new StringBuilder();
              StringBuilder sbInArgumentsFromArray = new StringBuilder();
              for(int i = 0; i < matchingPattern.Inputs.Length; ++i)
              {
                  sbInParameters.Append(", ");
                  sbInParameters.Append(TypesHelper.TypeName(matchingPattern.Inputs[i]));
                  sbInParameters.Append(" ");
                  sbInParameters.Append(matchingPattern.InputNames[i]);
  
                  sbInArguments.Append(", ");
                  sbInArguments.Append(matchingPattern.InputNames[i]);
  
                  sbInArgumentsFromArray.Append(", (");
                  sbInArgumentsFromArray.Append(TypesHelper.TypeName(matchingPattern.Inputs[i]));
                  sbInArgumentsFromArray.Append(") parameters[");
                  sbInArgumentsFromArray.Append(i);
                  sbInArgumentsFromArray.Append("]");
              }
              String inParameters = sbInParameters.ToString();
              String inArguments = sbInArguments.ToString();
              String inArgumentsFromArray = sbInArgumentsFromArray.ToString();
  
              StringBuilder sbOutParameters = new StringBuilder();
              StringBuilder sbRefParameters = new StringBuilder();
              StringBuilder sbOutLocals = new StringBuilder();
              StringBuilder sbRefLocals = new StringBuilder();
              StringBuilder sbOutArguments = new StringBuilder();
              StringBuilder sbRefArguments = new StringBuilder();
              StringBuilder sbOutIntermediateLocalsAll = new StringBuilder();
  
gt:             StringBuilder sbOutParametersAll = new StringBuilder();