4
$\begingroup$

I'm finishing right now the lambda expression's resolution for an ActionScript 3 compiler, but, in terms of control flow analysis I've some difficulty to get into it.

I've searched for some existing control flow analysers just to understand what they do, but I've found more complicated ones that are intended for linter tooling (in the case of AS3, more nearby examples are JavaScript CFG analysers, but you know, they're too clever). In my case I don't need to detect infinite loops for example or deal with constants at all (even though I do handle constants in the semantic model, I don't want to have a lot of work going on in the control flow analysis).

I don't understand what parameters are involved when building a control flow graph from a series of statements or "directives".

For example, this is what I'm guessing that I'd have in Rust:

use crate::ns::*;

pub(crate) struct ControlFlowAnalyser;

impl ControlFlowAnalyser {
    pub fn analyse_directives(list: &[Rc<Directive>], cfg: &ControlFlowGraph, building_block: &mut Vec<Rc<Directive>>) {
        todo_here();
    }
}

This is what I've for the ControlFlowGraph structures:

#[derive(Clone)]
pub struct ControlFlowGraph(Rc<ControlFlowGraph1>);

impl ControlFlowGraph {
    pub fn new() -> Self {
        Self(Rc::new(ControlFlowGraph1 {
            blocks: SharedArray::new(),
            edges: SharedArray::new(),
        }))
    }

    pub fn blocks(&self) -> SharedArray<ControlFlowBlock> {
        self.0.blocks.clone()
    }

    pub fn edges(&self) -> SharedArray<ControlFlowEdge> {
        self.0.edges.clone()
    }
}

impl std::hash::Hash for ControlFlowGraph {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        Rc::as_ptr(&self.0).hash(state)
    }
}

impl PartialEq for ControlFlowGraph {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl Eq for ControlFlowGraph {}

struct ControlFlowGraph1 {
    blocks: SharedArray<ControlFlowBlock>,
    edges: SharedArray<ControlFlowEdge>,
}

#[derive(Clone)]
pub struct ControlFlowBlock(Rc<Vec<Rc<Directive>>>);

impl ControlFlowBlock {
    pub fn new(lines: Vec<Rc<Directive>>) -> Self {
        Self(Rc::new(lines))
    }

    pub fn lines(&self) -> Rc<Vec<Rc<Directive>>> {
        self.0.clone()
    }
}

impl std::hash::Hash for ControlFlowBlock {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        Rc::as_ptr(&self.0).hash(state)
    }
}

impl PartialEq for ControlFlowBlock {
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl Eq for ControlFlowBlock {}

#[derive(Clone)]
pub struct ControlFlowEdge {
    pub from: ControlFlowBlock,
    pub to: ControlFlowBlock,
}

As I understand it, jump instructions (whether conditional or not) end a block, and jump targets start a block. In ActionScript 3 there are no C gotos, it's really an ECMAScript 3 dialect.

My question is what do I need to do to analyse the control flow without any advanced linting tooling (i.e. infinite loop detection) going on, assuming I've already resolved the semantics of the statements?

In addition, I've two goals for now:

  • Ensure all code paths return a value
  • Deduce the result type of a method signature when omitted

My future goal will be to have AVM2 bytecode generation, but I'll probably focus more in an ASDoc to HTML output once I finish things.

I do support, syntactically speaking, asynchronous methods, but I don't plan to implement them in AVM2 for now.

Similiarly I also support yield for generators, but I already report an error at it for now.

In AS3, the only basic jump statements are break and continue which take an optional label as part of a parent loop or block.

To restrict more the scope, AS3 doesn't support expressions containing statements; only lambdas can have them.

$\endgroup$
2
  • 2
    $\begingroup$ The factors that will determine the design of your flow analyzer are answers to the question "why do you want to build an analyzer?" You've already rejected linting as a reason, but you haven't said what goal you intend to achieve. Knowing what goal you intend to achieve will help motivate a design. $\endgroup$ Commented May 11 at 21:07
  • $\begingroup$ @EricLippert Good point, I'd like to ensure all code paths return a value and also be able to deduce the result type in omission cases. Other than this, I'm leaving AVM2 codegen for later, but I forgot to talk about "asynchronous" cases. I probably won't implement them and report an error at await. $\endgroup$
    – Hydroper
    Commented May 11 at 21:37

1 Answer 1

2
$\begingroup$

I've two goals for now:

  • Ensure all code paths return a value
  • Deduce the result type of a method signature when omitted

The first is easier, so start by implementing that. You'll then have experience building one analyzer and can use that knowledge to extend your existing analyzer or build a second one for the second problem.

Let's start by crisping up that statement. You've said that you don't care about detecting infinite loops, and you've also said that you want to ensure that all code paths return a value, but that's a contradiction. Code paths containing infinite loops never return a value! You can't both fail to detect infinite loops and ensure that every possible path returns a value. (Hint: "every path returns a value" in the general case requires you to solve the Halting Problem, which you are not going to solve.)

My first piece of advice is to very clearly state what policy it is that you are attempting to enforce, and then take a page from test-driven-development and write some small test case programs that you expect an analyzer to flag or not flag as violating your policy.

Let me be a bit more clear about the specific policy here. For example, consider the subtle difference between these two policies:

  • If any return statement in the method returns a value then every return statement must return a value and the endpoint of the method body must not be reachable.
  • If any reachable return statement in the method returns a value then every reachable return statement must return a value and the endpoint of the method body must not be reachable.

How do those differ? Consider the body:

{ 
  if (false) return 123;
}

That would violate the first policy but not the second. Similarly

{
    return;
    return 123;
}

violates the first policy but not the second.

What you decide to check is up to you, but be very clear about what the policy is before you start writing the analyzer.

As I understand it, jump instructions (whether conditional or not) end a block, and jump targets start a block.

Correct. Suppose we are trying to implement the first policy, because that's easier.

Step one: Check the body to see if there are any return statements that return values. If there are none, then the policy requirements are trivially met. Let's assume there is at least one.

Step two: Do all the return statements return a value? If not then the policy is trivially violated.   Step three: Put an invisible "return;" at the end of the method body.

Step four, the hard one: Partition all code into "basic blocks" where the start of each block is possibly the target of a jump and the end of each block is a conditional jump, unconditional jump, or return (or throw or whatever). (Remember that expressions like x() && y() have a hidden jump in them and therefore there are at least two blocks here. Consider desugaring such expressions into statements.)

Put a magical node "caller" and an edge from "caller" to the block containing the first statement in the body.

Now you have a graph where the nodes are blocks and the edges are control flows and you can ask questions about that graph. (Note that this is a directed graph that might contain cycles, so implement your graph algorithms accordingly!)

Step five: There is a block in the graph which contains an inserted invisible "return;" statement. Is there a path through the graph from "caller" to the invisible "return" block? If yes, then the policy is violated.


Summing up:

  • Be very, very clear about what policy you're checking. Write tests first.
  • Check for "easy outs" before building a control flow graph.
  • Partition the desugared program into a graph of basic blocks.
  • Characterize the policy as a property of the graph, and then query the graph for that property.

Your second goal requires tracking type information around the program and that gets us into lattices and all sorts of fun topics, so again my advice is to try and solve the easier problem first and then come back here if you have questions about the harder problem.

$\endgroup$
5
  • $\begingroup$ Oh yeah, I totally forgot about conditional and logical expressions, good reminder, Eric! I'm wondering what you mean exactly by putting a magical caller node? You mean, contribute a first block containing a caller node and an edge for it? $\endgroup$
    – Hydroper
    Commented May 12 at 9:39
  • $\begingroup$ So, I think you meant caller as a reference point. I'll try to follow this first policy about the all "return values" implication in case any return statement contains a return value, thanks for the answer! $\endgroup$
    – Hydroper
    Commented May 12 at 10:07
  • 1
    $\begingroup$ @Hydroper: I mean that the first block in the method must always be "known to be reachable" because it is reached by the caller of the method. A control flow path must start at some node, and that's the node to start at. $\endgroup$ Commented May 12 at 18:53
  • 1
    $\begingroup$ @EricLippert: My intuition is use "the end of the code block is not reachable" as the spec, rather than using something like "Ensure all code paths return a value." This makes for a very nicely overlapped specification and analyzer: "The invisible return statement is not reachable" meshes nicely with "the end of the clode block is not reachable." $\endgroup$
    – Brian
    Commented May 13 at 13:33
  • $\begingroup$ @Brian: Indeed, that is how C# is specified. $\endgroup$ Commented May 13 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .