package jetbrains.mps.baseLanguage.behavior;

/*Generated by MPS */

import org.jetbrains.mps.openapi.model.SNode;
import org.jetbrains.annotations.NotNull;
import jetbrains.mps.lang.smodel.generator.smodelAdapter.IAttributeDescriptor;
import jetbrains.mps.lang.smodel.generator.smodelAdapter.SLinkOperations;
import jetbrains.mps.lang.smodel.generator.smodelAdapter.SNodeOperations;
import jetbrains.mps.baseLanguage.editor.EditorParenthesisUtil;
import java.util.Objects;
import jetbrains.mps.smodel.action.SNodeFactoryOperations;
import java.util.List;
import jetbrains.mps.internal.collections.runtime.ListSequence;
import jetbrains.mps.baseLanguage.closures.runtime.Wrappers;
import java.util.ArrayList;
import jetbrains.mps.lang.smodel.generator.smodelAdapter.SPropertyOperations;
import org.jetbrains.mps.openapi.language.SAbstractConcept;
import org.jetbrains.mps.openapi.language.SConcept;
import jetbrains.mps.smodel.adapter.structure.MetaAdapterFactory;
import org.jetbrains.mps.openapi.language.SInterfaceConcept;
import org.jetbrains.mps.openapi.language.SContainmentLink;
import org.jetbrains.mps.openapi.language.SProperty;

public class ParenthesisUtil {
  public ParenthesisUtil() {
  }

  public static SNode createUnmatchedLeftParenthesis(@NotNull SNode leftExpression) {
    return createUnmatchedParenthesisAndCheckParentParens(leftExpression, false);
  }

  public static SNode createUnmatchedRightParenthesis(@NotNull SNode rightExpression) {
    return createUnmatchedParenthesisAndCheckParentParens(rightExpression, true);
  }


  /**
   * First search up the ancestors for ParenthesisedExpressions.
   * If found one, break it into two incomplete parentheses and match with one of them.
   * The continue trying to match the other incomplete parenthesis.
   * If no more ancestor ParenthesisedExpression is found, continue with the standard matching
   */
  private static SNode createUnmatchedParenthesisAndCheckParentParens(@NotNull final SNode myExpression, final boolean completingByRightParen) {

    SNode expressionToProcess = myExpression;
    SNode expressionToSetFocusOn = null;

    SNode current = findWrappingParens(expressionToProcess);
    while (current != null) {
      SNode leftParenOnParens = new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(current);
      SNode rightParenOnParens = new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(current);
      boolean propagateNewParensInsteadOfExpr = false;

      SNode replacing = SLinkOperations.getTarget(SNodeOperations.cast(current, CONCEPTS.ParenthesizedExpression$Ws), LINKS.expression$TlhM);
      SNode rightMostNode = EditorParenthesisUtil.findRightmostOrLeftmostLeafExpression(replacing, true);
      SNode leftMostNode = EditorParenthesisUtil.findRightmostOrLeftmostLeafExpression(replacing, false);

      if ((completingByRightParen && Objects.equals(expressionToProcess, rightMostNode)) || (!(completingByRightParen) && Objects.equals(expressionToProcess, leftMostNode))) {
        propagateNewParensInsteadOfExpr = true;
      }

      SNodeOperations.replaceWithAnother(current, replacing);
      SNode localExpToSetFocusOn;
      if (completingByRightParen) {
        setOrIncreaseParen(leftMostNode, false);
        localExpToSetFocusOn = ParenthesisUtil.createUnmatchedParenthesis(expressionToProcess, true);
        expressionToProcess = (propagateNewParensInsteadOfExpr ? localExpToSetFocusOn : rightMostNode);
      } else {
        setOrIncreaseParen(rightMostNode, true);
        localExpToSetFocusOn = ParenthesisUtil.createUnmatchedParenthesis(expressionToProcess, false);
        expressionToProcess = (propagateNewParensInsteadOfExpr ? localExpToSetFocusOn : leftMostNode);
      }

      // Remember the first parenthing result for the editor to set focus to
      if (expressionToSetFocusOn == null) {
        expressionToSetFocusOn = localExpToSetFocusOn;
      }

      // Put back the parens that were on the wrapping parentheses and belong to the mating expr
      if (completingByRightParen && leftParenOnParens != null) {
        setOrMergeParen(localExpToSetFocusOn, false, leftParenOnParens);
      }
      if (!(completingByRightParen) && rightParenOnParens != null) {
        setOrMergeParen(localExpToSetFocusOn, true, rightParenOnParens);
      }

      // Put back the parens that were on the wrapping parentheses and belong to the new expressionToProcess
      if (completingByRightParen && rightParenOnParens != null) {
        setOrMergeParen(expressionToProcess, true, rightParenOnParens);
      }
      if (!(completingByRightParen) && leftParenOnParens != null) {
        setOrMergeParen(expressionToProcess, false, leftParenOnParens);
      }

      current = findWrappingParens(expressionToProcess);
    }

    SNode created = createUnmatchedParenthesis(expressionToProcess, completingByRightParen);
    checkWholeExpressionPriorities(myExpression);
    return (expressionToSetFocusOn != null ? expressionToSetFocusOn : created);
  }

