challenge JS AST | Python Fiddle

from collections import OrderedDict

import json

## The good stuff

# statics

# I'm allowing object creation:
#   var obj = { foo = "bar }
#
# and this function definition syntax: 
#
#   var f = function() {return "I can be global!"}
#
# P.S.: I never programmed in JS and I don't know JS! 
#       All i now is from snippets and random code I found in the web
#
allowed_globals = ['ObjectDefinition', 'AnonymousFunction']

def findEval(ast):
    sub_trees = ast.find(name="FunctionCall")
    
    for sub_tree in sub_trees:
        match = sub_tree.find(name="Name", terminal="eval")
        #for x in match:
        #    print x
        for x in filter(bool, match):    # it's probably just one
            print('line {0}: Dangerous operation "eval".'.format(x.line))
   
   
def quoteConsistencyFinder(ast):
    def test_single_quotes(string):
        return string[0] == "'" and string[-1] == "'"

sub_trees = ast.find(name="StringLiteral")
    single_quotes = test_single_quotes(sub_trees[0].terminal)
    
    for sub_tree in sub_trees[1:]:
        if single_quotes != test_single_quotes(sub_tree.terminal):
            print("You're mixing single with double quotes.")           # I have no idea what to print here
            return
            
            
def globalVariableFinder(ast):
    exp_trees = ast.shallow_find(name="ExpressionStatement")
    ass_trees = [tree.shallow_find(name="Assignment") for tree in exp_trees]
    ass_trees = [tree for trees in ass_trees for tree in trees]         # flattening list.

for tree in ass_trees:
        # I assume the first entry is the variable name
        forbidden = filter(lambda x : x not in allowed_globals, tree.children[1:]) 
        if len(forbidden) != 0:
            print("line {0}: Global variable declaration -> '{1}'".format(tree.line, tree.children[0].terminal))

