grm_flow_graph.rb in rley-0.5.04

- old
+ new

@@ -44,13 +44,14 @@
       # then elimination of unreachable symbols
       def diagnose
         mark_unreachable_symbols
       end
 
-      Branching = Struct.new(:vertex, :to_visit, :visited) do
-        def initialize(aVertex)
+      Branching = Struct.new(:vertex, :in_edge, :to_visit, :visited) do
+        def initialize(aVertex, aCallEdge)
           super(aVertex)
+          self.in_edge = aCallEdge
           self.to_visit = aVertex.edges.dup
           self.visited = []
         end
 
         def done?
@@ -62,52 +63,71 @@
           visited << next_one.successor unless next_one.nil?
 
           return next_one
         end
       end
+      
+      def print_vertex(aText, aVertex)
+        print aText + ' '
+        if aVertex.kind_of?(NonTerminalVertex)
+          puts "#{aVertex.class} #{aVertex.non_terminal.name}"
+        else
+          p(aVertex.label)
+        end       
+      end
 
       # Walk over all the vertices of the graph that are reachable from a given
       # start vertex. This is a depth-first graph traversal.
       # @param aStartVertex [StartVertex] the depth-first traversal begins
       #   from here
       # @param _visitAction [Proc] block called when a new graph vertex is found
       def traverse_df(aStartVertex, &_visitAction)
         visited = Set.new
         stack = []
         visitee = aStartVertex
+        curr_edge = nil
 
         begin
+          # print_vertex( 'Traversing', visitee)
+          
           first_time = !visited.include?(visitee)
           if first_time
             yield(visitee)
             visited << visitee
-          end
-
+          end         
+                      
           case visitee
             when Rley::GFG::StartVertex
               if first_time
-                stack.push(Branching.new(visitee))
+                stack.push(Branching.new(visitee, curr_edge))
                 curr_edge = stack.last.next_edge
               else
-                # Skip start and end vertices
+                # Skip both start and end vertices
                 # Retrieve the corresponding return edge
                 curr_edge = get_matching_return(curr_edge)
               end
 
             when Rley::GFG::EndVertex
-              stack.pop if stack.last.done?
-              break if stack.empty?
-              curr_edge = stack.last.next_edge
+              if stack.last.done?
+                popped = stack.pop
+                break if stack.empty?
+                # puts "Popped!"
+                return_key = popped.in_edge.key.sub(/^CALL/, 'RET')
+                curr_edge = visitee.edges.find { |e| e.key == return_key }
+              else
+                curr_edge = stack.last.next_edge          
+              end
 
             else
               # All other vertex types have only one successor
               curr_edge = visitee.edges[0]
           end
           visitee = curr_edge.successor unless curr_edge.nil?
         end until stack.empty?
         # Now process the end vertex matching the initial start vertex
-        yield(end_vertex_for[aStartVertex.non_terminal])
+        last_one = end_vertex_for[aStartVertex.non_terminal]
+        yield(last_one) unless visited.include?(last_one)
       end
 
       private
 
       def add_vertex(aVertex)
@@ -286,14 +306,16 @@
         # Mark all non-terminals as unreachable
         start_vertex_for.each_value do |a_vertex|
           a_vertex.non_terminal.unreachable = true
         end
 
-        # Now traverse graph from start vertex
-        # and make all visited non-terminals as reachable
+        # Now traverse graph from start vertex of graph
+        # and mark all visited non-terminals as reachable
         traverse_df(start_vertex) do |a_vertex|
-          next unless a_vertex.kind_of?(StartVertex)
-          a_vertex.non_terminal.unreachable = false
+          # print_vertex('  Visiting', a_vertex)
+          if a_vertex.kind_of?(StartVertex)
+            a_vertex.non_terminal.unreachable = false
+          end
         end
       end
     end # class
   end # module
 end # module