commit d667b9ed430f9df5f4c65fa977a4a30091573101 Author: David Malcolm dmalcolm@redhat.com Date: Fri Sep 23 16:38:43 2011 -0400

cpychecker: bulletproof against combinatorial explosion

Introduce a Limits class to track how much work we've done analysing a particular function, and give up if the trace tree becomes larger than a certain number of transitions (hardcoded as 1024 for now).

The selftest for this takes a few seconds on my laptop (before it gives up)

libcpychecker/absinterp.py | 28 ++++- libcpychecker/refcounts.py | 8 +- run-test-suite.py | 10 ++- .../refcounts/combinatorial-explosion/input.c | 153 ++++++++++++++++++++ .../refcounts/combinatorial-explosion/script.py | 22 +++ .../refcounts/combinatorial-explosion/stderr.txt | 2 + 6 files changed, 219 insertions(+), 4 deletions(-) --- diff --git a/libcpychecker/absinterp.py b/libcpychecker/absinterp.py index 2f8bbf7..9025ef9 100644 --- a/libcpychecker/absinterp.py +++ b/libcpychecker/absinterp.py @@ -1003,7 +1003,26 @@ class Resources: logger('acquisitions: %s' % self._acquisitions) logger('releases: %s' % self._releases)

-def iter_traces(fun, stateclass, prefix=None): +class TooComplicated(Exception): + """ + The function is too complicated for the checker to analyze. + """ + pass + +class Limits: + """ + Resource limits, to avoid an analysis going out of control + """ + def __init__(self, maxtrans): + self.maxtrans = maxtrans + self.trans_seen = 0 + + def on_transition(self, transition): + self.trans_seen += 1 + if self.trans_seen > self.maxtrans: + raise TooComplicated() + +def iter_traces(fun, stateclass, prefix=None, limits=None): """ Traverse the tree of traces of program state, returning a list of Trace instances. @@ -1074,8 +1093,13 @@ def iter_traces(fun, stateclass, prefix=None): check_isinstance(transition, Transition) transition.dest.verify()

+ if limits: + limits.on_transition(transition) + + newprefix = prefix.copy().add(transition) + # Recurse: - for trace in iter_traces(fun, stateclass, prefix.copy().add(transition)): + for trace in iter_traces(fun, stateclass, newprefix, limits): result.append(trace) return result else: diff --git a/libcpychecker/refcounts.py b/libcpychecker/refcounts.py index 6f6fd96..3a4420a 100644 --- a/libcpychecker/refcounts.py +++ b/libcpychecker/refcounts.py @@ -2272,7 +2272,13 @@ def check_refcounts(fun, dump_traces=False, show_traces=False, # print(dot) invoke_dot(dot)

- traces = iter_traces(fun, MyState) + try: + traces = iter_traces(fun, MyState, limits=Limits(maxtrans=1024)) + except TooComplicated: + gcc.inform(fun.start, + 'this function is too complicated for the reference-count checker to analyze') + return + if dump_traces: traces = list(traces) dump_traces_to_stdout(traces) diff --git a/run-test-suite.py b/run-test-suite.py index 8ec682b..b50bbce 100644 --- a/run-test-suite.py +++ b/run-test-suite.py @@ -181,8 +181,16 @@ def run_test(testdir): #print 'err: %r' % err.actual c = p.wait()

+ expsuccess = (err.expdata == '') + + # Special case: + if testdir == 'tests/cpychecker/refcounts/combinatorial-explosion': + # This test case should succeed, whilst emitting a note on stderr; + # don't treat the stderr output as leading to an expected failure: + expsuccess = True + # Check exit code: - if err.expdata == '': + if expsuccess: # Expect a successful exit: if c != 0: raise CompilationError(out.actual, err.actual, p, args) diff --git a/tests/cpychecker/refcounts/combinatorial-explosion/input.c b/tests/cpychecker/refcounts/combinatorial-explosion/input.c new file mode 100644 index 0000000..9476a16 --- /dev/null +++ b/tests/cpychecker/refcounts/combinatorial-explosion/input.c @@ -0,0 +1,153 @@ +/* + Copyright 2011 David Malcolm dmalcolm@redhat.com + Copyright 2011 Red Hat, Inc. + + This is free software: you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see + http://www.gnu.org/licenses/. +*/ + +#include <Python.h> + +/* + Verify that the refcount checker can cope with a combinatorial explosion + + Each function call below can have two possible outcomes on the refcount + of the object. +*/ + +PyObject * +test_adding_module_objects(PyObject *m) +{ + PyObject *item = PyString_FromString("foo"); + if (!item) { + return NULL; + } + + /* + Each of these function calls steals a reference to the object if it + succeeds, but can fail. + + Hence the expected ereference count can change at each function call, so + that (in theory) there are 2^N possible outcomes. + + The point of the test is to verify that the checker doesn't take O(2^N) + time for such a case. + */ + + Py_INCREF(item); + PyModule_AddObject(m, "item_001", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_002", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_003", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_004", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_005", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_006", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_007", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_008", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_009", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_010", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_011", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_012", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_013", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_014", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_015", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_016", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_017", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_018", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_019", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_020", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_021", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_022", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_023", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_024", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_025", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_026", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_027", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_028", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_029", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_030", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_031", item); + + Py_INCREF(item); + PyModule_AddObject(m, "item_032", item); + + return item; +} + +/* + PEP-7 +Local variables: +c-basic-offset: 4 +indent-tabs-mode: nil +End: +*/ diff --git a/tests/cpychecker/refcounts/combinatorial-explosion/script.py b/tests/cpychecker/refcounts/combinatorial-explosion/script.py new file mode 100644 index 0000000..fdd5ba3 --- /dev/null +++ b/tests/cpychecker/refcounts/combinatorial-explosion/script.py @@ -0,0 +1,22 @@ +# -*- coding: utf-8 -*- +# Copyright 2011 David Malcolm dmalcolm@redhat.com +# Copyright 2011 Red Hat, Inc. +# +# This is free software: you can redistribute it and/or modify it +# under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see +# http://www.gnu.org/licenses/. + +from libcpychecker import main +main(verify_refcounting=True, + dump_traces=True, + show_traces=False) diff --git a/tests/cpychecker/refcounts/combinatorial-explosion/stderr.txt b/tests/cpychecker/refcounts/combinatorial-explosion/stderr.txt new file mode 100644 index 0000000..31a9f86 --- /dev/null +++ b/tests/cpychecker/refcounts/combinatorial-explosion/stderr.txt @@ -0,0 +1,2 @@ +tests/cpychecker/refcounts/combinatorial-explosion/input.c: In function 'test_adding_module_objects': +tests/cpychecker/refcounts/combinatorial-explosion/input.c:31:1: note: this function is too complicated for the reference-count checker to analyze diff --git a/tests/cpychecker/refcounts/combinatorial-explosion/stdout.txt b/tests/cpychecker/refcounts/combinatorial-explosion/stdout.txt new file mode 100644 index 0000000..e69de29