1

This is a subset of the problem I am trying to tackle. Assume that I have parsed some code and now I am trying to check if it is logically correct. One of those checks is that functions calls can't call themselves or be involved in another function calling each other or a function of a function calling each other, and so on.

I have tackled the problem and was able to easily solve the call to itself and one level down though it might not be the optimal code. Right now, performance is not an issue.

Here is the logic I have coded along with an example:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LoopTest {

    public static void main(String[] args) {
        List<Loop> test = new ArrayList<Loop>();
        test.add(new Loop("Function1",new String[]{"Function2", "Function1"}));
        test.add(new Loop("Function2",new String[]{"Function3", "Function1"}));
        test.add(new Loop("Function3",new String[]{"Function1"}));
        checkLooping(test);
    }

    public static void checkLooping(List<Loop> input) {
        for(Loop main : input) {
            for(int i = 0; i < main.getInputSize(); i++) {
                if(main.getName().equals(main.getInputValue(i))) {
                    System.err.println("Looping condition found at " + main.getName());
                }
                for(Loop inside : input) {
                    for(int j = 0; j < inside.getInputSize(); j++) {
                        if(main.getInputValue(i).contains(inside.getName()) && 
                                main.getName().equals(inside.getInputValue(j))) {
                            System.err.println("Looping condition found between " 
                                    + main.getName() + " and " + inside.getName());
                        }
                    }
                }
            }
        }
    }
}

class Loop {
    private String name;
    private String input[];

    public Loop(String name, String input[]) {
        this.name = name;
        this.input = input;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String[] getInput() {
        return input;
    }
    public void setInput(String[] input) {
        this.input = input;
    }

    public int getInputSize() {
        return input.length;
    }

    public String getInputValue(int i) {
        return input[i];
    }

    public boolean contains(String search) {
        if(name.contains(search))
            return true;
        else
            return false;
    }

    @Override
    public String toString() {
        return String.format("%s %s", this.name, Arrays.toString(input));
    }
}

This won't catch that Function1 exists in Function3. So if it is deeper than level 1, it won't catch it based on my logic. Is there another way to do so?

Thanks in advance!

Andy M
  • 119
  • 9

2 Answers2

4

Is there another way to do so?

Yes it is a graph traversal problem; specifically the problem of detecting circular references in (in this case) the graph of method calls.

A simple algorithm goes like this:

def detect_cycle(node, seen={}):
    if seen contains node:
        // found a cycle
    seen.add(node)
    foreach child in node.children:
        detect_cycle(child, seen)

(You don't need an explicit graph structure to do this traversal. The same approach can be used to traverse/check a graph that is implied by another data structure.)

However, what we are actually doing here is checking for recursive calls. We won't be able to distinguish between recursion that terminates (which is ok) and infinite recursion (which is bad). And THAT is a really difficult problem. (In fact, computation theory says that the most general form of the problem of proving termination has no solution.)

As a matter or interest ( :-) ) the graph traversal algorithm above is an example of a program with good recursion. However, it would be a huge amount of work to write a program that can prove that it will terminate ... and identify the theoretical case where it won't!

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Yup, the way to model that kind of thing is a directed graph, which can be checked for cycles in linear time. See for example http://stackoverflow.com/questions/4168/graph-serialization/4577#4577 – G. Bach Feb 02 '13 at 04:49
  • Thanks! The good thing I guess is the language I am parsing doesn't allow any recursive calls. My question is what would a good data structure that Java has or should I use an outside library like JGraph? – Andy M Feb 03 '13 at 00:02
  • You don't *need* an extra data structure. All the information you require is in the `List` data structure. It might be easier if it was a `Map` ... to make lookup easier. And you may want to change it for other reasons. You don't need a generic graph data structure. Your primary structure is a tree, at least when you are doing syntactic stuff. – Stephen C Feb 03 '13 at 00:33
  • I am probably having trouble understanding this: "foreach child in node.children" to be implemented. Maybe, if implemented through a Map it would make more sense. – Andy M Feb 03 '13 at 02:36
  • Thanks a lot for your help @StephenC! I have provided an answer of running code for future readers using your pseudocode! – Andy M Feb 03 '13 at 06:34
0

Thanks to @StephenC

Here is my running code after I converted to using Map:

private static Map<String, List<String>> main;


// more code from above


public void detectCycle(String node, Stack<String> seen) {
        if(seen.contains(node)) {
            System.out.println("found cycle at " + node + " and " + seen.get(seen.size()-1));
            return;
        }
        else 
            seen.push(node);

        if(main.get(node) != null && main.get(node).size() != 0) {
            for(int i = 0; i < main.get(node).size(); i++) {
                detectCycle(main.get(node).get(i), seen);
            }
        }

        if(!seen.isEmpty())
            seen.pop();
        return;
}
Andy M
  • 119
  • 9