Added liveness analysis for protocols, and removed warnings about empty states.

4 files changed, 115 insertions, 0 deletions

diff --git a/src/libsyntax/ext/pipes.rs b/src/libsyntax/ext/pipes.rs
index bea1c8cae0c..5a1462cea30 100644
--- a/src/libsyntax/ext/pipes.rs
+++ b/src/libsyntax/ext/pipes.rs
@@ -27,6 +27,9 @@ fn expand_proto(cx: ext_ctxt, _sp: span, id: ast::ident,
     // check for errors
     visit(proto, cx);
 
+    // do analysis
+    liveness::analyze(proto, cx);
+
     // compile
     base::mr_item(proto.compile(cx))
 }
diff --git a/src/libsyntax/ext/pipes/liveness.rs b/src/libsyntax/ext/pipes/liveness.rs
new file mode 100644
index 00000000000..4f803992520
--- /dev/null
+++ b/src/libsyntax/ext/pipes/liveness.rs
@@ -0,0 +1,91 @@
+/*
+
+Liveness analysis for protocols. This is useful for a lot of possible
+optimizations.
+
+This analysis computes the "co-live" relationship between
+states. Co-live is defined inductively as follows.
+
+1. u is co-live with v if u can transition to v in one message.
+
+2. u is co-live with v if there exists a w such that u and w are
+co-live, w and v are co-live, and u and w have the same direction.
+
+This relationship approximates when it is safe to store two states in
+the same memory location. If there is no u such u is co-live with
+itself, then the protocol is bounded.
+
+(These assertions could use proofs)
+
+In addition, this analysis does reachability, to warn when we have
+useless states.
+
+The algorithm is a fixpoint computation. For each state, we initialize
+a bitvector containing whether it is co-live with each other state. At
+first we use rule (1) above to set each vector. Then we iterate
+updating the states using rule (2) until there are no changes.
+
+*/
+
+import dvec::extensions;
+
+import std::bitv::{bitv, methods};
+
+import proto::methods;
+import ast_builder::empty_span;
+
+fn analyze(proto: protocol, _cx: ext_ctxt) {
+    #debug("initializing colive analysis");
+    let num_states = proto.num_states();
+    let colive = do (copy proto.states).map_to_vec |state| {
+        let bv = bitv(num_states, false);
+        for state.reachable |s| {
+            bv.set(s.id, true);
+        }
+        bv
+    };
+
+    let mut i = 0;
+    let mut changed = true;
+    while changed {
+        changed = false;
+        #debug("colive iteration %?", i);
+        for colive.eachi |i, this_colive| {
+            let this = proto.get_state_by_id(i);
+            for this_colive.ones |j| {
+                let next = proto.get_state_by_id(j);
+                if this.dir == next.dir {
+                    changed = changed || this_colive.union(colive[j]);
+                }
+            }
+        }
+        i += 1;
+    }
+
+    #debug("colive analysis complete");
+
+    // Determine if we're bounded
+    let mut self_live = ~[];
+    for colive.eachi |i, bv| {
+        if bv.get(i) {
+            vec::push(self_live, proto.get_state_by_id(i))
+        }
+    }
+
+    if self_live.len() > 0 {
+        let states = str::connect(self_live.map(|s| *s.name), ~" ");
+
+        #debug("protocol %s is unbounded due to loops involving: %s",
+               *proto.name, states);
+
+        // Someday this will be configurable with a warning
+        //cx.span_warn(empty_span(),
+        //              #fmt("protocol %s is unbounded due to loops \
+        //                    involving these states: %s",
+        //                   *proto.name,
+        //                   states));
+    }
+    else {
+        #debug("protocol %s is bounded. yay!", *proto.name);
+    }
+}
\ No newline at end of file
diff --git a/src/libsyntax/ext/pipes/proto.rs b/src/libsyntax/ext/pipes/proto.rs
index 1c88732adb0..e9070c79b55 100644
--- a/src/libsyntax/ext/pipes/proto.rs
+++ b/src/libsyntax/ext/pipes/proto.rs
@@ -55,6 +55,7 @@ impl methods for message {
 
 enum state {
     state_(@{
+        id: uint,
         name: ident,
         dir: direction,
         ty_params: ~[ast::ty_param],
@@ -81,6 +82,20 @@ impl methods for state {
         cx.ty_path_ast_builder
             (path(self.name).add_tys(cx.ty_vars(self.ty_params)))
     }
+
+    /// Iterate over the states that can be reached in one message
+    /// from this state.
+    fn reachable(f: fn(state) -> bool) {
+        for self.messages.each |m| {
+            alt m {
+              message(_, _, _, some({state: id, _})) {
+                let state = self.proto.get_state(id);
+                if !f(state) { break }
+              }
+              _ { }
+            }
+        }
+    }
 }
 
 enum protocol {
@@ -104,6 +119,8 @@ impl methods for protocol {
         self.states.find(|i| i.name == name).get()
     }
 
+    fn get_state_by_id(id: uint) -> state { self.states[id] }
+
     fn has_state(name: ident) -> bool {
         self.states.find(|i| i.name == name) != none
     }
@@ -113,6 +130,7 @@ impl methods for protocol {
         let messages = dvec();
 
         let state = state_(@{
+            id: self.states.len(),
             name: name,
             dir: dir,
             ty_params: ty_params,
@@ -127,6 +145,8 @@ impl methods for protocol {
     fn filename() -> ~str {
         ~"proto://" + *self.name
     }
+
+    fn num_states() -> uint { self.states.len() }
 }
 
 trait visitor<Tproto, Tstate, Tmessage> {
diff --git a/src/libsyntax/syntax.rc b/src/libsyntax/syntax.rc
index 9750f2d5bd1..10ff0d336c2 100644
--- a/src/libsyntax/syntax.rc
+++ b/src/libsyntax/syntax.rc
@@ -87,5 +87,6 @@ mod ext {
         mod pipec;
         mod proto;
         mod check;
+        mod liveness;
     }
 }