tools/kprint/addBrackets.cpp
bool requiresBracketWithSimpleAlgorithm(
    KORECompositePattern *outer, KORECompositePattern *leftCapture,
    KORECompositePattern *rightCapture, KOREPattern *inner, int position,
    PrettyPrintData const &data) {
  if (auto innerComposite = dynamic_cast<KORECompositePattern *>(inner)) {
    std::string innerName = innerComposite->getConstructor()->getName();
    if (innerName == outer->getConstructor()->getName()) {
      if (data.assoc.count(innerName)) {
        return false;
      }
    }
    if (innerName == "\\dv") {
      return false;
    }
    Fixity fixity = getFixity(position, outer->getConstructor(), data);
    if (fixity == EMPTY) {
      return false;
    }
    bool priority = isPriorityWrong(outer, innerComposite, position, data);
    if (priority) {
      return true;
    }
    if (data.terminals.at(innerName) == "0") {
      return false;
    }
    Fixity innerFixity = getFixity(innerComposite->getConstructor(), data);
    if ((innerFixity & BARE_RIGHT) && rightCapture != nullptr) {
      bool inversePriority = isPriorityWrong(
          innerComposite, rightCapture,
          innerComposite->getArguments().size() - 1, data);
      Fixity rightCaptureFixity
          = getFixity(rightCapture->getConstructor(), data);
      if (!inversePriority && (rightCaptureFixity & BARE_LEFT)) {
        return true;
      }
    }
    if ((innerFixity & BARE_LEFT) && leftCapture != nullptr) {
      bool inversePriority
          = isPriorityWrong(innerComposite, leftCapture, 0, data);
      Fixity leftCaptureFixity = getFixity(leftCapture->getConstructor(), data);
      if (!inversePriority && (leftCaptureFixity & BARE_RIGHT)) {
        return true;
      }
    }
    return false;
  } else {
    return false;
  }
}
/**
 * Computes whether a bracket needs to appear around `inner`.
 *
 * outer: the parent of `inner`
 *
 * leftCapture: the left capture of `inner`
 *
 * rightCapture: the right capture of `inner`
 *
 * inner: the pattern to test
 *
 * position: the position of `inner` within the nonterminals of `outer`
 *
 * data: pretty printing metadata
 *
 * returns: true if a bracket is required according to this algorithm. Roughly
 * speaking, parentheses are not needed around associative symbols, constants,
 * or patterns that appear between two terminals in their parent. Otherwise,
 * parentheses are needed if priority or associativity forbids the term inside
 * its parent, or if the term begins or ends with a nonterminal and priority
 * and associativity do not forbid the term from appearing inside its left
 * or right capture, respectively, and its left or right capture does not
 * end or begin, respectively, with a terminal.
 *
 * Warning: this algorithm is *unsound*. There is no guarantee that after
 * it completes, the resulting term can be unparsed into a string that will
 * parse unambiguously as the original AST. Indeed, the problem of inserting
 * brackets into an AST in order to ensure this property is NP-hard, and
 * grammars can be constructed such that solving the unparsing problem is
 * equivalent to boolean satisfiability. This algorithm is merely a linear-time
 * approximation of the general problem which performs very well in most
 * real-world grammars, especially the common expression-grammar category of
 * grammar where parentheses are most often required in practice.
 *
 * As an example, consider the following simple grammar:
 *
 * syntax Exp ::= Exp "++" | "++" Exp | Exp Exp | "(" Exp ")" [bracket]
 *
 * The terms `(1 ++) 1` and `1 (++ 1)` will not have brackets inserted
 * into them by this algorithm, even though they are required.
 */
Computes whether a bracket needs to appear around `inner`.
outer: the parent of `inner`

the left capture of `inner`

the right capture of `inner`

the pattern to test

the position of `inner` within the nonterminals of `outer`

pretty printing metadata

true if a bracket is required according to this algorithm. Roughly
speaking, parentheses are not needed around associative symbols, constants,
or patterns that appear between two terminals in their parent. Otherwise,
parentheses are needed if priority or associativity forbids the term inside
its parent, or if the term begins or ends with a nonterminal and priority
and associativity do not forbid the term from appearing inside its left
or right capture, respectively, and its left or right capture does not
end or begin, respectively, with a terminal.

this algorithm is *unsound*. There is no guarantee that after
it completes, the resulting term can be unparsed into a string that will
parse unambiguously as the original AST. Indeed, the problem of inserting
brackets into an AST in order to ensure this property is NP-hard, and
grammars can be constructed such that solving the unparsing problem is
equivalent to boolean satisfiability. This algorithm is merely a linear-time
approximation of the general problem which performs very well in most
real-world grammars, especially the common expression-grammar category of
grammar where parentheses are most often required in practice.

As an example, consider the following simple grammar.