# Infinite cycle... HOW??
# 
# 
# NOTE: - All of this *needs* an additional data structure to keep track of
#         scopes and values of variables (or possible replacements, i.e., with "i = 0; a = i;", 
#         the data structure should be capable of inferring that "a=0" when possible)
#       - I'll use "loop block" and "loop scope" interchangeably because I suck at writing and explaining
#         my thoughts. What I mean is "everything inside the loop. I can probably see only the shallow code 
#         inside the loop (depth 1) but the further I can see (inside ifs or inside functions) the best.
#       - When I talk about a *concrete value* I mean a (primitive) value that is easy to work with (strings, numbers, bools)
# 
# PREMISSE: Analyse the variable(s) used in the loop condition to see if the loop ends.
# 
# SPECIAL RULES:
#     - Concept of "reachable code": code that can be accessed and can run. 
#         "if (1 != 0) { do_stuff() }"  -> do_stuff is not reachable.
#         Unreachable should, in most cases, be ignored.
#     
#     - If an infinite cycle is detected, a reachable "break" or "return" statement should be 
#       searched in the scope of the loop. (or "GOTO"'s but, int that case, http://xkcd.com/292/)
#       
#     - In any case, detecting an infinite loop is, in most cases, detecting a *possible*
#       infinite loop. The variable may be changed outside of the loop block via side-effects,
#       another thread, etc.
#       
# * 1st Step:
#     - Get the loop condition.
#     (1) If it uses no variables ("true", or "1 == 2-1"), try to eval it. It may be a case 
#         of an infinite loop on purpose or a loop that never starts. In the first case, check for "break"
#       
#     (2) If it uses variables ("x == y + 1") do the following:
#           - Of these, check which variables are changed inside the loop.
#             - If none is changed, it may be a situation like (1). Try to replace them with the helper data-structure.
#                 - If you can't replace them all, we can't conclude anything.
#                 
#             - The ones that are not changed, replace them with the helper data structure.
#               We now need to check how these variables change with the iterations.
#               (If there is more than one variable like this, this is probably gonna get too complex to be done)
#               
#             - For the ones that are changed check, with the helper data structure, what it their initial values
#               (that is, the last *concrete* value assigned to it before the loop.
#               
# * 2nd Step:
#     - VARIABLES ARE BOOLS ( "x == true")
#         - check if there any assignments in the loop block that make the loop end.
#         
#                 while (x == y):
#                     x = false
#                     if (x != y):
#                         x = true
#                     else:
#                         y = true
#                         
#             - we can see (at a glance) that it is possible to have "x=false; y=true", then ending the loop.
#         - if we cannot find a combination that ends the loop, then it's an infinite loop.
#         
#         
#     - VARIABLES ARE NUMBERS
#         - TO START: 
#             - Check if the condition uses "==" instead of "<", ">", ">=", "<=". 
#               In this case a warning should be thrown (just in case).
#     
#         - The Naive Approach: "(i=0; i <= 100;i=i-1)"
#             - One variable
#             - The variable in the condition is only initialized & used in the for "header" 
#             - Uses numbers & the condition is numeric
#             SOLUTION:
#                 - s = value i is initialized with
#                 - t = target value for the condition
#                 - check if target condition is bigger or smaller than the value i starts with. If it's a complex equation 
#                 - calculate limit L of the increment -> overkill, but allows for complex increments
#                 (1) if s < t && t < L -> not an infinite cycle!   
#                 (2) if s > t && t > L -> not an infinite cycle!   
#                 - (in most cases L == -INFINITY || L == +INFINITY)
#                 
#         - The Naive Approach 2.0 
#             - One variable
#             - Variable in the condition is changed int the loop scope
#             - once again, only numbers
#             SOLUTION:
#                - If the var is changed only in the upmost context block (depth 1):
#                     - aggregate all the expressions into one, calculate limit and do the same as above
#                - If the var is changed inside other blocks (specially "if blocks")
#                     - calculate limit for each expression. If any of them doesn't obey the previous
#                       conditions (1) and (2) for the limit -> we may have an infinite loop
#                     - NOTE: Always check if the assignments are reachable!!
#                    
#         - The Serious Approach.
#             - More than one variable.
#             - In this case, I believe the limit based algorithm is sound, but we would delve into
#               R^n calculus, that is beyond my immediate knowledge.
#               
#     - VARIABLES ARE STRINGS
#         - In these cases, the tests are usualy "x.contains('abc')", "x.length() == 10" or "x.equals("xpto")".
#         - The strategy here is to make the same replacements as in the BOOL strategy:
#             - check which expressions change the variables.
#             - Check if any combination can make the loop end.
#         - NOTE: This is not only complicated to do, as it is dangerous. 
#                  - In one hand, you need to "run" the condition (and possibly the assignments too) in your programs 
#                    language, interpreting the ast, to check the outcomes. Or just use "eval". This is needed 
#                    because different languages have different syntax for common string operations 
#                    ("len(x)", "x.length()", "x.size", etc.)
#                  - On the other hand, running and processing external string may allow for attacks and running 
#                    malicious code (or not, I really don't know if it is really possible)
#                    
#     - VARIABLES ARE CUSTOM OR "WEIRD" OBJECTS, DATA-STRUCTURES, ETC
#         - Hum... no dice. Probably too complex. I believe you can only do it in runtime, checking the objects and the values.
#         - This is specially true in dynamic language, as many time you don't know what you're gonna get.
#         
#     - ITERATORS AND FOREACH
#         - This is a tricky one. It's extremely language dependant. The language may support lazy/infinite lists. 
#           Even if it doesn't, a smart programmer can easily make one.
#         - In my opinion, in this case, you do nothing. There's no way to really check if there is an infinite cycle.
#         - In most cases, Iterators and foreach's end. 
#         - If we're dealing with infinite lists, the dev is playing with fire, and maybe should get burnt (just a bit)
#                 
# TL;DR : If Turing couldn't do it, I can't too. Here I outline a series of strategies for detecting
#         *possible* infinite loops. I'm not going to implement a solution because:
#             1 - It's too much work just for a fun exercise.
#             2 - Even I implement a solution just for your example, I wouldn't feel good about myself. It would be 
#                 as bad as hardcoding a "print("Infinite loop found at line 7)"
#         In the end, isn't this your job? ;)
#
def infiniteCycleFinder(ast):
    print("INFINITE CYCLE -> Check my code!!")

