Exponential time complexity when generating code from AST with nested sizeofs.

[huzecong]

Minimum example to reproduce:

from pycparser.c_parser import CParser
from pycparser.c_generator import CGenerator

# Code is 30 nested `sizeof`s.
code = "int x = sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(sizeof(int))))))))))))))))))))))))))))));"
tree = CParser().parse(code)
print(tree)  # the tree is correct
print(CGenerator().visit(tree))  # this never stops

The issue is within CGenerator.visit_UnaryOp:

pycparser/pycparser/c_generator.py

Lines 61 to 72 in 61eac63

	def visit_UnaryOp(self, n):
	operand = self._parenthesize_unless_simple(n.expr)
	if n.op == 'p++':
	return '%s++' % operand
	elif n.op == 'p--':
	return '%s--' % operand
	elif n.op == 'sizeof':
	# Always parenthesize the argument of sizeof since it can be
	# a name.
	return 'sizeof(%s)' % self.visit(n.expr)
	else:
	return '%s%s' % (n.op, operand)

In the case where n.op is sizeof, n.expr is visited twice. When there are nested sizeofs, the leaf nodes will be visited an exponential number of times. (Although in reality such code wouldn't make sense)

I can create a PR with a few of my previous issues, but it might take a few days before I can work on this.

[eliben]

Interesting find. Feel free to send a PR to fix this.