  private static SNode findWrappingParens(SNode original) {
    SNode current = original;
    while (SNodeOperations.isInstanceOf(SNodeOperations.getParent(current), CONCEPTS.Expression$mB)) {
      current = SNodeOperations.cast(SNodeOperations.getParent(current), CONCEPTS.Expression$mB);
      if (SNodeOperations.isInstanceOf(current, CONCEPTS.ParenthesizedExpression$Ws)) {
        return current;
      }
    }
    return null;
  }

  private static void setOrIncreaseParen(SNode node, boolean right) {
    SNode paren = (right ? new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(node) : new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(node));
    if (paren != null) {
      IIncompleteParen__BehaviorDescriptor.increaseCount_idVufYxgmE1y.invoke(paren);
    } else {
      if (right) {
        SNodeFactoryOperations.setNewAttribute(node, new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc), CONCEPTS.IncompleteRightParen$Sc);
      } else {
        SNodeFactoryOperations.setNewAttribute(node, new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7), CONCEPTS.IncompleteLeftParen$Z7);
      }
    }
  }

  private static void setOrMergeParen(SNode myNode, boolean right, SNode parens) {
    SNode nodesParens = (right ? new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(myNode) : new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(myNode));
    if (nodesParens == null) {
      if (right) {
        nodesParens = SNodeFactoryOperations.setNewAttribute(myNode, new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc), CONCEPTS.IncompleteRightParen$Sc);
      } else {
        nodesParens = SNodeFactoryOperations.setNewAttribute(myNode, new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7), CONCEPTS.IncompleteLeftParen$Z7);
      }
    }
    while (!((boolean) IIncompleteParen__BehaviorDescriptor.isSingleParen_idVufYxgmHsD.invoke(parens))) {
      IIncompleteParen__BehaviorDescriptor.decreaseCount_idVufYxgmFtR.invoke(parens);
      IIncompleteParen__BehaviorDescriptor.increaseCount_idVufYxgmE1y.invoke(nodesParens);
    }
  }

  /**
   * First search existing unmatched parens, whether they can be paired with the new one.
   * If found, pair them, if not, create an unmatched paren annotation.
   */
  private static SNode createUnmatchedParenthesis(@NotNull SNode myExpression, boolean completingByRightParen) {

    if (!(completingByRightParen) && new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(myExpression) != null) {
      IIncompleteParen__BehaviorDescriptor.increaseCount_idVufYxgmE1y.invoke(new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(myExpression));
      return myExpression;
    }
    if (completingByRightParen && new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(myExpression) != null) {
      IIncompleteParen__BehaviorDescriptor.increaseCount_idVufYxgmE1y.invoke(new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(myExpression));
      return myExpression;
    }

    List<SNode> myParentPath = parentPath(myExpression, completingByRightParen);
    SNode topExp = ListSequence.fromList(myParentPath).findLast((it) -> SNodeOperations.isInstanceOf(it, CONCEPTS.IBinaryLike$eU));
    if (topExp == null) {
      // No IBinaryLike ancestor of myExpression exists
      topExp = myExpression;
    }

    List<SNode> candidateParenthedNodes = descendInto(topExp, completingByRightParen);

    int index = ListSequence.fromList(candidateParenthedNodes).count() - 1;
    SNode candidateExpression = null;
    final Wrappers._T<List<SNode>> candidateParentPath = new Wrappers._T<List<SNode>>(null);
    // The bottom-most common ancestor
    SNode firstCommonAncestor = null;
    // Find a matching parenthesis among candidates, going from the back of the list
    while (index >= 0) {
      candidateExpression = ListSequence.fromList(candidateParenthedNodes).getElement(index);
      if (Objects.equals(candidateExpression, myExpression)) {
        // they are both the same node
        SNode parens = SNodeFactoryOperations.replaceWithNewChild(candidateExpression, CONCEPTS.ParenthesizedExpression$Ws);
        SLinkOperations.setTarget(parens, LINKS.expression$TlhM, candidateExpression);
        ParenthesisUtil.clearIncompleteParens(candidateExpression, completingByRightParen, parens);
        return parens;
      }

      // Find the bottom-most common ancestor
      candidateParentPath.value = parentPath(candidateExpression, !(completingByRightParen));
      if (ListSequence.fromList(myParentPath).contains(ListSequence.fromList(candidateParentPath.value).last()) || ListSequence.fromList(candidateParentPath.value).contains(ListSequence.fromList(myParentPath).last())) {
        firstCommonAncestor = ListSequence.fromList(myParentPath).findFirst((it) -> ListSequence.fromList(candidateParentPath.value).contains(it));
        assert firstCommonAncestor != null;
        if (!(SNodeOperations.isInstanceOf(firstCommonAncestor, CONCEPTS.IBinaryLike$eU))) {
          continue;
        }

        SNode leftSideExpression = IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(SNodeOperations.cast(firstCommonAncestor, CONCEPTS.IBinaryLike$eU));
        SNode rightSideExpression = IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(SNodeOperations.cast(firstCommonAncestor, CONCEPTS.IBinaryLike$eU));
        List<SNode> candidateAncestors = SNodeOperations.getNodeAncestors(candidateExpression, null, true);
        List<SNode> myAncestors = SNodeOperations.getNodeAncestors(myExpression, null, true);

        // Validate the bottom-most ancestor, whether the two parentheses can be paired legally
        if (completingByRightParen && (ListSequence.fromList(candidateAncestors).contains(leftSideExpression) || leftSideExpression == null) && (ListSequence.fromList(myAncestors).contains(rightSideExpression) || rightSideExpression == null)) {
          break;
        }
        if (!(completingByRightParen) && (ListSequence.fromList(myAncestors).contains(leftSideExpression) || leftSideExpression == null) && (ListSequence.fromList(candidateAncestors).contains(rightSideExpression) || rightSideExpression == null)) {
          break;
        }
        // Break out if found a valid match
      }
      // Continue to try another candidate parenthesis
      index--;
    }
    if (index == -1) {
      // no common ancestor with any of the candidate parens or swapped left-right -> can't parenthesise
      if (completingByRightParen) {
        setOrIncreaseParen(myExpression, true);
      } else {
        setOrIncreaseParen(myExpression, false);
      }
      return myExpression;
    }


    // Let's call them left and right parens from now, instead of 'my' and 'candidate'
    SNode leftExpression = (completingByRightParen ? candidateExpression : myExpression);
    SNode rightExpression = (completingByRightParen ? myExpression : candidateExpression);
    // Find the turning points, if exist, otherwise just wrap in parens
    SNode leftTurn = ParenthesisUtil.findLeftTurn(leftExpression, firstCommonAncestor);
    SNode rightTurn = ParenthesisUtil.findRightTurn(rightExpression, firstCommonAncestor);

    if (leftTurn != null || rightTurn != null) {
      SNode parens = ParenthesisUtil.rebalance(leftTurn, SNodeOperations.cast(firstCommonAncestor, CONCEPTS.IBinaryLike$eU), rightTurn);
      clearIncompleteParens(candidateExpression, completingByRightParen, parens);
      return parens;
    } else {
      SNode p = SNodeFactoryOperations.createNewNode(CONCEPTS.ParenthesizedExpression$Ws, null);
      SNode parens = SNodeOperations.replaceWithAnother(firstCommonAncestor, p);
      SLinkOperations.setTarget(p, LINKS.expression$TlhM, firstCommonAncestor);
      clearIncompleteParens(candidateExpression, completingByRightParen, p);
      return parens;
    }
  }

  /**
   * Returns an orderred list of nodes with incomplete left/right paren
   * The nodes are orderred by their occurence on the expression in left-to-right order
   * The current node is added at the front of the list,
   * so that it is always the most distant node among the returned candidates
   */
  private static List<SNode> descendInto(SNode expr, final boolean completingByRightParen) {
    List<SNode> path = ListSequence.fromListAndArray(new ArrayList<SNode>(), null, expr);
    List<SNode> result = ListSequence.fromList(new ArrayList<SNode>());

    SNode current = expr;
    while (ListSequence.fromList(path).isNotEmpty()) {
      if (SNodeOperations.isInstanceOf(current, CONCEPTS.IBinaryLike$eU)) {
        if (Objects.equals(ListSequence.fromList(path).last(), current)) {
          SNode left = IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(SNodeOperations.cast(current, CONCEPTS.IBinaryLike$eU));
          if (left != null) {
            ListSequence.fromList(path).addElement(left);
            current = left;
          } else {
            current = ListSequence.fromList(path).removeLastElement();
          }
        } else {
          ListSequence.fromList(result).addElement(current);
          SNode right = IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(SNodeOperations.cast(current, CONCEPTS.IBinaryLike$eU));
          if (right != null) {
            ListSequence.fromList(path).addElement(right);
            current = right;
          } else {
            current = ListSequence.fromList(path).removeLastElement();
          }
        }
      } else {
        ListSequence.fromList(result).addElement(current);
        if (Objects.equals(ListSequence.fromList(path).last(), current)) {
          ListSequence.fromList(path).removeLastElement();
        }
        current = ListSequence.fromList(path).removeLastElement();
      }
    }
    if (!(completingByRightParen)) {
      result = ListSequence.fromList(result).reversedList();
    }

    result = ListSequence.fromList(result).where((it) -> completingByRightParen && (new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(it) != null) || !(completingByRightParen) && (new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(it) != null)).toList();

    return result;
  }

  /**
   * Create a ParenthesisedExpression and hook it properly into the model
   * 
   * @param leftTurn The expression that should be put outside and to the left from the new parens
   * @param rightTurn The expression that should be put outside and to the right from the new parens
   * @param firstCommonAncestor The common ancestor expression of both parentheses
   */
  private static SNode rebalance(SNode leftTurn, SNode firstCommonAncestor, SNode rightTurn) {

    // Accumulate expressions between the leftTurn and firstCommon to include inside the parens.
    // These would be the nodes into which we come from the left child.
    SNode leftAccumulator = buildAccumulator(firstCommonAncestor, leftTurn, true);
    // Accumulate expressions between the rightTurn and firstCommon to include inside the parens.
    // These would be the nodes into which we come from the right child.
    SNode rightAccumulator = buildAccumulator(firstCommonAncestor, rightTurn, false);

    SNode parens = SNodeFactoryOperations.createNewNode(CONCEPTS.ParenthesizedExpression$Ws, null);
    if (SNodeOperations.isInstanceOf(firstCommonAncestor, CONCEPTS.BinaryOperation$W1)) {
      rebalanceIBinaryLikeAfterParenthing(SNodeOperations.cast(firstCommonAncestor, CONCEPTS.BinaryOperation$W1), rightTurn, leftTurn, parens, rightAccumulator, leftAccumulator);
    } else if (SNodeOperations.isInstanceOf(firstCommonAncestor, CONCEPTS.TernaryOperatorExpression$aq)) {
      rebalanceTernaryOpAfterParenthing(SNodeOperations.cast(firstCommonAncestor, CONCEPTS.TernaryOperatorExpression$aq), rightTurn, leftTurn, parens, rightAccumulator, leftAccumulator);
    } else if (SNodeOperations.isInstanceOf(firstCommonAncestor, CONCEPTS.CastExpression$$8) || SNodeOperations.isInstanceOf(firstCommonAncestor, CONCEPTS.BaseAssignmentExpression$PA)) {
      rebalanceIBinaryLikeAfterParenthing(SNodeOperations.cast(firstCommonAncestor, CONCEPTS.IBinaryLike$eU), rightTurn, leftTurn, parens, rightAccumulator, leftAccumulator);
    }

    SLinkOperations.setTarget(parens, LINKS.expression$TlhM, firstCommonAncestor);
    return parens;
  }

  private static void rebalanceIBinaryLikeAfterParenthing(SNode node, SNode rightTurn, SNode leftTurn, SNode parens, SNode rightAccumulator, SNode leftAccumulator) {
    SNode leftSide = IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(node);
    SNode rightSide = IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(node);
    assert leftSide != null || rightSide != null;
    SNode head = (rightSide != null ? rightSide : leftSide);
    SNodeOperations.replaceWithAnother(node, head);
    SLinkOperations.setTarget(parens, LINKS.expression$TlhM, node);

    if (leftAccumulator != null) {
      IBinaryLike__BehaviorDescriptor.setSyntacticallyLeftSideExpression_id1wHCnsn58ZK.invoke(node, leftAccumulator);
    }
    if (rightAccumulator != null) {
      IBinaryLike__BehaviorDescriptor.setSyntacticallyRightSideExpression_id1wHCnsn58ZY.invoke(node, rightAccumulator);
    }
    SNode subtree;
    if (leftSide != null) {
      subtree = leftSide;
      IBinaryLike__BehaviorDescriptor.setSyntacticallyRightSideExpression_id1wHCnsn58ZY.invoke(leftTurn, parens);
    } else {
      subtree = parens;
    }
    if (rightSide != null) {
      IBinaryLike__BehaviorDescriptor.setSyntacticallyLeftSideExpression_id1wHCnsn58ZK.invoke(rightTurn, subtree);
    }
  }

  private static void rebalanceTernaryOpAfterParenthing(SNode node, SNode rightTurn, SNode leftTurn, SNode parens, SNode rightAccumulator, SNode leftAccumulator) {
    SNode bottomMostTernary = findBottomMostTernary(node);
    if (rightTurn != null) {
      SNodeOperations.replaceWithAnother(node, SLinkOperations.getTarget(bottomMostTernary, LINKS.ifFalse$Wbma));
      if (leftTurn != null) {
        IBinaryLike__BehaviorDescriptor.setSyntacticallyLeftSideExpression_id1wHCnsn58ZK.invoke(rightTurn, SLinkOperations.getTarget(node, LINKS.condition$nwNI));
        IBinaryLike__BehaviorDescriptor.setSyntacticallyRightSideExpression_id1wHCnsn58ZY.invoke(leftTurn, parens);
      } else {
        IBinaryLike__BehaviorDescriptor.setSyntacticallyLeftSideExpression_id1wHCnsn58ZK.invoke(rightTurn, parens);
      }
    } else {
      if (leftTurn != null) {
        SNodeOperations.replaceWithAnother(node, SLinkOperations.getTarget(node, LINKS.condition$nwNI));
        IBinaryLike__BehaviorDescriptor.setSyntacticallyRightSideExpression_id1wHCnsn58ZY.invoke(leftTurn, parens);
      } else {
        SNodeOperations.replaceWithAnother(node, parens);
      }
    }
    SLinkOperations.setTarget(bottomMostTernary, LINKS.ifFalse$Wbma, rightAccumulator);
    SLinkOperations.setTarget(node, LINKS.condition$nwNI, leftAccumulator);
  }

  /**
   * Ternary expressions can be nested in one anothers ifFalse child. Find the right-most one.
   * 
   * @param bottomMostTernary The so-far most-bottom ternary operator expression
   * @return The found right-most ternary operator expression.
   */
  private static SNode findBottomMostTernary(SNode bottomMostTernary) {
    while (SNodeOperations.isInstanceOf(SLinkOperations.getTarget(bottomMostTernary, LINKS.ifFalse$Wbma), CONCEPTS.TernaryOperatorExpression$aq)) {
      bottomMostTernary = SNodeOperations.cast(SLinkOperations.getTarget(bottomMostTernary, LINKS.ifFalse$Wbma), CONCEPTS.TernaryOperatorExpression$aq);
    }
    return bottomMostTernary;
  }

  /**
   * Accumulate the nodes that need to be added into the parentheses
   */
  private static SNode buildAccumulator(SNode firstCommonAncestor, SNode turn, boolean left) {
    SNode accumulator;
    if (turn != null && !(Objects.equals(turn, firstCommonAncestor))) {
      // Accumulate nodes on the path up from the left/right paren
      accumulator = (left ? IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(turn) : IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(turn));
      SNodeOperations.deleteNode(accumulator);
      SNode current = SNodeOperations.cast(SNodeOperations.getParent(turn), CONCEPTS.IBinaryLike$eU);
      SNode previous = turn;
      while (!(Objects.equals(current, firstCommonAncestor))) {
        SNode sideExpression = (left ? IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(current) : IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(current));
        if (sideExpression != null && Objects.equals(sideExpression, previous)) {
          SNodeOperations.replaceWithAnother(current, previous);
          if (left) {
            IBinaryLike__BehaviorDescriptor.setSyntacticallyLeftSideExpression_id1wHCnsn58ZK.invoke(current, accumulator);
          } else {
            IBinaryLike__BehaviorDescriptor.setSyntacticallyRightSideExpression_id1wHCnsn58ZY.invoke(current, accumulator);
          }
          accumulator = SNodeOperations.cast(current, CONCEPTS.Expression$mB);
        } else {
          previous = current;
        }
        current = SNodeOperations.cast(SNodeOperations.getParent(previous), CONCEPTS.IBinaryLike$eU);
      }
    } else {
      // Nothing to accumulate
      SNode firstCommonAncestorChild = (left ? IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(firstCommonAncestor) : IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(firstCommonAncestor));
      if (firstCommonAncestorChild != null) {
        accumulator = firstCommonAncestorChild;
        SNodeOperations.deleteNode(accumulator);
      } else {
        accumulator = null;
      }
    }
    return accumulator;
  }

  /**
   * Remove the found matching paren annotation from its node
   */
  private static void clearIncompleteParens(SNode otherExpression, boolean completingByRightParen, SNode parens) {
    int count = 0;
    if (completingByRightParen) {
      count = SPropertyOperations.getInteger(new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).get(otherExpression), PROPS.count$FDpi);
      new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).set(otherExpression, null);
      new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteLeftParen$Z7).set(parens, null);
    } else {
      count = SPropertyOperations.getInteger(new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).get(otherExpression), PROPS.count$FDpi);
      new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).set(otherExpression, null);
      new IAttributeDescriptor.NodeAttribute(CONCEPTS.IncompleteRightParen$Sc).set(parens, null);
    }

    // One paren has been matched, so we should decrease the count
    count -= 1;
    if (count < 1) {
      return;
    }
    for (int i = 0; i < count; i++) {
      setOrIncreaseParen(parens, !(completingByRightParen));
    }
  }

  /**
   * Climb up the ancestor expressions and return the first binary operation, in which we come from the right sub-tree.
   * 
   * @param stopNode Never climb beyond this node
   */
  private static SNode findLeftTurn(SNode leaf, SNode stopNode) {
    return findTurn(leaf, stopNode, true);
  }

  /**
   * Climb up the ancestor expressions and return the first binary operation, in which we come from the left sub-tree.
   * 
   * @param stopNode Never climb beyond this node
   */
  private static SNode findRightTurn(SNode leaf, SNode stopNode) {
    return findTurn(leaf, stopNode, false);
  }

  private static SNode findTurn(SNode leaf, SNode stopNode, boolean leftTurn) {
    SNode currentNode = SNodeOperations.getParent(leaf);
    SNode previous = leaf;
    while (!(Objects.equals(previous, stopNode)) && SNodeOperations.isInstanceOf(currentNode, CONCEPTS.IBinaryLike$eU)) {
      SNode leftSideExpression = IBinaryLike__BehaviorDescriptor.getSyntacticallyLeftSideExpression_id1wHCnsn590c.invoke(SNodeOperations.cast(currentNode, CONCEPTS.IBinaryLike$eU));
      SNode rightSideExpression = IBinaryLike__BehaviorDescriptor.getSyntacticallyRightSideExpression_id1wHCnsn590i.invoke(SNodeOperations.cast(currentNode, CONCEPTS.IBinaryLike$eU));
      if (leftTurn && Objects.equals(rightSideExpression, previous)) {
        return SNodeOperations.cast(currentNode, CONCEPTS.IBinaryLike$eU);
      }
      if (!(leftTurn) && Objects.equals(leftSideExpression, previous)) {
        return SNodeOperations.cast(currentNode, CONCEPTS.IBinaryLike$eU);
      }

      previous = currentNode;
      currentNode = SNodeOperations.getParent(currentNode);
    }
    return null;
  }


  /**
   * Find all the ancestor expressions of leaf that could be wrapped in parens.
   * Stops when the parent current expression could no longer be parenthesised.
   */
  private static List<SNode> parentPath(SNode leaf, boolean rightParen) {
    List<SNode> path = new ArrayList<SNode>();
    ListSequence.fromList(path).addElement(leaf);
    List<SNode> leafAncestors = SNodeOperations.getNodeAncestors(leaf, null, true);

    for (SNode currentNode = SNodeOperations.getParent(leaf); SNodeOperations.isInstanceOf(currentNode, CONCEPTS.IBinaryLike$eU) && (boolean) IBinaryLike__BehaviorDescriptor.canPropagateUnmatchedParenUp_id1wHCnsn58ZA.invoke(SNodeOperations.cast(currentNode, CONCEPTS.IBinaryLike$eU), leaf, ((boolean) rightParen)); currentNode = SNodeOperations.getParent(currentNode)) {
      ListSequence.fromList(path).addElement(SNodeOperations.cast(currentNode, CONCEPTS.Expression$mB));
    }
    return path;
  }

  public static void checkWholeExpressionPriorities(SNode expr) {
    SNode current = expr;
    // find the top-most expression
    while (SNodeOperations.isInstanceOf(SNodeOperations.getParent(current), CONCEPTS.Expression$mB)) {
      current = SNodeOperations.cast(SNodeOperations.getParent(current), CONCEPTS.Expression$mB);
    }

    List<SNode> candidates = ListSequence.fromList(new ArrayList<SNode>());
    ListSequence.fromList(candidates).addSequence(ListSequence.fromList(SNodeOperations.getNodeDescendants(current, CONCEPTS.BinaryOperation$W1, true, new SAbstractConcept[]{})));
    checkCandidateExpressionsPriorities(candidates);
  }

  public static void checkOperationWRTPriority(SNode binOp) {
    List<SNode> candidates = ListSequence.fromListAndArray(new ArrayList<SNode>(), binOp);
    checkCandidateExpressionsPriorities(candidates);
  }

  private static void checkCandidateExpressionsPriorities(List<SNode> candidates) {
    while (ListSequence.fromList(candidates).isNotEmpty()) {
      SNode candidate = ListSequence.fromList(candidates).first();
      if (checkOperationChildWRTPriority(candidate, false, candidates) && checkOperationChildWRTPriority(candidate, true, candidates) && checkOperationParentWRTPriority(candidate, candidates)) {
        ListSequence.fromList(candidates).removeElementAt(0);
      }
    }
  }

  private static boolean checkOperationChildWRTPriority(SNode node, boolean isRight, List<SNode> candidates) {
    SNode sideExpr = (isRight ? SLinkOperations.getTarget(node, LINKS.rightExpression$nvX) : SLinkOperations.getTarget(node, LINKS.leftExpression$sEj));
    if (SNodeOperations.isInstanceOf(sideExpr, CONCEPTS.BinaryOperation$W1)) {
      SNode sideChild = SNodeOperations.cast(sideExpr, CONCEPTS.BinaryOperation$W1);
      if (isBadPriority(sideChild, node, isRight)) {
        ParenthesisUtil.rotateTree(sideChild, node, isRight);
        ListSequence.fromList(candidates).addElement(SNodeOperations.cast(sideExpr, CONCEPTS.BinaryOperation$W1));
        return false;
      }
    } else if (SNodeOperations.isInstanceOf(sideExpr, CONCEPTS.TernaryOperatorExpression$aq)) {
      SNodeOperations.replaceWithAnother(node, sideExpr);
      if (isRight) {
        SLinkOperations.setTarget(node, LINKS.rightExpression$nvX, SLinkOperations.getTarget(SNodeOperations.cast(sideExpr, CONCEPTS.TernaryOperatorExpression$aq), LINKS.condition$nwNI));
        SLinkOperations.setTarget(SNodeOperations.cast(sideExpr, CONCEPTS.TernaryOperatorExpression$aq), LINKS.condition$nwNI, node);
      } else {
        SLinkOperations.setTarget(node, LINKS.leftExpression$sEj, SLinkOperations.getTarget(SNodeOperations.cast(sideExpr, CONCEPTS.TernaryOperatorExpression$aq), LINKS.ifFalse$Wbma));
        SLinkOperations.setTarget(SNodeOperations.cast(sideExpr, CONCEPTS.TernaryOperatorExpression$aq), LINKS.ifFalse$Wbma, node);
      }
      if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(sideExpr), CONCEPTS.BinaryOperation$W1)) {
        ListSequence.fromList(candidates).addElement(SNodeOperations.cast(SNodeOperations.getParent(sideExpr), CONCEPTS.BinaryOperation$W1));
      }
      return false;
    }
    return true;
  }

  private static boolean checkOperationParentWRTPriority(SNode node, List<SNode> candidates) {
    if (SNodeOperations.getParent(node) == null) {
      return true;
    }
    if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(node), CONCEPTS.BinaryOperation$W1)) {
      SNode parent = SNodeOperations.cast(SNodeOperations.getParent(node), CONCEPTS.BinaryOperation$W1);
      boolean isRight = false;
      if (SLinkOperations.getTarget(parent, LINKS.rightExpression$nvX) == node) {
        isRight = true;
      } else if (SLinkOperations.getTarget(parent, LINKS.leftExpression$sEj) == node) {
        isRight = false;
      }
      if (ParenthesisUtil.isBadPriority(node, parent, isRight)) {
        ParenthesisUtil.rotateTree(node, parent, isRight);
        ListSequence.fromList(candidates).addElement(parent);
        return false;
      }
      return true;
    } else {
      if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(node), CONCEPTS.AbstractUnaryNumberOperation$Q6)) {
        SNode parent = SNodeOperations.cast(SNodeOperations.getParent(node), CONCEPTS.AbstractUnaryNumberOperation$Q6);
        SLinkOperations.setTarget(parent, LINKS.expression$uRUg, SLinkOperations.getTarget(node, LINKS.leftExpression$sEj));
        SNodeOperations.replaceWithAnother(parent, node);
        SLinkOperations.setTarget(node, LINKS.leftExpression$sEj, parent);
      } else if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(node), CONCEPTS.CastExpression$$8)) {
        SNode castExpr = SNodeOperations.cast(SNodeOperations.getParent(node), CONCEPTS.CastExpression$$8);
        SNodeOperations.replaceWithAnother(castExpr, node);
        SLinkOperations.setTarget(castExpr, LINKS.expression$XDmN, SLinkOperations.getTarget(node, LINKS.leftExpression$sEj));
        SLinkOperations.setTarget(node, LINKS.leftExpression$sEj, castExpr);
      } else if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(node), CONCEPTS.NotExpression$Pc)) {
        SNode notExpr = SNodeOperations.cast(SNodeOperations.getParent(node), CONCEPTS.NotExpression$Pc);
        SNodeOperations.replaceWithAnother(notExpr, node);
        SLinkOperations.setTarget(notExpr, LINKS.expression$sv_H, SLinkOperations.getTarget(node, LINKS.leftExpression$sEj));
        SLinkOperations.setTarget(node, LINKS.leftExpression$sEj, notExpr);
      } else if (SNodeOperations.isInstanceOf(SNodeOperations.getParent(node), CONCEPTS.DotExpression$yW) && SNodeOperations.hasRole(node, LINKS.operand$w6IR)) {
        SNode dotExpr = SNodeOperations.cast(SNodeOperations.getParent(node), CONCEPTS.DotExpression$yW);
        SNodeOperations.replaceWithAnother(dotExpr, node);
        SLinkOperations.setTarget(dotExpr, LINKS.operand$w6IR, SLinkOperations.getTarget(node, LINKS.rightExpression$nvX));
        SLinkOperations.setTarget(node, LINKS.rightExpression$nvX, dotExpr);
      } else {
        return true;
      }
      return false;
    }
  }

  public static SNode getBinOp(SNode expr, boolean toRight) {
    SNode parent = SNodeOperations.getParent(expr);
    if (!(SNodeOperations.isInstanceOf(parent, CONCEPTS.BinaryOperation$W1))) {
      return null;
    }
    SNode parentOp = SNodeOperations.cast(parent, CONCEPTS.BinaryOperation$W1);
    boolean right = toRight && SLinkOperations.getTarget(parentOp, LINKS.leftExpression$sEj) == expr;
    boolean left = !(toRight) && SLinkOperations.getTarget(parentOp, LINKS.rightExpression$nvX) == expr;
    if (right || left) {
      return parentOp;
    }
    return getBinOp(parentOp, toRight);
  }
  public static void rotateTree(SNode child, SNode op, boolean isRight) {
    SNode backsideExpr = (isRight ? SLinkOperations.getTarget(child, LINKS.leftExpression$sEj) : SLinkOperations.getTarget(child, LINKS.rightExpression$nvX));
    SNodeOperations.deleteNode(child);
    SNodeOperations.replaceWithAnother(op, child);
    if (backsideExpr != null) {
      SNodeOperations.replaceWithAnother(backsideExpr, op);
      if (isRight) {
        SLinkOperations.setTarget(op, LINKS.rightExpression$nvX, backsideExpr);
      } else {
        SLinkOperations.setTarget(op, LINKS.leftExpression$sEj, backsideExpr);
      }
    } else {
      if (isRight) {
        SLinkOperations.setTarget(child, LINKS.leftExpression$sEj, op);
      } else {
        SLinkOperations.setTarget(child, LINKS.rightExpression$nvX, op);
      }
    }
  }
  public static boolean isBadPriority(SNode child, SNode parent, boolean isRight) {
    return (int) BinaryOperation__BehaviorDescriptor.getPriority_id1653mnvAgo2.invoke(SNodeOperations.asSConcept(SNodeOperations.getConcept(child))) < (int) BinaryOperation__BehaviorDescriptor.getPriority_id1653mnvAgo2.invoke(SNodeOperations.asSConcept(SNodeOperations.getConcept(parent))) || (isRight && ((int) (int) BinaryOperation__BehaviorDescriptor.getPriority_id1653mnvAgo2.invoke(SNodeOperations.asSConcept(SNodeOperations.getConcept(child)))) == ((int) (int) BinaryOperation__BehaviorDescriptor.getPriority_id1653mnvAgo2.invoke(SNodeOperations.asSConcept(SNodeOperations.getConcept(parent)))));
  }

  private static final class CONCEPTS {
    /*package*/ static final SConcept IncompleteLeftParen$Z7 = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x64a1ef64cd9b42ceL, "jetbrains.mps.baseLanguage.structure.IncompleteLeftParen");
    /*package*/ static final SConcept IncompleteRightParen$Sc = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x2052c4520af308e1L, "jetbrains.mps.baseLanguage.structure.IncompleteRightParen");
    /*package*/ static final SConcept ParenthesizedExpression$Ws = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfb4ed32b7fL, "jetbrains.mps.baseLanguage.structure.ParenthesizedExpression");
    /*package*/ static final SConcept Expression$mB = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xf8c37f506fL, "jetbrains.mps.baseLanguage.structure.Expression");
    /*package*/ static final SInterfaceConcept IBinaryLike$eU = MetaAdapterFactory.getInterfaceConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x182da1771714863eL, "jetbrains.mps.baseLanguage.structure.IBinaryLike");
    /*package*/ static final SConcept BinaryOperation$W1 = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfbdeb6fecfL, "jetbrains.mps.baseLanguage.structure.BinaryOperation");
    /*package*/ static final SConcept TernaryOperatorExpression$aq = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x10ef01239c9L, "jetbrains.mps.baseLanguage.structure.TernaryOperatorExpression");
    /*package*/ static final SConcept CastExpression$$8 = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xf940dabe4aL, "jetbrains.mps.baseLanguage.structure.CastExpression");
    /*package*/ static final SConcept BaseAssignmentExpression$PA = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x11b0d00332cL, "jetbrains.mps.baseLanguage.structure.BaseAssignmentExpression");
    /*package*/ static final SConcept AbstractUnaryNumberOperation$Q6 = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x120a4c1f269L, "jetbrains.mps.baseLanguage.structure.AbstractUnaryNumberOperation");
    /*package*/ static final SConcept NotExpression$Pc = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfbcf6bd10dL, "jetbrains.mps.baseLanguage.structure.NotExpression");
    /*package*/ static final SConcept DotExpression$yW = MetaAdapterFactory.getConcept(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x116b46a08c4L, "jetbrains.mps.baseLanguage.structure.DotExpression");
  }

  private static final class LINKS {
    /*package*/ static final SContainmentLink expression$TlhM = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfb4ed32b7fL, 0xfb4ed32b80L, "expression");
    /*package*/ static final SContainmentLink ifFalse$Wbma = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x10ef01239c9L, 0x10ef012cedcL, "ifFalse");
    /*package*/ static final SContainmentLink condition$nwNI = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x10ef01239c9L, 0x10ef012826fL, "condition");
    /*package*/ static final SContainmentLink rightExpression$nvX = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfbdeb6fecfL, 0xfbdeb7a11bL, "rightExpression");
    /*package*/ static final SContainmentLink leftExpression$sEj = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfbdeb6fecfL, 0xfbdeb7a11cL, "leftExpression");
    /*package*/ static final SContainmentLink expression$uRUg = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x120a4c1f269L, 0x120a4c433a6L, "expression");
    /*package*/ static final SContainmentLink expression$XDmN = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xf940dabe4aL, 0xf940dabe4cL, "expression");
    /*package*/ static final SContainmentLink expression$sv_H = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xfbcf6bd10dL, 0xfbcf6c30a4L, "expression");
    /*package*/ static final SContainmentLink operand$w6IR = MetaAdapterFactory.getContainmentLink(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0x116b46a08c4L, 0x116b46a4416L, "operand");
  }

  private static final class PROPS {
    /*package*/ static final SProperty count$FDpi = MetaAdapterFactory.getProperty(0xf3061a5392264cc5L, 0xa443f952ceaf5816L, 0xede3fe8510255edL, 0xede3fe8510255eeL, "count");
  }
}