## The main function

def main():
    ast = AstNode.get_ast_from_json(getJsonAST())
    #print(ast)
    findEval(ast)
    quoteConsistencyFinder(ast)
    globalVariableFinder(ast)
    infiniteCycleFinder(ast)

## Helper class

class AstNode(object):
    def __init__(self, name, line, terminal, children=None, parent=None):
        self.name = name
        self.line = line
        self.terminal = terminal
        self.children = children if children else []
        self.parent = parent
    
    def test_self(self, name=None, terminal=None): 
        if (not name) and (not terminal):
            raise TypeError("You provide a search term")    # improve text
        if (name == None or self.name == name) and \
           (terminal == None or self.terminal == terminal):
           return self
        
    
    def find(self, name=None, terminal=None):               # TODO: make it cooler. Generators!
        if (not name) and (not terminal):
            raise TypeError("You provide a search term")    # improve text
        
        results = []
        if self.test_self(name, terminal):
            results = [self]
           
        for child in self.children:
            results += child.find(name, terminal)
            
        return results
        
    def shallow_find(self, name=None, terminal=None):
        if (not name) and (not terminal):
            raise TypeError("You provide a search term")    # improve text
            
        results = []
        if self.test_self(name, terminal):
            results = [self]
            
        child_matches = [child.test_self(name, terminal) for child in self.children]
        return results + filter(bool, child_matches)
        
        
        
    # TODO find_parent(name, terminal)
    # TODO find(name, terminal, child_condition)
    # TODO get_scope()  
    # TODO find_declaration()   ->  find where var was declared (tricky for dynamic langs)

def __str__(self):
        strings = []
        strings.append("name : {0}".format(self.name))
        strings.append("line : {0}".format(self.line))
        strings.append("terminal : {0}".format(self.terminal))
        
        #if self.parent:
        #    strings.append("parent :{0}".format(self.parent.name))
        
        if self.children:
            childs = [str(child) for child in self.children]
            childs = [s.replace('\n', '\n\t') for s in childs]            
            strings.append("children: \n\t{0}".format('\n'.join(childs)))
        
        return '\n'.join(strings)
    
    
    @classmethod
    def _create_ast(cls, sub_tree, parent):
        ast = cls(sub_tree["name"], sub_tree["line"],
                      sub_tree["terminal"], parent=parent)
        ast.children = [cls._create_ast(child, ast) for child in sub_tree['children']]
        return ast
        
    @classmethod
    def get_ast_from_json(cls, json_string):
        tree = json.loads(json_string)
        return cls._create_ast(tree, None)

## Data

def getAST():
    return json.loads(getJsonAST())

