Repository: eliben/pycparser

Issue:
Precedence-aware CGenerator
I ran into the issue that in a code more than 256 variables are summed up. The `CGenerator` turned this into >256 nested BinaryOperators with that many parenthesis, that in turn was something clang did not like (be default).

I wrote a small generator which takes precedence into account for binary operators:

```python
class LessParanthesizingCGenerator(CGenerator):
    def get_BinaryOp_precedence(self, n):
        """
        Gives precedence for op of n, otherwise -1.
        
        Lower number have precedence over higher numbers.
        """
        binary_op_precedence = {
            # based on https://en.cppreference.com/w/c/language/operator_precedence
            '*': 3, '%': 3,
            '-': 4, '+': 4,
            '<<': 5, '>>': 5,
            '<': 6, '<=': 6, '>': 6, '>=': 6,
            '==': 7, '!=': 7,
            '&': 8,
            '^': 9,
            '|': 10,
            '&&': 11,
            '||': 12
        }
        if not isinstance(n, c_ast.BinaryOp):
            return -1
        else:
            return binary_op_precedence[n.op]

    def visit_BinaryOp(self, n):
        p = self.get_BinaryOp_precedence(n)
        lval_str = self._parenthesize_if(n.left,
                            lambda d: not self._is_simple_node(d) and 
                                      self.get_BinaryOp_precedence(d) > p)
        rval_str = self._parenthesize_if(n.right,
                            lambda d: not self._is_simple_node(d) and
                                      self.get_BinaryOp_precedence(d) >= p)
        return '%s %s %s' % (lval_str, n.op, rval_str)
```

Would you like me to make a pull request and if so, is this implementation sufficient for now? Tests I would of cause add.

Discussion:
cod3monk: Sorry for being a little trigger-happy on commits ;)
eliben: > Sorry for being a little trigger-happy on commits ;)

No worries, I squash them anyway.

When you're done addressing the code review, please either "Request code review " again (using the refresh icon next to my name), or add a comment saying so

