Checking Suspicious Functions

[Michael Hudson]

Moshe Zadka <moshez at math.huji.ac.il> writes:

> After Tim and mine discusion, I thought writing code for a change would be
> nice. Here's a rough draft of my "checking whether a function can return a
> value from one place and return None from another" code:
> 
> --- suspect.py
> import dis # for HAVE_ARGUMENT, and opname
> 
> # currently we're to dumb to understand this is valid:
> # if x:
> #	return 1
> # else:
> #	return 0
> 

I had written some code for splitting Python bytecode into basic
blocks a couple weeks back, so I've used that to whip up an effort
that *is* clever enough to cope with the above.

I think it takes exceptions to confuse it - how do they fit into the
basic block view of the world?

Large chunks of the standard library seem to pass muster, which is
good...

Comments appreciated (even if it's "Don't attach the file like *that*,
doofus").

Cheers,
M.



-- 
very few people approach me in real life and insist on proving they are
drooling idiots.                         -- Erik Naggum, comp.lang.lisp


===File ~/src/python/returnnanny/returnnanny.py=============
from bytecodehacks.code_editor import Function
from bytecodehacks.ops import *
import block_analysis

def _is_argumented_return(op):
    if op.__class__ is not LOAD_CONST:
        return 1
    if op.arg is not 0:
        return 1
    return 0

def is_sensible(func):
    code = Function(func).func_code
    blocks = block_analysis.block_analyse(code)

    returns = []

    cmpval = 0
    
    for block in blocks.values():
        if block.body[-1].__class__ is RETURN_VALUE:
            if len(block.body) < 2:
                cmpval = 1
            else:
                returns.append( block.body[-2] )

    if cmpval == 0:
        cmpval = _is_argumented_return(returns[0])

    for op in returns[1:]:
        if _is_argumented_return(op) <> cmpval:
            return 0

    return 1

import types

def check_module(module):
    for i in module.__dict__.values():
        if type(i) is types.FunctionType:
            print i.func_name, is_sensible(i)
============================================================

===File ~/src/python/returnnanny/block_analysis.py==========
from bytecodehacks.ops import *

class BasicBlock:
    def __init__(self,body,label):
        self.body = body
        self.label = label
        self.exits = []
        self.entries = []
    def __repr__(self):
        return """\
 %3d body: %s
     exits %-20s entries %s"""%(self.label,`self.body`,`self.exits`,`self.entries`)

def isJump(op):
    """ isJump(op: Opcode) -> Boolean

Return true if execution of op can result in transfer of control."""

    return op.is_jump() or op.__class__ is RETURN_VALUE

def basic_blockize(code):
    """ basic_blockize(code: CodeObject) -> {Int:BasicBlock}

Return the list of basic blocks of the code object.  NB: |code| is
DESTRUCTIVELY MODIFIED to remove line nos. and SETUP_LOOPs. """
    
    cs = code.co_code

    targets = []
    for label in cs.labels:
        targets.append( label.op )

    blocks = []
    curblock = []

    for op in cs:
        if op in targets:
            blocks.append(curblock)
            curblock = []
            
        curblock.append(op)
        
        if isJump(op):
            blocks.append(curblock)
            curblock = []

    blocks = filter(None,blocks)

    block_objects = {}

    for i in range(len(blocks)):
        block_objects[i] = BasicBlock(blocks[i],i)

    for block in block_objects.values():
        last_op = block.body[-1]
        if last_op.is_jump():
            target = last_op.label.op
            for t in block_objects.values():
                if t.body[0] == target:
                    block.exits.append( t.label )
                    t.entries.append( block.label )
        if  (last_op.__class__ is not RETURN_VALUE
             and last_op.__class__ is not JUMP_ABSOLUTE
             and last_op.__class__ is not JUMP_FORWARD):
            block.exits.append( block.label + 1 )
            block_objects[ block.label + 1].entries.append( block.label )

    return block_objects

def eliminate_unreachable_blocks(blocks):
    """ eliminate_unreachable_blocks(blocks: {Int:BasicBlock}) -> None

remove unreachable blocks from the sequence """

    reachable = [0]

    for i in reachable:
        for l in blocks[i].exits:
            if l not in reachable:
                reachable.append( l )

    newblocks = []

    for block in blocks.values():
        if block.label in reachable:
            newexits = []
            for l in block.exits:
                if l in reachable:
                    newexits.append( l )
            block.exits = newexits
            
            newentries = []
            for l in block.entries:
                if l in reachable:
                    newentries.append( l )
            block.entries = newentries
            
            newblocks.append( block )
        else:
            del blocks[block.label]
                
def print_blocks(blocks):
    v = blocks.keys()
    v.sort()
    for i in v: print blocks[i]

def block_analyse(code):
    """ block_analyse(code:CodeObject) -> {Int:BasicBlock}

1) Split code into basic blocks
2) Remove unreachable basic blocks. """
    
    blocks = basic_blockize(code)
    eliminate_unreachable_blocks(blocks)

    return blocks
============================================================