def getJsonAST():
    return '''{
  "name": "AstRoot",
  "line": 1,
  "terminal": "",
  "children": [
    {
      "name": "ExpressionStatement",
      "line": 1,
      "terminal": "",
      "children": [
        {
          "name": "Assignment",
          "line": 1,
          "terminal": "ASSIGN",
          "children": [
            {
              "name": "Name",
              "line": 1,
              "terminal": "a",
              "children": []
            },
            {
              "name": "NumberLiteral",
              "line": 1,
              "terminal": "1",
              "children": []
            }
          ]
        }
      ]
    },
    {
      "name": "FunctionNode",
      "line": 3,
      "terminal": "foo",
      "children": [
        {
          "name": "Block",
          "line": 3,
          "terminal": "",
          "children": [
            {
              "name": "ExpressionStatement",
              "line": 5,
              "terminal": "",
              "children": [
                {
                  "name": "FunctionCall",
                  "line": 5,
                  "terminal": "",
                  "children": [
                    {
                      "name": "Name",
                      "line": 5,
                      "terminal": "eval",
                      "children": []
                    },
                    {
                      "name": "StringLiteral",
                      "line": 5,
                      "terminal": "console.log(\\\"hey hey\\\")",
                      "children": []
                    }
                  ]
                }
              ]
            },
            {
              "name": "ForLoop",
              "line": 7,
              "terminal": "",
              "children": [
                {
                  "name": "VariableDeclaration",
                  "line": 7,
                  "terminal": "",
                  "children": [
                    {
                      "name": "VariableInitializer",
                      "line": 7,
                      "terminal": "",
                      "children": [
                        {
                          "name": "Name",
                          "line": 7,
                          "terminal": "i",
                          "children": []
                        },
                        {
                          "name": "NumberLiteral",
                          "line": 7,
                          "terminal": "0",
                          "children": []
                        }
                      ]
                    }
                  ]
                },
                {
                  "name": "InfixExpression",
                  "line": 7,
                  "terminal": "LE",
                  "children": [
                    {
                      "name": "Name",
                      "line": 7,
                      "terminal": "i",
                      "children": []
                    },
                    {
                      "name": "NumberLiteral",
                      "line": 7,
                      "terminal": "100",
                      "children": []
                    }
                  ]
                },
                {
                  "name": "Assignment",
                  "line": 7,
                  "terminal": "ASSIGN",
                  "children": [
                    {
                      "name": "Name",
                      "line": 7,
                      "terminal": "i",
                      "children": []
                    },
                    {
                      "name": "InfixExpression",
                      "line": 7,
                      "terminal": "SUB",
                      "children": [
                        {
                          "name": "Name",
                          "line": 7,
                          "terminal": "i",
                          "children": []
                        },
                        {
                          "name": "NumberLiteral",
                          "line": 7,
                          "terminal": "1",
                          "children": []
                        }
                      ]
                    }
                  ]
                },
                {
                  "name": "Scope",
                  "line": 7,
                  "terminal": "",
                  "children": [
                    {
                      "name": "ExpressionStatement",
                      "line": 8,
                      "terminal": "",
                      "children": [
                        {
                          "name": "FunctionCall",
                          "line": 8,
                          "terminal": "",
                          "children": [
                            {
                              "name": "PropertyGet",
                              "line": 8,
                              "terminal": "GETPROP",
                              "children": [
                                {
                                  "name": "Name",
                                  "line": 8,
                                  "terminal": "console",
                                  "children": []
                                },
                                {
                                  "name": "Name",
                                  "line": 8,
                                  "terminal": "log",
                                  "children": []
                                }
                              ]
                            },
                            {
                              "name": "StringLiteral",
                              "line": 8,
                              "terminal": "hey hey",
                              "children": []
                            }
                          ]
                        }
                      ]
                    }
                  ]
                }
              ]
            },
            {
              "name": "ReturnStatement",
              "line": 11,
              "terminal": "",
              "children": [
                {
                  "name": "StringLiteral",
                  "line": 11,
                  "terminal": "'bar'",
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    },
    {
      "name": "ExpressionStatement",
      "line": 14,
      "terminal": "",
      "children": [
        {
          "name": "FunctionCall",
          "line": 14,
          "terminal": "",
          "children": [
            {
              "name": "Name",
              "line": 14,
              "terminal": "foo",
              "children": []
            }
          ]
        }
      ]
    }
  ]
}'''

#print (getAST())
#ast = AstNode.get_ast_from_json(getJsonAST())
#subs = ast.find(name='FunctionCall')

if __name__ == "__main__":
    main()

Python Fiddle

Python Cloud IDE