The terms `(1 ++) 1` and `1 (++ 1)` will not have brackets inserted
into them by this algorithm, even though they are required.
Computes whether a bracket needs to appear around ` inner ` . outer : the parent of ` inner ` the left capture of ` inner ` the right capture of ` inner ` the pattern to test the position of ` inner ` within the nonterminals of ` outer ` pretty printing metadata true if a bracket is required according to this algorithm . Roughly speaking parentheses are not needed around associative symbols constants or patterns that appear between two terminals in their parent . Otherwise parentheses are needed if priority or associativity forbids the term inside its parent or if the term begins or ends with a nonterminal and priority and associativity do not forbid the term from appearing inside its left or right capture respectively and its left or right capture does not end or begin respectively with a terminal . this algorithm is * unsound * . There is no guarantee that after it completes the resulting term can be unparsed into a string that will parse unambiguously as the original AST . Indeed the problem of inserting brackets into an AST in order to ensure this property is NP - hard and grammars can be constructed such that solving the unparsing problem is equivalent to boolean satisfiability . This algorithm is merely a linear - time approximation of the general problem which performs very well in most real - world grammars especially the common expression - grammar category of grammar where parentheses are most often required in practice . As an example consider the following simple grammar . The terms ` ( 1 ++ ) 1 ` and ` 1 ( ++ 1 ) ` will not have brackets inserted into them by this algorithm even though they are required .
bool requiresBracketWithSimpleAlgorithm(
    KORECompositePattern *outer, KORECompositePattern *leftCapture,
    KORECompositePattern *rightCapture, KOREPattern *inner, int position,
    PrettyPrintData const &data) {
  if (auto innerComposite = dynamic_cast<KORECompositePattern *>(inner)) {
    std::string innerName = innerComposite->getConstructor()->getName();
    if (innerName == outer->getConstructor()->getName()) {
      if (data.assoc.count(innerName)) {
        return false;
      }
    }
    if (innerName == "\\dv") {
      return false;
    }
    Fixity fixity = getFixity(position, outer->getConstructor(), data);
    if (fixity == EMPTY) {
      return false;
    }
    bool priority = isPriorityWrong(outer, innerComposite, position, data);
    if (priority) {
      return true;
    }
    if (data.terminals.at(innerName) == "0") {
      return false;
    }
    Fixity innerFixity = getFixity(innerComposite->getConstructor(), data);
    if ((innerFixity & BARE_RIGHT) && rightCapture != nullptr) {
      bool inversePriority = isPriorityWrong(
          innerComposite, rightCapture,
          innerComposite->getArguments().size() - 1, data);
      Fixity rightCaptureFixity
          = getFixity(rightCapture->getConstructor(), data);
      if (!inversePriority && (rightCaptureFixity & BARE_LEFT)) {
        return true;
      }
    }
    if ((innerFixity & BARE_LEFT) && leftCapture != nullptr) {
      bool inversePriority
          = isPriorityWrong(innerComposite, leftCapture, 0, data);
      Fixity leftCaptureFixity = getFixity(leftCapture->getConstructor(), data);
      if (!inversePriority && (leftCaptureFixity & BARE_RIGHT)) {
        return true;
      }
    }
    return false;
  } else {
    return false;
  }
}
bool requiresBracketWithSimpleAlgorithm ( KORECompositePattern * outer , KORECompositePattern * leftCapture , KORECompositePattern * rightCapture , KOREPattern * inner , int position , PrettyPrintData const & data ) { if ( auto innerComposite = dynamic_cast < KORECompositePattern * > ( inner ) ) { std :: string innerName = innerComposite -> getConstructor ( ) -> getName ( ) ; if ( innerName == outer -> getConstructor ( ) -> getName ( ) ) { if ( data . assoc . count ( innerName ) ) { return false ; } } if ( innerName == " \\ " ) { return false ; } Fixity fixity = getFixity ( position , outer -> getConstructor ( ) , data ) ; if ( fixity == EMPTY ) { return false ; } bool priority = isPriorityWrong ( outer , innerComposite , position , data ) ; if ( priority ) { return true ; } if ( data . terminals . at ( innerName ) == " " ) { return false ; } Fixity innerFixity = getFixity ( innerComposite -> getConstructor ( ) , data ) ; if ( ( innerFixity & BARE_RIGHT ) && rightCapture != nullptr ) { bool inversePriority = isPriorityWrong ( innerComposite , rightCapture , innerComposite -> getArguments ( ) . size ( ) - 1 , data ) ; Fixity rightCaptureFixity = getFixity ( rightCapture -> getConstructor ( ) , data ) ; if ( ! inversePriority && ( rightCaptureFixity & BARE_LEFT ) ) { return true ; } } if ( ( innerFixity & BARE_LEFT ) && leftCapture != nullptr ) { bool inversePriority = isPriorityWrong ( innerComposite , leftCapture , 0 , data ) ; Fixity leftCaptureFixity = getFixity ( leftCapture -> getConstructor ( ) , data ) ; if ( ! inversePriority && ( leftCaptureFixity & BARE_RIGHT ) ) { return true ; } } return false ; } else { return false ; } }
Computes whether a bracket needs to appear around `inner`.
Computes whether a bracket needs to appear around ` inner ` .