Patch:
diff --git a/pycparser/c_generator.py b/pycparser/c_generator.py
index 53c26fd..c494176 100644
--- a/pycparser/c_generator.py
+++ b/pycparser/c_generator.py
@@ -14,11 +14,17 @@ class CGenerator(object):
         return a value from each visit method, using string accumulation in
         generic_visit.
     """
-    def __init__(self):
+    def __init__(self, reduce_parentheses=False):
+        """ Constructs C-code generator
+
+            reduce_parentheses:
+                if True, eliminates needless parentheses on binary operators
+        """
         # Statements start with indentation of self.indent_level spaces, using
         # the _make_indent method
         #
         self.indent_level = 0
+        self.reduce_parentheses = reduce_parentheses
 
     def _make_indent(self):
         return ' ' * self.indent_level
@@ -72,11 +78,49 @@ class CGenerator(object):
             else:
                 return '%s%s' % (n.op, operand)
 
+    # Precedence map of binary operators:
+    precedence_map = {
+        # Some what of a duplicate of c_paarser.CParser.precedence
+        # Higher numbers are stronger binding
+        '||': 0,  # weakest binding
+        '&&': 1,
+        '|': 2,
+        '^': 3,
+        '&': 4,
+        '==': 5, '!=': 5,
+        '>': 6, '>=': 6, '<': 6, '<=': 6,
+        '>>': 7, '<<': 7,
+        '+': 8, '-': 8,
+        '*': 9, '/': 9, '%': 9  # strongest binding
+    }
+
     def visit_BinaryOp(self, n):
-        lval_str = self._parenthesize_if(n.left,
-                            lambda d: not self._is_simple_node(d))
-        rval_str = self._parenthesize_if(n.right,
-                            lambda d: not self._is_simple_node(d))
+        # Note: all binary operators are left-to-right associative
+        #
+        # If `n.left.op` has a stronger or equally binding precedence in
+        # comparison to `n.op`, no parenthesis are needed for the left:
+        # e.g., `(a*b) + c` is equivelent to `a*b + c`, as well as
+        #       `(a+b) - c` is equivelent to `a+b - c` (same precedence).
+        # If the left operator is weaker binding than the current, then
+        # parentheses are necessary:
+        # e.g., `(a+b) * c` is NOT equivelent to `a+b * c`.
+        lval_str = self._parenthesize_if(
+            n.left,
+            lambda d: not (self._is_simple_node(d) or
+                      self.reduce_parentheses and isinstance(d, c_ast.BinaryOp) and
+                      self.precedence_map[d.op] >= self.precedence_map[n.op]))
+        # If `n.right.op` has a stronger -but not equal- binding precedence,
+        # parenthesis can be omitted on the right:
+        # e.g., `a + (b*c)` is equivelent to `a + b*c`.
+        # If the right operator is weaker or equally binding, then parentheses
+        # are necessary:
+        # e.g., `a * (b+c)` is NOT equivelent to `a * b+c` and
+        #       `a - (b+c)` is NOT equivelent to `a - b+c` (same precedence).
+        rval_str = self._parenthesize_if(
+            n.right,
+            lambda d: not (self._is_simple_node(d) or
+                      self.reduce_parentheses and isinstance(d, c_ast.BinaryOp) and
+                      self.precedence_map[d.op] > self.precedence_map[n.op]))
         return '%s %s %s' % (lval_str, n.op, rval_str)
 
     def visit_Assignment(self, n):
diff --git a/pycparser/c_parser.py b/pycparser/c_parser.py
index c2d82f7..0536e58 100644
--- a/pycparser/c_parser.py
+++ b/pycparser/c_parser.py
@@ -491,6 +491,7 @@ class CParser(PLYParser):
     ##
     ## Precedence and associativity of operators
     ##
+    # If this changes, c_generator.CGenerator.precedence_map needs to change as well
     precedence = (
         ('left', 'LOR'),
         ('left', 'LAND'),


Test patch:
diff --git a/tests/test_c_generator.py b/tests/test_c_generator.py
index 159c763..7937525 100644
--- a/tests/test_c_generator.py
+++ b/tests/test_c_generator.py
@@ -61,19 +61,22 @@ class TestFunctionDeclGeneration(unittest.TestCase):
 
 
 class TestCtoC(unittest.TestCase):
-    def _run_c_to_c(self, src):
+    def _run_c_to_c(self, src, *args, **kwargs):
         ast = parse_to_ast(src)
-        generator = c_generator.CGenerator()
+        generator = c_generator.CGenerator(*args, **kwargs)
         return generator.visit(ast)
 
-    def _assert_ctoc_correct(self, src):
+    def _assert_ctoc_correct(self, src, *args, **kwargs):
         """ Checks that the c2c translation was correct by parsing the code
             generated by c2c for src and comparing the AST with the original
             AST.
+
+            Additional arguments are passed to CGenerator.__init__.
         """
-        src2 = self._run_c_to_c(src)
+        src2 = self._run_c_to_c(src, *args, **kwargs)
         self.assertTrue(compare_asts(parse_to_ast(src), parse_to_ast(src2)),
-                        src2)
+                        "{!r} != {!r}".format(src, src2))
+        return src2
 
     def test_trivial_decls(self):
         self._assert_ctoc_correct('int a;')
@@ -361,6 +364,26 @@ class TestCtoC(unittest.TestCase):
         src = 'int x = ' + src + ';'
         self._assert_ctoc_correct(src)
 
+    def test_flattened_binaryops(self):
+        # codes with minimum number of (necessary) parenthesis:
+        test_snippets = [
+            'int x = a*b*c*d;',
+            'int x = a+b*c*d;',
+            'int x = a*b+c*d;',
+            'int x = a*b*c+d;',
+            'int x = (a+b)*c*d;',
+            'int x = (a+b)*(c+d);',
+            'int x = (a+b)/(c-d);',
+            'int x = a+b-c-d;',
+            'int x = a+(b-c)-d;'
+        ]
+        for src in test_snippets:
+            src2 = self._assert_ctoc_correct(src, reduce_parentheses=True)
+            self.assertTrue(
+                src2.count('(') == src.count('('),
+                msg="{!r} did not have minimum number of parenthesis, should be like {!r}.".format(
+                    src2, src))
+
 
 class TestCasttoC(unittest.TestCase):
     def _find_file(self, name):