Skip to content

Instantly share code, notes, and snippets.

@worldbeater
Last active April 21, 2024 21:59
Show Gist options
  • Save worldbeater/51fa42ed4380da9218368bde78024bab to your computer and use it in GitHub Desktop.
Save worldbeater/51fa42ed4380da9218368bde78024bab to your computer and use it in GitHub Desktop.
A Python library and eDSL for code complexity assessment algorithm synthesis, see our paper "A Rule-Based Algorithm and Its Specializations for Measuring the Complexity of Software in Educational Digital Environments" @ https://www.mdpi.com/2073-431X/13/3/75
import ast
def check(rules, env, node, parent):
total, names = 0, []
for name, (spec, check, weight) in rules.items():
if isinstance(node, spec) and check(node, parent):
if score := weight(env, node) if callable(weight) else weight:
total += score
names.append(name)
return total, '+'.join(names)
def report(node, complexity, nesting, reason):
return [(
complexity,
nesting,
reason,
type(node).__name__,
node.lineno,
node.end_lineno,
node.col_offset,
node.end_col_offset,
)] if complexity else []
def complexity(increment, nesting, nesting_increment):
def apply(node, env, parent=None, level=-1):
i, reason = check(increment, env, node, parent)
n, _ = check(nesting, env, node, parent)
ni, _ = check(nesting_increment, env, node, parent)
ml = max(0, level)
score = i + ni * ml
reports = report(node, score, ml, reason)
for child in ast.iter_child_nodes(node):
cs, rep = apply(child, env, node, level + n)
reports += rep
score += cs
return score, reports
return apply
def max_complexity(module, complexity):
maxc = 0
functions = []
for node in ast.walk(module):
if not isinstance(node, ast.FunctionDef | ast.AsyncFunctionDef):
continue
score, reps = complexity(node)
toplevel = report(node, score, -1, '')
if score > maxc:
maxc = score
functions.append(toplevel + reps)
return maxc, functions
def humanize(report):
lines = []
for cc, nesting, reason, name, ls, le, cs, ce in report:
ne = f' (nesting={nesting})' if nesting > 0 else ''
sign = '+' if nesting >= 0 else ''
note = f'L{ls:02d}:{cs:02d}-L{le:02d}:{ce:02d} {sign}{cc}{ne} {name} [{reason}]'
lines.append(note)
return '\n'.join(lines)
Function = (
ast.FunctionDef,
ast.AsyncFunctionDef,
)
Loop = (
ast.For,
ast.AsyncFor,
ast.While,
)
Generator = (
ast.ListComp,
ast.DictComp,
ast.SetComp,
ast.GeneratorExp,
)
HasOrElse = Loop + (
ast.Try,
)
ControlFlowBreak = Loop + Generator + (
ast.Match,
ast.ExceptHandler,
ast.IfExp,
ast.If,
)
NestedControlFlowBreak = Loop + Generator + (
ast.Match,
ast.ExceptHandler,
ast.IfExp,
)
Nesting = NestedControlFlowBreak + (
ast.With,
ast.AsyncWith,
ast.ClassDef,
ast.Lambda,
)
def true(node, parent):
return True
def is_recurrent(func: Function, parent):
return any(isinstance(node, ast.Call) and
isinstance(node.func, ast.Name) and
node.func.id == func.name
for node in ast.walk(func))
def has_else(node: ast.If, parent):
return (len(node.orelse) and
not (len(node.orelse) == 1 and
isinstance(node.orelse[0], ast.If)))
def not_decorator(node: Function, parent):
return not (len(node.body) == 2 and
isinstance(node.body[0], Function) and
isinstance(node.body[1], ast.Return))
def not_elif(node: ast.If, parent):
return not (isinstance(parent, ast.If) and
len(parent.orelse) == 1 and
parent.orelse[0] == node)
def get_du(node):
defs, uses = [], []
for node in ast.walk(node):
match node:
case ast.Name(name, ast.Load()):
uses.append(name)
case ast.Name(name, ast.Store()):
defs.append(name)
return defs, uses
def assign(env: set, node):
defs, uses = get_du(node)
score = sum(1 for var in defs if var in env and var not in uses)
env.update(defs)
return score
def aug_assign(env: set, node):
defs, _ = get_du(node)
env.update(defs)
return 0
def cognitive(tree):
metric = complexity(
increment=dict(
ifelse=(ast.If, has_else, 1),
recursion=(Function, is_recurrent, 1),
orelse=(HasOrElse, lambda node, p: bool(node.orelse), 1),
controlflowbreak=(ControlFlowBreak, true, 1),
comprehensionifs=(Generator, true, lambda e, node: sum(len(g.ifs) for g in node.generators)),
boolop=(ast.BoolOp, true, 1)),
nesting=dict(
ifelse=(ast.If, not_elif, 1),
nestedfunction=(Function, not_decorator, 1),
nestedblock=(Nesting, true, 1)),
nesting_increment=dict(
ifelse=(ast.If, not_elif, 1),
controlflowbreak=(NestedControlFlowBreak, true, 1)))
return metric(tree, set())
def cyclomatic(tree):
metric = complexity(
increment=dict(
tryexcept=(ast.Try, true, lambda e, node: len(node.handlers) + bool(node.orelse)),
boolops=(ast.BoolOp, true, lambda e, node: len(node.values) - 1),
matchcases=(ast.Match, true, lambda e, node: len(node.cases)),
comprehensionifs=(Generator, true, lambda e, node: sum(len(g.ifs) + 1 for g in node.generators)),
loop=(Loop, true, lambda e, node: bool(node.orelse) + 1),
controlflowbreak=((ast.If, ast.IfExp, *Function), true, 1)),
nesting=dict(),
nesting_increment=dict())
return metric(tree, set())
def educational(tree):
metric = complexity(
increment=dict(
ifelse=(ast.If, has_else, 1),
recursion=(Function, is_recurrent, 1),
orelse=(HasOrElse, lambda node, p: bool(node.orelse), 1),
controlflowbreak=(ControlFlowBreak, true, 1),
# Conditionals in comprehensions are readable.
# comprehensionifs=(Generator, true, lambda e, node: sum(len(g.ifs) for g in node.generators)),
boolop=(ast.BoolOp, true, 1),
# Cyclomatic complexity rules.
boolops=(ast.BoolOp, true, lambda e, node: max(0, len(node.values) - 2)),
matchcases=(ast.Match, true, lambda e, node: max(0, len(node.cases) - 1)),
function=(Function, true, 1),
# Penalties for break and continue.
loopbreak=(ast.Break | ast.Continue, true, 1),
# Variable redefinition rules.
redefine=(ast.Assign | ast.AnnAssign | ast.NamedExpr, true, assign),
augassign=(ast.AugAssign, true, aug_assign),
name=(ast.Name, lambda node, p: isinstance(node.ctx, ast.Store), lambda e, node: e.update(node.id)),
arg=(ast.arg, true, lambda e, node: e.update(node.arg))),
nesting=dict(
ifelse=(ast.If, not_elif, 1),
nestedfunction=(Function, not_decorator, 1),
nestedblock=(Nesting, true, 1)),
nesting_increment=dict(
ifelse=(ast.If, not_elif, 1),
controlflowbreak=(NestedControlFlowBreak, true, 1)))
return metric(tree, set())
import inspect
import doctest
def overriden_symbol(klass):
'''
Test case #1. Code ported from Java, see p.17 of the paper:
Campbell G.A. Cognitive Complexity, SonarSource, 2021.
https://www.sonarsource.com/docs/CognitiveComplexity.pdf
>>> cognitive(ast.parse(inspect.getsource(overriden_symbol)))[0]
19
>>> cyclomatic(ast.parse(inspect.getsource(overriden_symbol)))[0]
10
>>> educational(ast.parse(inspect.getsource(overriden_symbol)))[0]
21
'''
if klass.unknown(): # +1
return Symbols.UnknownMethodSymbol
unknown = False
symbols = klass.symbol().members().lookup(name);
for override in symbols: # +1
if override.kind(JavaSymbol.MTH) and ( # +2 (nesting = 1)
not override.static()): # +1
if can_override(override): # +3 (nesting = 2)
overriding = check(override, klass)
if overriding is None: # +4 (nesting = 3)
if not unknown: # +5 (nesting = 4)
unknown = True # +1 (variable redefinition)
elif overriding: # +1
return override
if unknown: # +1
return Symbols.UnknownMethodSymbol
return None
def add_version(entry, txn):
'''
Test case #2. Code ported from Java, see p.18 of the paper:
Campbell G.A. Cognitive Complexity, SonarSource, 2021.
https://www.sonarsource.com/docs/CognitiveComplexity.pdf
>>> cognitive(ast.parse(inspect.getsource(add_version)))[0]
35
>>> cyclomatic(ast.parse(inspect.getsource(add_version)))[0]
14
>>> educational(ast.parse(inspect.getsource(add_version)))[0]
38
'''
ti = persistit.transaction()
while True: # +1
try:
if first is not None: # +2 (nesting = 1)
if first.version() > entry.version(): # +3 (nesting = 2)
raise RollbackException()
if txn.active(): # +3 (nesting = 2)
for e in e.get_previous(): # +4 (nesting = 3)
version = e.version()
depends = ti.dependency(version, txn.status(), 0)
if depends == TimedOut: # +5 (nesting = 4)
raise RetryException()
if depends != 0 and ( # +5 (nesting = 4)
depends != Aborted): # +1
raise RollbackException()
entry.set_previous(first)
first = entry
break
except RetryException as re: # +2 (nesting = 1)
try:
depends = persistit.transaction() # +1 (variable redefinition)
if depends != 0 and ( # +3 (nesting = 2)
depends != Aborted): # +1
raise RollbackException()
except InterruptedException as ie: # +3 (nesting = 2)
raise PersistitInterruptedException(ie)
except InterruptedException as ie: # +2 (nesting = 1)
raise PersistitInterruptedException(ie)
def to_regexp(ant, ds):
'''
Test case #3. Code ported from Java, see p.19 of the paper:
Campbell G.A. Cognitive Complexity, SonarSource, 2021.
https://www.sonarsource.com/docs/CognitiveComplexity.pdf
>>> cognitive(ast.parse(inspect.getsource(to_regexp)))[0]
20
>>> cyclomatic(ast.parse(inspect.getsource(to_regexp)))[0]
12
>>> educational(ast.parse(inspect.getsource(to_regexp)))[0]
21
'''
eds = '\\' + ds
sb = []
sb.append('^')
i = (1 if ant.startswith('/') or # +1
ant.startswith('\\') else 0) # +1
while i < len(ant): # +1
ch = ant[i]
if SpecialChars.find(ch) != -1: # +2 (nesting = 1)
sb.append('\\').append(ch)
elif ch == '*': # +1
if i + 1 < len(ant) and ( # +3 (nesting = 2)
ant[i + 1] == '*'): # +1
if i + 2 < len(ant) and ( # +4 (nesting = 3)
slash(ant[i + 2])): # +1
sb.append('(?:.*').append(eds).append('|)')
i += 2
else: # +1
sb.append('.*')
i += 1
else: # +1
sb.append('[^').append(eds).append(']*?')
elif ch == '?': # +1
sb.append('[^').append(eds).append(']')
elif slash(ch): # +1
sb.append(eds)
else: # +1
sb.append(ch)
i += 1
sb.append('$')
return ''.join(sb)
def save(self, options, callback):
'''
Test case #4. Code ported from JS, see p.20 of the paper:
Campbell G.A. Cognitive Complexity, SonarSource, 2021.
https://www.sonarsource.com/docs/CognitiveComplexity.pdf
>>> cognitive(ast.parse(inspect.getsource(save)))[0]
20
>>> cyclomatic(ast.parse(inspect.getsource(save)))[0]
12
>>> educational(ast.parse(inspect.getsource(save)))[0]
24
'''
if callable(options): # +1
callback = options
options = {}
options = options or {} # +1
def validate(err):
if err: # +2 (nesting = 1)
callback and callback(None, err) # +1
return
def sync(err, response):
facade = {'options': options, 'response': response}
parsed = None
if err: # +3 (nesting = 2)
facade['error'] = err
facade['src'] = 'save'
self.fire(EVT_ERROR, facade)
else: # +1
if not self._saveEvent: # +4 (nesting = 3)
self._saveEvent = self.publish(EVT_SAVE, {
'preventable': False
})
if response: # +4 (nesting = 3)
parsed = self._parse(response) # +1 (variable redefinition)
facade['parsed'] = parsed
self.setAttrs(parsed, options)
self.changed = {}
self.fire(EVT_SAVE, facade)
callback and callback(*arguments) # +1
arg = 'create' if self.new() else 'update' # +2 (nesting = 1)
self.sync(arg, options, sync)
self._validate(self.toJSON(), validate)
err = self._validate(self.toJSON(), validate)
return self
def my_method():
'''
Test case #5. Code ported from Java, see p.9 of the paper:
Campbell G.A. Cognitive Complexity, SonarSource, 2021.
https://www.sonarsource.com/docs/CognitiveComplexity.pdf
>>> cognitive(ast.parse(inspect.getsource(my_method)))[0]
9
>>> cyclomatic(ast.parse(inspect.getsource(my_method)))[0]
6
>>> educational(ast.parse(inspect.getsource(my_method)))[0]
10
'''
try:
if condition1: # +1
for i in range(10): # +2 (nesting = 1)
while condition2: # +3 (nesting = 2)
pass
except Exception as e: # +1
if condition2: # +2 (nesting = 1)
pass
def redefine_example(y):
'''
Test case #6. Example of variable redefinition.
wiki.sei.cmu.edu/confluence/display/c/DCL01-C.+Do+not+reuse+variable+names+in+subscopes
>>> cognitive(ast.parse(inspect.getsource(redefine_example)))[0]
0
>>> cyclomatic(ast.parse(inspect.getsource(redefine_example)))[0]
1
>>> educational(ast.parse(inspect.getsource(redefine_example)))[0]
5
'''
x = 10
x = 20 # +1 (variable redefinition)
y = 30 # +1 (variable redefinition)
x, y = 10, 20 # +2 (variable redefinition)
x, y = x, y
return x, y
def test_maxcc():
funcs = [overriden_symbol, add_version, to_regexp, save, my_method]
file = '\n'.join(inspect.getsource(func) for func in funcs)
maxcc, _ = max_complexity(ast.parse(file), cognitive)
assert maxcc == 35
def test_humanize():
assert humanize([]) == ''
assert humanize([
(1, 0, 'controlflowbreak', 'IfExp', 13, 14, 9, 36),
(1, 1, 'controlflowbreak', 'BoolOp', 13, 14, 14, 29)
]) == ('L13:9-L14:36 +1 IfExp [controlflowbreak]\n'
'L13:14-L14:29 +1 (nesting=1) BoolOp [controlflowbreak]')
results = doctest.testmod()
assert results.attempted == 18
assert results.failed == 0
test_maxcc()
test_humanize()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment