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 Edgar Jakumeit
  
  using System.Diagnostics;
  
  namespace de.unika.ipd.grGen.lgsp
  {
      /// <summary>
      /// Class completing search programs
      /// </summary>
      class SearchProgramCompleter
      {
          /// <summary>
          /// Iterate all search programs to complete check operations within each one
          /// </summary>
          public void CompleteCheckOperationsInAllSearchPrograms(
              SearchProgram searchProgram)
          {
              do
              {
                  CompleteCheckOperations(
                      searchProgram.GetNestedSearchOperationsList(),
                      searchProgram,
                      null,
                      null,
                      searchProgram);
                  searchProgram = searchProgram.Next as SearchProgram;
              }
              while (searchProgram != null);
          }
  
          ///////////////////////////////////////////////////////////////////////////////////
          ///////////////////////////////////////////////////////////////////////////////////
  
          /// <summary>
          /// Completes check operations in search program from given currentOperation on
          /// (taking borderlines set by enclosing search program and check negative into account)
          /// Completion:
          /// - determine continuation point
          /// - insert remove isomorphy opertions needed for continuing there
          /// - insert continuing operation itself
          /// </summary>
          private void CompleteCheckOperations(
              SearchProgramOperation currentOperation,
              SearchProgramOperation enclosingSearchProgram, // might be a negative/independent in case these are nested
              GetPartialMatchOfAlternative enclosingAlternative,
              CheckPartialMatchByNegativeOrIndependent enclosingCheckNegativeOrIndependent,
              SearchProgram topLevelSearchProgram)
          {
              // mainly dispatching and iteration method, traverses search program
              // real completion done in MoveOutwardsAppendingRemoveIsomorphyAndJump
              // outermost operation for that function is computed here, regarding negative patterns
              // program nesting structure: search program - [alternative] - [negative|independent]*
  
              // complete check operations by inserting failure code
              // find them in depth first search of search program
              while (currentOperation != null)
              {
                  //////////////////////////////////////////////////////////
                  if (currentOperation is CheckCandidate)
                  //////////////////////////////////////////////////////////
                  {
                      CheckCandidate checkCandidate =
                          (CheckCandidate)currentOperation;
                      checkCandidate.CheckFailedOperations =
                          new SearchProgramList(checkCandidate);
                      string[] neededElementsForCheckOperation = new string[1];
                      neededElementsForCheckOperation[0] = checkCandidate.PatternElementName;
                      MoveOutwardsAppendingRemoveIsomorphyAndJump(
                          checkCandidate,
                          neededElementsForCheckOperation,
                          enclosingCheckNegativeOrIndependent ?? (enclosingAlternative ?? enclosingSearchProgram),
                          topLevelSearchProgram);
                  }
                  //////////////////////////////////////////////////////////
                  else if (currentOperation is CheckPartialMatch)
                  //////////////////////////////////////////////////////////
                  {
                      if (currentOperation is CheckPartialMatchByCondition)
                      {
                          CheckPartialMatchByCondition checkCondition =
                              (CheckPartialMatchByCondition)currentOperation;
                          checkCondition.CheckFailedOperations =
                              new SearchProgramList(checkCondition);
                          MoveOutwardsAppendingRemoveIsomorphyAndJump(
                              checkCondition,
                              checkCondition.NeededElements,
                              enclosingCheckNegativeOrIndependent ?? (enclosingAlternative ?? enclosingSearchProgram),
                              topLevelSearchProgram);
                      }
                      else if(currentOperation is CheckPartialMatchForDuplicate)
                      {
                          CheckPartialMatchForDuplicate checkDuplicateMatch =
                              (CheckPartialMatchForDuplicate)currentOperation;
                          checkDuplicateMatch.CheckFailedOperations =
                              new SearchProgramList(checkDuplicateMatch);
                          MoveOutwardsAppendingRemoveIsomorphyAndJump(
                              checkDuplicateMatch,
                              checkDuplicateMatch.NeededElements,
                              enclosingCheckNegativeOrIndependent ?? (enclosingAlternative ?? enclosingSearchProgram),
                              topLevelSearchProgram);
                      }
                      else if(currentOperation is CheckPartialMatchByNegativeOrIndependent)
                      {
                          CheckPartialMatchByNegativeOrIndependent checkNegativeOrIndependent =
                              (CheckPartialMatchByNegativeOrIndependent)currentOperation;
  
                          // ByNegative/ByIndependent is handled in CheckContinueMatchingFailed
                          // of the negative/independent case - enter negative/independent case
                          CompleteCheckOperations(
                              checkNegativeOrIndependent.NestedOperationsList,
                              enclosingCheckNegativeOrIndependent ?? enclosingSearchProgram,
                              enclosingCheckNegativeOrIndependent!=null ? null : enclosingAlternative,
                              checkNegativeOrIndependent,
                              topLevelSearchProgram);
                      }
                      else if (currentOperation is CheckPartialMatchForSubpatternsFound)
                      {
                          CheckPartialMatchForSubpatternsFound checkSubpatternsFound =
                              (CheckPartialMatchForSubpatternsFound)currentOperation;
  
                          if (enclosingCheckNegativeOrIndependent == null)
                          {
                              // determine insertion point within check failed operations
                              // to append the nested check maximum matches
                              SearchProgramOperation insertionPoint =
                                  checkSubpatternsFound.CheckFailedOperations;
                              while (insertionPoint.Next != null)
                              {
                                  insertionPoint = insertionPoint.Next;
                              }
  
                              // append nested check maximum matches
                              CheckMaximumMatchesType checkMaxMatchesType = CheckMaximumMatchesType.Action;
                              if(enclosingSearchProgram is SearchProgramOfSubpattern
                                  || enclosingSearchProgram is SearchProgramOfAlternative) {
                                  checkMaxMatchesType = CheckMaximumMatchesType.Subpattern;
                              } else if(enclosingSearchProgram is SearchProgramOfIterated) {
                                  checkMaxMatchesType = CheckMaximumMatchesType.Iterated;
                              }
                              CheckContinueMatchingMaximumMatchesReached checkMaximumMatches =
                                  new CheckContinueMatchingMaximumMatchesReached(checkMaxMatchesType, false, 
                                      enclosingSearchProgram is SearchProgramOfActionParallelizationBody);
                              insertionPoint.Append(checkMaximumMatches);
  
                              MoveOutwardsAppendingRemoveIsomorphyAndJump(
                                  checkSubpatternsFound,
                                  null,
                                  enclosingCheckNegativeOrIndependent ?? (enclosingAlternative ?? enclosingSearchProgram),
                                  topLevelSearchProgram);
                          }
  
                          // check subpatterns found has a further check maximum matches
                          // or check continue matching of negative failed nested within check failed code
                          // give it its special bit of attention here
                          CompleteCheckOperations(
                              checkSubpatternsFound.CheckFailedOperations,
                              enclosingSearchProgram,
                              enclosingAlternative,
                              enclosingCheckNegativeOrIndependent,
                              topLevelSearchProgram);
                      }
                      else
                      {
                          Debug.Assert(false, "unknown check partial match operation");
                      }
  
                  }
                  //////////////////////////////////////////////////////////
                  else if (currentOperation is CheckContinueMatching)
                  //////////////////////////////////////////////////////////
                  {
                      if (currentOperation is CheckContinueMatchingMaximumMatchesReached)
                      {
                          CheckContinueMatchingMaximumMatchesReached checkMaximumMatches =
                              (CheckContinueMatchingMaximumMatchesReached)currentOperation;
                          checkMaximumMatches.CheckFailedOperations =
                              new SearchProgramList(checkMaximumMatches);
  
                          if (checkMaximumMatches.ListHeadAdjustment)
                          {
                              MoveOutwardsAppendingListHeadAdjustment(checkMaximumMatches, checkMaximumMatches.InParallelizedBody);
                          }
  
                          string[] neededElementsForCheckOperation = new string[0];
                          MoveOutwardsAppendingRemoveIsomorphyAndJump(
                              checkMaximumMatches,
                              neededElementsForCheckOperation,
                              enclosingSearchProgram,
                              topLevelSearchProgram);
                      }
                      else if (currentOperation is CheckContinueMatchingOfNegativeFailed)
                      {
                          CheckContinueMatchingOfNegativeFailed checkFailed =
                              (CheckContinueMatchingOfNegativeFailed)currentOperation;
                          checkFailed.CheckFailedOperations =
                              new SearchProgramList(checkFailed);
                          if(checkFailed.IsIterationBreaking)
                          {
                              string[] neededElementsForCheckOperation = new string[0];
                              MoveOutwardsAppendingRemoveIsomorphyAndJump(
                                  checkFailed,
                                  neededElementsForCheckOperation,
                                  enclosingSearchProgram,
                                  topLevelSearchProgram);
                          }
                          else
                          {
                              MoveOutwardsAppendingRemoveIsomorphyAndJump(
                                  checkFailed,
                                  enclosingCheckNegativeOrIndependent.NeededElements,
                                  enclosingAlternative ?? enclosingSearchProgram,
                                  topLevelSearchProgram);
                          }
                      }
                      else if (currentOperation is CheckContinueMatchingOfIndependentSucceeded)
                      {
                          CheckContinueMatchingOfIndependentSucceeded checkSucceeded =
                              (CheckContinueMatchingOfIndependentSucceeded)currentOperation;
                          checkSucceeded.CheckFailedOperations = // yep, rotten wording
                              new SearchProgramList(checkSucceeded);
                          MoveRightAfterCorrespondingIndependentFailedAppendingRemoveIsomorphyAndJump(
                              checkSucceeded,
                              (CheckPartialMatchByIndependent)enclosingCheckNegativeOrIndependent,
                              topLevelSearchProgram);
                      }
                      else if (currentOperation is CheckContinueMatchingOfIndependentFailed)
                      {
                          CheckContinueMatchingOfIndependentFailed checkFailed =
                              (CheckContinueMatchingOfIndependentFailed)currentOperation;
                          checkFailed.CheckFailedOperations =
                              new SearchProgramList(checkFailed);
                          if(checkFailed.IsIterationBreaking)
                          {
                              string[] neededElementsForCheckOperation = new string[0];
                              MoveOutwardsAppendingRemoveIsomorphyAndJump(
                                  checkFailed,
                                  neededElementsForCheckOperation,
                                  enclosingSearchProgram,
                                  topLevelSearchProgram);
                          }
                          else
                          {
                              MoveOutwardsAppendingRemoveIsomorphyAndJump(
                                  checkFailed,
                                  checkFailed.CheckIndependent.NeededElements,
                                  enclosingAlternative ?? enclosingSearchProgram,
                                  topLevelSearchProgram);
                          }
                      }
                      else if (currentOperation is CheckContinueMatchingTasksLeft)
                      {
                          CheckContinueMatchingTasksLeft tasksLeft =
                              (CheckContinueMatchingTasksLeft)currentOperation;
  
                          // determine insertion point within check failed operations
                          // to append the nested check maximum matches
                          SearchProgramOperation insertionPoint =
                              tasksLeft.CheckFailedOperations;
                          while (insertionPoint.Next != null)
                          {
                              insertionPoint = insertionPoint.Next;
                          }
  
                          // append nested check maximum matches
                          CheckContinueMatchingMaximumMatchesReached checkMaximumMatches =
                              new CheckContinueMatchingMaximumMatchesReached(
                                  enclosingSearchProgram is SearchProgramOfIterated ? CheckMaximumMatchesType.Iterated : CheckMaximumMatchesType.Subpattern,
                                  false, topLevelSearchProgram is SearchProgramOfActionParallelizationBody);
                          insertionPoint.Append(checkMaximumMatches);
  
                          MoveOutwardsAppendingRemoveIsomorphyAndJump(
                              tasksLeft,
                              null,
                              enclosingCheckNegativeOrIndependent ?? (enclosingAlternative ?? enclosingSearchProgram),
                              topLevelSearchProgram);
  
                          // check tasks left has a further check maximum matches nested within check failed code
                          // give it its special bit of attention here
                          CompleteCheckOperations(
                              tasksLeft.CheckFailedOperations,
                              enclosingSearchProgram,
                              enclosingAlternative,
                              enclosingCheckNegativeOrIndependent,
                              topLevelSearchProgram);
                      }
                      else if (currentOperation is CheckContinueMatchingIteratedPatternNonNullMatchFound)
                      {
                          // was built completely, nothing to complete
                      }
                      else
                      {
                          Debug.Assert(false, "unknown check abort matching operation");
                      }
                  }
                  //////////////////////////////////////////////////////////
                  else if (currentOperation is GetPartialMatchOfAlternative)
                  //////////////////////////////////////////////////////////
                  {
                      // depth first
                      CompleteCheckOperations(
                          currentOperation.GetNestedSearchOperationsList(),
                          enclosingSearchProgram,
                          (GetPartialMatchOfAlternative)currentOperation,
                          null,
                          topLevelSearchProgram);
                  }
                  //////////////////////////////////////////////////////////
                  else if (currentOperation.IsSearchNestingOperation())
                  //////////////////////////////////////////////////////////
                  {
                      // depth first
                      CompleteCheckOperations(
                          currentOperation.GetNestedSearchOperationsList(),
                          enclosingSearchProgram,
                          enclosingAlternative,
                          enclosingCheckNegativeOrIndependent,
                          topLevelSearchProgram);
                  }
  
                  // breadth
                  currentOperation = currentOperation.Next;
              }
          }
  
          /// <summary>
          /// "listentrick": append search program operations to adjust list heads
          /// i.e. set list entry point to element after last found,
          /// so that next searching starts there - performance optimization
          /// (leave graph in the state of our last visit (searching it))
          /// </summary>
          private void MoveOutwardsAppendingListHeadAdjustment(
              CheckContinueMatchingMaximumMatchesReached checkMaximumMatches,
              bool inParallelizedBody)
          {
              // todo: avoid adjusting list heads twice for lookups of same type
  
              // insertion point for candidate failed operations
              SearchProgramOperation insertionPoint =
                  checkMaximumMatches.CheckFailedOperations;
              SearchProgramOperation op = checkMaximumMatches;
              do
              {
                  if(op is GetCandidateByIteration)
                  {
                      GetCandidateByIteration candidateByIteration =
                          op as GetCandidateByIteration;
                      if(candidateByIteration.Type == GetCandidateByIterationType.GraphElements)
                      {
                          AdjustListHeads adjustElements =
                              new AdjustListHeads(
                                  AdjustListHeadsTypes.GraphElements,
                                  candidateByIteration.PatternElementName,
                                  candidateByIteration.IsNode,
                                  inParallelizedBody);
                          insertionPoint = insertionPoint.Append(adjustElements);
                      }
                      else if(candidateByIteration.Type==GetCandidateByIterationType.IncidentEdges)
                      {
                          AdjustListHeads adjustIncident =
                              new AdjustListHeads(
                                  AdjustListHeadsTypes.IncidentEdges,
                                  candidateByIteration.PatternElementName,
                                  candidateByIteration.StartingPointNodeName,
                                  candidateByIteration.EdgeType,
                                  inParallelizedBody);
                          insertionPoint = insertionPoint.Append(adjustIncident);
                      }
                  }
                  else if(op is GetCandidateByIterationParallel)
                  {
                      GetCandidateByIterationParallel candidateByIteration =
                          op as GetCandidateByIterationParallel;
                      if(candidateByIteration.Type == GetCandidateByIterationType.GraphElements)
                      {
                          AdjustListHeads adjustElements =
                              new AdjustListHeads(
                                  AdjustListHeadsTypes.GraphElements,
                                  candidateByIteration.PatternElementName,
                                  candidateByIteration.IsNode,
                                  inParallelizedBody);
  
gt:                         insertionPoint = insertionPoint.Append(adjustElements);