Thread: [Scstudio-commits] SF.net SVN: scstudio:[103] trunk

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Revision: 103
          http://scstudio.svn.sourceforge.net/scstudio/?rev=103&view=rev
Author:   babicaj
Date:     2008-07-27 09:20:07 +0000 (Sun, 27 Jul 2008)

Log Message:
-----------
HMsc now supports connections nodes, few bugs were found and corrected. DotWriter as same as livelock_checker needs to be rewritten to follow changes in structure of HMsc.

Modified Paths:
--------------
    trunk/CMakeLists.txt
    trunk/src/check/CMakeLists.txt
    trunk/src/check/bmsc_race_checker.cpp
    trunk/src/check/deadlock_checker.cpp
    trunk/src/check/deadlock_checker.h
    trunk/src/check/dfs_events_traverser.cpp
    trunk/src/check/dfs_events_traverser.h
    trunk/src/check/dfs_hmsc_traverser.cpp
    trunk/src/check/dfs_hmsc_traverser.h
    trunk/src/check/dfs_instance_events_traverser.cpp
    trunk/src/check/dfs_instance_events_traverser.h
    trunk/src/data/Z120/CMakeLists.txt
    trunk/src/data/msc.cpp
    trunk/src/data/msc.h
    trunk/tests/CMakeLists.txt

Added Paths:
-----------
    trunk/src/check/dfs_bmsc_graph_traverser.cpp
    trunk/src/check/dfs_bmsc_graph_traverser.h

Removed Paths:
-------------
    trunk/src/check/dfs_msc_graph_traverser.cpp
    trunk/src/check/dfs_msc_graph_traverser.h
    trunk/src/check/instance_vis_cls_init.cpp
    trunk/src/check/instance_vis_cls_init.h

Modified: trunk/CMakeLists.txt
===================================================================

--- trunk/CMakeLists.txt	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/CMakeLists.txt	2008-07-27 09:20:07 UTC (rev 103)
@@ -3,7 +3,7 @@
 # cmake . -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=/usr/local
 
 PROJECT(scstudio C CXX)
-# SET(CMAKE_VERBOSE_MAKEFILE ON)
+#SET(CMAKE_VERBOSE_MAKEFILE ON)
 
 INCLUDE_DIRECTORIES(src)
 ADD_SUBDIRECTORY(src .)

Modified: trunk/src/check/CMakeLists.txt
===================================================================
--- trunk/src/check/CMakeLists.txt	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/src/check/CMakeLists.txt	2008-07-27 09:20:07 UTC (rev 103)
@@ -1,13 +1,17 @@
-ADD_LIBRARY(acyclic_checker STATIC acyclic_checker.cpp)
-ADD_LIBRARY(bmsc_race_checker STATIC bmsc_race_checker.cpp)
-ADD_LIBRARY(causal_closure_initiator STATIC causal_closure_initiator.cpp)
-ADD_LIBRARY(deadlock_checker STATIC deadlock_checker.cpp)
+#traversers
 ADD_LIBRARY(dfs_area_traverser STATIC dfs_area_traverser.cpp)
 ADD_LIBRARY(dfs_events_traverser STATIC dfs_events_traverser.cpp)
 ADD_LIBRARY(dfs_hmsc_traverser STATIC dfs_hmsc_traverser.cpp)
 ADD_LIBRARY(dfs_instance_events_traverser STATIC dfs_instance_events_traverser.cpp)
-ADD_LIBRARY(dfs_msc_graph_traverser STATIC dfs_msc_graph_traverser.cpp)
+ADD_LIBRARY(dfs_bmsc_graph_traverser STATIC dfs_bmsc_graph_traverser.cpp)
+
+#order relation
+ADD_LIBRARY(causal_closure_initiator STATIC causal_closure_initiator.cpp)
+ADD_LIBRARY(visual_closure_initiator STATIC visual_closure_initiator.cpp)
+
+#checkers
+ADD_LIBRARY(acyclic_checker STATIC acyclic_checker.cpp)
+ADD_LIBRARY(deadlock_checker STATIC deadlock_checker.cpp)
 ADD_LIBRARY(fifo_checker STATIC fifo_checker.cpp)
-#ADD_LIBRARY(instance_vis_cls_init STATIC instance_vis_cls_init.cpp)
-ADD_LIBRARY(livelock_checker STATIC livelock_checker.cpp)
-ADD_LIBRARY(visual_closure_initiator STATIC visual_closure_initiator.cpp)
+#ADD_LIBRARY(livelock_checker STATIC livelock_checker.cpp)
+#ADD_LIBRARY(race_checker STATIC race_checker.cpp)

Modified: trunk/src/check/bmsc_race_checker.cpp
===================================================================
--- trunk/src/check/bmsc_race_checker.cpp	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/src/check/bmsc_race_checker.cpp	2008-07-27 09:20:07 UTC (rev 103)
@@ -18,7 +18,64 @@
 
 #include "check/bmsc_race_checker.h"
 
-const std::string BMscRaceChecker::m_instance_events_attribute = "brc_instance_events";
+void MinimalEventsInitiator::on_white_node_found(ReferenceNode* node)
+{
+  BMscPtr b = node->get_bmsc();
+  const InstancePtrList& instances = b->get_instances();
+  //compute minimal Events of Instances
+  EventPList minimal_events;
+  InstancePtrList::const_iterator i;
+  for(i=instances.begin();i!=instances.end();i++)
+  {
+    EventPList* events = DFSInstanceEventsTraverser::topology_order(*i);
+    EventPList::const_iterator e1 = events->begin();
+    while(e1!=events->end())
+    {
+      EventPList::const_iterator e2 = events->begin();
+      while(e2!=events->end())
+      {
+        if(e1!=e2)
+        {
+          Event* e = *e2;
+          BoolVector& e2_causal = m_caus_initiator->get_causal_closure(*e2);
+          size_t e1_index = m_vis_initiator->get_topology_index(*e1);
+          //e2<<e1 => e1 isn't minimal
+          if(e2_causal[e1_index]) break;
+        }
+        e2++;
+      }
+      //'while loop' hasn't found any Event e2 to be less than e1
+      if(e2==events.end())
+        minimal_events.push_back(*e1);
+      e1++;
+    }
+    delete events;
+  }
+  /*
+  For the minimal_events find Instances containing less Events.
+  Note that if there exists any less Event e1 at Instance i, e1 must be grater
+  or equal to some Event e2 in minimal_events, therefore we will use only
+  minimal_events to seek.
+  */
+  EventPList::const_iterator e;
+  ExtremeEvents& extreme_events = get_minimal_events(b.get());
+  for(e=minimal_events.begin();e!=minimal_events.end();e++)
+  {
+    EventDependentInstances e_instances(*e,m_instance_marker.get_count());
+    size_t e_index = m_vis_initiator->get_topology_index(*e);
+    EventPList::const_iterator f;
+    for(f=minimal_events.begin();f!=minimal_events.end();f++)
+    {
+      //if f is less than e then Instance of f must be inserted
+      BoolVector& closure = m_caus_initiator->get_causal_closure(*f);
+      if(closure[e_index])
+        e_instances.set_dependent(
+          m_instance_marker->get_id((*f)->get_instance()));
+    }
+    extreme_events.add_extreme_event(e_instances);
+  }
+  m_modified_bmscs.push_back(b.get());
+}
 
 BMsc* BMscRaceChecker::create_counter_example(Event* e1, Event* e2)
 {
@@ -70,35 +127,36 @@
 BMscPtr BMscRaceChecker::check(BMscPtr bmsc, ChannelMapperPtr mapper)
 {
   DFSEventsTraverser traverser;
+  TopologicalOrderListener topology_listener;
   traverser.add_event_finished_listener(this);
   traverser.traverse(bmsc);
   EventPVector topology(
-    get_topology().begin(),
-    get_topology().end()
+    topology_listener.get_topology().begin(),
+    topology_listener.get_topology().end()
   );
   m_visual_initiator.initialize(topology);
   m_causal_initiator.initialize(topology,m_visual_initiator,mapper);
-  BMscPtr result;
+  OrderCheckerListener order_checker_listener(&m_visual_initiator);
+  DFSInstanceEventsTraverser instance_traverser;
   for(size_t i = 0; i < topology.size(); i++)
   {
-    size_t i_index = m_visual_initiator.get_topology_index(topology[i]);
-    BoolVector& i_visual = m_visual_initiator.get_visual_closure(topology[i]);
-    BoolVector& i_causal = m_causal_initiator.get_causal_closure(topology[i]);
-    EventPList& instance_events = get_instance_events(topology[i]->get_instance());
-    EventPList::iterator j;
-    for(j=instance_events.begin(); j!=instance_events.end(); j++)
+    //in this block checkout whether there is any Event in race with topology[i]
+    order_checker_listener.reset(
+      topology[i],
+      &m_visual_initiator.get_visual_closure(topology[i]),
+      &m_causal_initiator.get_causal_closure(topology[i]));
+    try
     {
-      size_t j_index = m_visual_initiator.get_topology_index(*j);
-      if(i_visual[j_index] && !i_causal[j_index])
-      {
-        result = create_counter_example(topology[i_index],topology[j_index]);
-        cleanup_attributes();
-        return result;
-      }
+      instance_traverser.traverse(topology[i]->get_instance());
+      instance_traverser.cleanup_traversing_attributes();
     }
+    catch(EventRaceException& e)
+    {
+      instance_traverser.cleanup_traversing_attributes();
+      return create_counter_example(topology[i],e->get_event());
+    }
   }
-  cleanup_attributes();
-  return result;
+  return BMscPtr();
 }
 
 void BMscRaceChecker::cleanup_attributes()

Modified: trunk/src/check/deadlock_checker.cpp
===================================================================
--- trunk/src/check/deadlock_checker.cpp	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/src/check/deadlock_checker.cpp	2008-07-27 09:20:07 UTC (rev 103)
@@ -18,86 +18,59 @@
 
 #include "check/deadlock_checker.h"
 
-const std::string DeadlockChecker::visited_attribute = "deadlock_visited";
-const std::string DeadlockChecker::checked_attribute = "deadlock_checked";
 DeadlockCheckerPtr DeadlockChecker::m_instance;
 
-
-ReferenceNode* DeadlockChecker::check_deadlock_free_visit(ReferenceNode* node){
-  ReferenceNode* p = new ReferenceNode(node);
-  set_visited(node);
-  //search current node if it contains HMsc
-  HMscPtr h = node->get_hmsc();
-  if(h.get() && !get_checked(h)){
-    HMscPtr inner = check_deadlock_free(h);
-    if(inner.get()){
-      p->set_msc(inner);
-      return p;
-    } 
-  }
-  ReferenceNodePSet::const_iterator succ;
-  const ReferenceNodePSet& successors = node->get_successors();
-  if(successors.size()==0 && !node->is_end_node())
+HMscPtr DeadlockChecker::create_counter_example(const InnerNodePListList& path)
+{
+  InnerNodePListList::const_iterator hmscs_it;
+  HMscPtr result;
+  for(hmscs_it=path.begin();hmscs_it!=path.end();hmscs_it++)
   {
-    return p;
-  }
-  for(succ = successors.begin();succ != successors.end();++succ)
-  {
-    if(!get_visited(*succ))
+    HMscPtr current_hmsc;
+    InnerNode* last_node = NULL;
+    InnerNodePList::const_iterator nodes_it;
+    for(nodes_it=hmscs_it->begin();nodes_it!=hmscs_it->end();nodes_it++)
     {
-      ReferenceNode* succ_node = check_deadlock_free_visit(*succ);
-      if(succ_node!=NULL)
+      if(last_node==NULL)
       {
-        p->add_successor(succ_node);
-        return p;
+        if(dynamic_cast<ReferenceNode*>(*nodes_it)!=NULL)
+          last_node = new ReferenceNode((ReferenceNode*)*nodes_it);
+        else
+          last_node = new ConnectionNode((ConnectionNode*)*nodes_it);
+        current_hmsc = new HMsc((*nodes_it)->get_owner());
+        current_hmsc->get_start()->add_successor(last_node);
+        if(!result.get())
+          result = current_hmsc;
       }
+      else
+      {
+        last_node->add_successor(*nodes_it);
+        last_node = *nodes_it;
+      }
     }
   }
-  delete p;
-  return NULL;
+  return result;
 }
 
-HMscPtr DeadlockChecker::check_deadlock_free(HMscPtr hmsc)
-{
-  set_checked(hmsc);
-  ReferenceNodePSet::const_iterator node;
-  const ReferenceNodePSet& successors = hmsc->get_start()->get_successors();
-  for(node = successors.begin();node!=successors.end();++node){
-    if(!get_visited(*node)){
-      ReferenceNode* n = check_deadlock_free_visit(*node);
-      if(n!=NULL)
-      {
-        HMscPtr h(new HMsc);
-        h->set_original(hmsc.get());
-        h->get_start()->add_successor(n);
-        return h;
-      }
-    }            
-  }
-  HMscPtr p;
-  return p;
-}   
-
 HMscPtr DeadlockChecker::check(HMscPtr hmsc, ChannelMapperPtr chm)
 {
   //this will be used do show eventual counterexample
-  HMscPtr p = check_deadlock_free(hmsc);
-  cleanup_attributes();
+  HMscPtr p;
+  DeadlockListener listener;
+  DFSHMscTraverser traverser;
+  traverser.add_white_node_found_listener(&listener);
+  try
+  {
+    traverser.traverse(hmsc);
+  }
+  catch(DeadlockException& e)
+  {
+    p = create_counter_example(traverser.get_reached_nodes());
+    traverser.cleanup_traversing_attributes();
+  }
   return p;
 }
 
 void DeadlockChecker::cleanup_attributes()
 {
-  while(!checked_elements.empty())
-  {
-    HMscPtr p = checked_elements.top();
-    p->remove_attribute<bool>(checked_attribute);
-    checked_elements.pop();
-  }
-  while(!visited_elements.empty())
-  {
-    ReferenceNode* p = visited_elements.top();
-    p->remove_attribute<bool>(visited_attribute);
-    visited_elements.pop();
-  }
 }

Modified: trunk/src/check/deadlock_checker.h
===================================================================
--- trunk/src/check/deadlock_checker.h	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/src/check/deadlock_checker.h	2008-07-27 09:20:07 UTC (rev 103)
@@ -16,93 +16,56 @@
  * $Id$
  */
 
+#include <string>
+#include <stack>
+#include <exception>
+
 #include "check/checker.h"
 #include "data/msc.h"
 #include "data/counted_ptr.h"
-#include <string>
-#include <stack>
+#include "check/dfs_hmsc_traverser.h"
 
 class DeadlockChecker;
 
 typedef counted_ptr<DeadlockChecker> DeadlockCheckerPtr;
 
-class DeadlockChecker: public HMscChecker
+class DeadlockException:public std::exception
 {
   
-protected:
+public:
   
-  /**
-   * Common instance.
-   */
-  static DeadlockCheckerPtr m_instance;
-  
-  DeadlockChecker(){};
-  
-  /**
-   * Visited attribute name.
-   */
-  static const std::string visited_attribute;
-
-  /**
-   * Checked attribute name.
-   */
-  static const std::string checked_attribute;    
-
-  /**
-   * Setter for visited attribute.
-   */
-  void set_visited(ReferenceNode* node)
+  const char* what()
   {
-    node->set_attribute<bool>(visited_attribute, true);
-    visited_elements.push(node);
+    return "There was found deadlock in HMsc";
   }
+};
 
-  /**
-   * Setter for checked attribute.
-   */
-  void set_checked(HMscPtr h)
-  {
-    h->set_attribute<bool>(checked_attribute,true);
-    checked_elements.push(h);
-  }
+class DeadlockListener:public WhiteRefNodeFoundListener
+{
+public:
   
-  /**
-   * Getter for visited attribute.
-   *
-   * This method isn't public due to missing control of cleaning this attribute.
-   */
-  bool get_visited(ReferenceNode* node)
+  void on_white_node_found(ReferenceNode* node)
   {
-    return node->get_attribute<bool>(visited_attribute, false);
+    if(!node->is_end_node() && !node->has_successors())
+    {
+      throw DeadlockException();
+    }
   }
+};
 
-  /**
-   * Getter for checked attribute.
-   *
-   * This method isn't public due to missing control of cleaning this attribute.
-   */
-  bool get_checked(HMscPtr h)
-  {
-    return h->get_attribute<bool>(checked_attribute,false);
-  }
+class DeadlockChecker: public HMscChecker
+{
   
+protected:
+  
   /**
-   * Container for elements with set visited attribute.
-   *
-   * Used for cleaning up these attributes. 
+   * Common instance.
    */
-  std::stack<ReferenceNode*> visited_elements;
-
-  /**
-   * Container for elements with set checked attribute.
-   *
-   * Used for cleaning up these attributes.
-   */
-  std::stack<HMscPtr> checked_elements;
+  static DeadlockCheckerPtr m_instance;
   
-  ReferenceNode* check_deadlock_free_visit(ReferenceNode* node);
+  DeadlockChecker(){};
 
-  HMscPtr check_deadlock_free(HMscPtr hmsc);
+  HMscPtr create_counter_example(const InnerNodePListList& path);
         
 public:
     

Copied: trunk/src/check/dfs_bmsc_graph_traverser.cpp (from rev 98, trunk/src/check/dfs_msc_graph_traverser.cpp)
===================================================================
--- trunk/src/check/dfs_bmsc_graph_traverser.cpp	                        (rev 0)
+++ trunk/src/check/dfs_bmsc_graph_traverser.cpp	2008-07-27 09:20:07 UTC (rev 103)
@@ -0,0 +1,138 @@
+/*
+ * scstudio - Sequence Chart Studio
+ * http://scstudio.sourceforge.net
+ *
+ *      This library is free software; you can redistribute it and/or
+ *      modify it under the terms of the GNU Lesser General Public
+ *      License version 2.1, as published by the Free Software Foundation.
+ *
+ *      This library is distributed in the hope that it will be useful,
+ *      but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *      Lesser General Public License for more details.
+ *
+ * Copyright (c) 2008 Jindra Babica <ba...@ma...>
+ *
+ * $Id$
+ */
+
+#include <stack>
+
+#include "check/dfs_bmsc_graph_traverser.h"
+
+DFSBMscGraphTraverser::~DFSBMscGraphTraverser()
+{
+  cleanup_traversing_attributes();
+}
+
+void DFSBMscGraphTraverser::traverse(HMscPtr hmsc)
+{
+  m_colored_nodes.push_back(InnerNodePList());
+  traverse_successors(hmsc->get_start()->get_successors());
+  cleanup_traversing_attributes();
+}
+
+bool DFSBMscGraphTraverser::traverse_node(InnerNode* node)
+{
+  Color c = get_color(node);
+  if(c==BLACK) 
+  {
+    black_node_found(node);
+    return false;
+  }
+  if(c==GRAY)
+  {
+    gray_node_found(node);
+    return false;
+  }
+  white_node_found(node);
+  ReferenceNode* ref_node = dynamic_cast<ReferenceNode*>(node);
+  if(ref_node!=NULL)
+  {
+    HMscPtr hmsc = ref_node->get_hmsc();
+    if(hmsc.get()!=NULL)
+    {
+      m_reached_nodes.push_back(InnerNodePList());
+      //this line ensures (yet another one) that HMsc will be traversed as many times
+      //as it is referenced
+      m_colored_nodes.push_back(InnerNodePList());
+      //node's successors aren't traversed if end node wasn't found in hmsc
+      return traverse_successors(hmsc->get_start()->get_successors()) && 
+        (traverse_successors(node->get_successors()) || ref_node->is_end_node());
+      //this line ensures (yet another one) that HMsc will traversed as many times
+      //as it is referenced
+      cleanup_top_attributes();
+      m_reached_nodes.pop_back();
+    }
+  }
+  bool ending_successors = traverse_successors(node->get_successors());
+  node_finished(node);
+  return ending_successors || (ref_node!=NULL && ref_node->is_end_node());
+}
+
+bool DFSBMscGraphTraverser::traverse_successors(const InnerNodePSet& successors)
+{
+  bool end_found = false;
+  InnerNodePSet::const_iterator successor;
+  for(successor=successors.begin();successor!=successors.end();successor++)
+  {
+    end_found = traverse_node(*successor) || end_found;
+  }
+  return end_found;
+}
+
+void DFSBMscGraphTraverser::cleanup_top_attributes()
+{
+  InnerNodePList& top = m_colored_nodes.back();
+  InnerNodePList::iterator event;
+  for(event=top.begin();event!=top.end();event++)
+    (*event)->remove_attribute<Color>(m_color_attribute);
+  m_colored_nodes.pop_back();
+}
+
+void DFSBMscGraphTraverser::cleanup_traversing_attributes()
+{
+  while(!m_colored_nodes.empty())
+  {
+    cleanup_top_attributes();
+  }
+  while(!m_reached_nodes.empty())
+  {
+    m_reached_nodes.pop_back();
+  }
+
+}
+
+void DFSBMscGraphTraverser::white_node_found(InnerNode* n)
+{
+  m_reached_nodes.back().push_back(n);
+  WhiteNodeFoundListenerPList::iterator l;
+  for(l=m_white_node_found_listeners.begin();l!=m_white_node_found_listeners.end();l++)
+    (*l)->on_white_node_found(n);
+  set_color(n,GRAY);
+  m_colored_nodes.back().push_back(n);
+}
+
+void DFSBMscGraphTraverser::gray_node_found(InnerNode* n)
+{
+  GrayNodeFoundListenerPList::iterator l;
+  for(l=m_gray_node_found_listeners.begin();l!=m_gray_node_found_listeners.end();l++)
+    (*l)->on_gray_node_found(n);
+}
+
+void DFSBMscGraphTraverser::black_node_found(InnerNode* n)
+{
+  BlackNodeFoundListenerPList::iterator l;
+  for(l=m_black_node_found_listeners.begin();l!=m_black_node_found_listeners.end();l++)
+    (*l)->on_black_node_found(n);
+}
+
+void DFSBMscGraphTraverser::node_finished(InnerNode* n)
+{
+  NodeFinishedListenerPList::iterator l;
+  for(l=m_node_finished_listeners.begin();l!=m_node_finished_listeners.end();l++)
+    (*l)->on_node_finished(n);
+  m_reached_nodes.back().pop_back();
+  set_color(n,BLACK);
+}
+

Copied: trunk/src/check/dfs_bmsc_graph_traverser.h (from rev 98, trunk/src/check/dfs_msc_graph_traverser.h)
===================================================================
--- trunk/src/check/dfs_bmsc_graph_traverser.h	                        (rev 0)
+++ trunk/src/check/dfs_bmsc_graph_traverser.h	2008-07-27 09:20:07 UTC (rev 103)
@@ -0,0 +1,425 @@
+/*
+ * scstudio - Sequence Chart Studio
+ * http://scstudio.sourceforge.net
+ *
+ *      This library is free software; you can redistribute it and/or
+ *      modify it under the terms of the GNU Lesser General Public
+ *      License version 2.1, as published by the Free Software Foundation.
+ *
+ *      This library is distributed in the hope that it will be useful,
+ *      but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *      Lesser General Public License for more details.
+ *
+ * Copyright (c) 2008 Jindra Babica <ba...@ma...>
+ *
+ * $Id$
+ */
+
+#ifndef _DFS_MSC_GRAPH_TRAVERSER_H
+#define	_DFS_MSC_GRAPH_TRAVERSER_H
+
+#include<stack>
+
+#include "data/msc.h"
+#include "check/checker.h"
+
+typedef std::list<InnerNode*> InnerNodePList;
+typedef std::list<InnerNodePList> InnerNodePListList;
+
+/**
+ * Listener of founded white InnerNode
+ */
+class WhiteNodeFoundListener
+{
+public:
+  
+  virtual ~WhiteNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_white_node_found(InnerNode* n)=0;
+};
+
+/**
+ * Listener of founded gray InnerNode
+ */
+class GrayNodeFoundListener
+{
+public:
+  
+  virtual ~GrayNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_gray_node_found(InnerNode* n)=0;
+};
+
+/**
+ * Listener of founded black InnerNode
+ */
+class BlackNodeFoundListener
+{
+public:
+  
+  virtual ~BlackNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_black_node_found(InnerNode* n)=0;
+};
+
+/**
+ * Listener of finished InnerNode
+ */
+class NodeFinishedListener
+{
+public:
+  
+  virtual ~NodeFinishedListener()
+  {
+    
+  }
+  
+  virtual void on_node_finished(InnerNode* node)=0;
+};
+
+/**
+ * Auxiliary listener of founded white InnerNode.
+ *
+ * Extend this listener to process only ReferenceNodes during traversing.
+ */
+class WhiteRefNodeFoundListener:public WhiteNodeFoundListener
+{
+public:
+  
+  virtual ~WhiteRefNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_white_node_found(InnerNode* n){
+    ReferenceNode* ref = dynamic_cast<ReferenceNode*>(n);
+    if(ref!=NULL)
+    {
+      on_white_node_found(ref);
+    }
+  }
+  
+  virtual void on_white_node_found(ReferenceNode* n)=0;
+};
+
+/**
+ * Auxiliary listener of founded gray InnerNode.
+ *
+ * Extend this listener to process only ReferenceNodes during traversing.
+ */
+class GrayRefNodeFoundListener:public GrayNodeFoundListener
+{
+public:
+  
+  virtual ~GrayRefNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_gray_node_found(InnerNode* n){
+    ReferenceNode* ref = dynamic_cast<ReferenceNode*>(n);
+    if(ref!=NULL)
+    {
+      on_gray_node_found(ref);
+    }
+  }
+  
+  virtual void on_gray_node_found(ReferenceNode* n)=0;
+};
+
+/**
+ * Auxiliary listener of founded black InnerNode.
+ *
+ * Extend this listener to process only ReferenceNodes during traversing.
+ */
+class BlackRefNodeFoundListener:public BlackNodeFoundListener
+{
+public:
+  
+  virtual ~BlackRefNodeFoundListener()
+  {
+    
+  }
+  
+  virtual void on_black_node_found(InnerNode* n){
+    ReferenceNode* ref = dynamic_cast<ReferenceNode*>(n);
+    if(ref!=NULL)
+    {
+      on_black_node_found(ref);
+    }
+  }
+  
+  virtual void on_black_node_found(ReferenceNode* n)=0;
+};
+
+/**
+ * Auxiliary listener of finished InnerNode.
+ *
+ * Extend this listener to process only ReferenceNodes during traversing.
+ */
+class RefNodeFinishedListener:public NodeFinishedListener
+{
+public:
+  
+  virtual ~RefNodeFinishedListener()
+  {
+    
+  }
+  
+  virtual void on_node_finished(InnerNode* n){
+    ReferenceNode* ref = dynamic_cast<ReferenceNode*>(n);
+    if(ref!=NULL)
+    {
+      on_node_finished(ref);
+    }
+  }
+  
+  virtual void on_node_finished(ReferenceNode* n)=0;
+};
+
+typedef NodeFinishedListener* NodeFinishedListenerP;
+typedef std::list<NodeFinishedListenerP> NodeFinishedListenerPList;
+typedef WhiteNodeFoundListener* WhiteNodeFoundListenerP;
+typedef std::list<WhiteNodeFoundListenerP> WhiteNodeFoundListenerPList;
+typedef GrayNodeFoundListener* GrayNodeFoundListenerP;
+typedef std::list<GrayNodeFoundListenerP> GrayNodeFoundListenerPList;
+typedef BlackNodeFoundListener* BlackNodeFoundListenerP;
+typedef std::list<BlackNodeFoundListenerP> BlackNodeFoundListenerPList;
+
+/**
+ * Traverses all accessible InnerNodes in HMsc and referenced HMsc in depth 
+ * first search manner.
+ *
+ * HMsc is traversed like BMsc-graph (flattened version of HMsc - each 
+ * ReferenceNode references only BMsc not HMsc), i.e. each HMsc is traversed as 
+ * many times as it is referenced. If ReferenceNode references HMsc, this HMsc 
+ * is traversed before successors of referencing node are processed.
+ *
+ * InnerNodes of HMsc are during traversing in different states - with different 
+ * color. WHITE color means that node wasn't traversed before. GRAY nodes
+ * are those which have been already traversed and they are just on the stack - 
+ * not all successors of these events were processed. BLACK nodes are those 
+ * which have been already traversed but aren't yet on the stack - all 
+ * successors have been processed.
+ *
+ * Note that not all InnerNodes must be traversed by this DFSBMscGraphTraverser, 
+ * imagine InnerNode B which is accessible only from ReferenceNode A but A's
+ * HMsc hasn't got any end node.
+ *
+ * @warning Non-recursive HMsc is expected.
+ */
+class DFSBMscGraphTraverser
+{
+  
+public:
+  
+  /**
+   * To change default name of attribute which holds color of InnerNodes use
+   * color_attribute parameter.
+   */
+  DFSBMscGraphTraverser(const std::string& color_attribute = "msc_graph_traverse_color")
+  {
+    m_color_attribute = color_attribute;
+  }
+  
+  /**
+   * Calls cleanup_traversing_attributes
+   */
+  virtual ~DFSBMscGraphTraverser();
+
+  /**
+   * Trigger of traversing
+   */
+  virtual void traverse(HMscPtr hmsc);
+
+  /**
+   * Cleans up traversing attributes
+   */
+  virtual void cleanup_traversing_attributes();
+  
+  /**
+   * Adds NodeFinishedListener
+   */
+  void add_node_finished_listener(NodeFinishedListenerP l)
+  {
+    m_node_finished_listeners.push_back(l);
+  }
+  
+  void remove_node_finished_listeners()
+  {
+    m_node_finished_listeners.erase(
+      m_node_finished_listeners.begin(),m_node_finished_listeners.end());
+  }
+  
+  /**
+   * Adds WhiteNodeFoundListener
+   */
+  void add_white_node_found_listener(WhiteNodeFoundListenerP l)
+  {
+    m_white_node_found_listeners.push_back(l);
+  }
+  
+  void remove_white_node_found_listeners()
+  {
+    m_white_node_found_listeners.erase(
+      m_white_node_found_listeners.begin(),m_white_node_found_listeners.end());
+  }
+  
+  /**
+   * Adds GrayNodeFoundListener
+   */
+  void add_gray_node_found_listener(GrayNodeFoundListenerP l)
+  {
+    m_gray_node_found_listeners.push_back(l);
+  }
+  
+  void remove_gray_node_found_listeners()
+  {
+    m_gray_node_found_listeners.erase(
+      m_gray_node_found_listeners.begin(),m_gray_node_found_listeners.end());
+  }
+  
+  /**
+   * Adds BlackNodeFoundListener
+   */
+  void add_black_node_found_listener(BlackNodeFoundListenerP l)
+  {
+    m_black_node_found_listeners.push_back(l);
+  }
+  
+  void remove_black_node_found_listeners()
+  {
+    m_black_node_found_listeners.erase(
+      m_black_node_found_listeners.begin(),m_black_node_found_listeners.end());
+  }
+  
+  void remove_all_listeners()
+  {
+    remove_node_finished_listeners();
+    remove_white_node_found_listeners();
+    remove_gray_node_found_listeners();
+    remove_black_node_found_listeners();
+  }
+  
+  /**
+   * Returns reached InnerNodes in particular phase of traversing.
+   *
+   * The result corresponds to call stack on particular InnerNodes.
+   *
+   * Warning: The result is emptied when cleanup_traversing_attributes() is called
+   */
+  const InnerNodePListList& get_reached_nodes()
+  {
+    return m_reached_nodes;
+  }
+  
+protected:
+  
+  /**
+   * Holds nodes with set color attribute
+   */
+  InnerNodePListList m_colored_nodes;
+
+  /**
+   * Holds currently reached InnerNodes.
+   */
+  InnerNodePListList m_reached_nodes;
+  
+  /**
+   * Cleans up traversing attributes from the top of m_colored_nodes
+   */
+  void cleanup_top_attributes();
+
+  /**
+   * Traverses single node
+   */
+  virtual bool traverse_node(InnerNode* node);
+
+  /**
+   * Traverses successors
+   */
+  virtual bool traverse_successors(const InnerNodePSet& successors);
+    
+  /**
+   * Holds listeners
+   */
+  NodeFinishedListenerPList m_node_finished_listeners;
+  
+  /**
+   * Holds listeners
+   */
+  WhiteNodeFoundListenerPList m_white_node_found_listeners;
+  
+  /**
+   * Holds listeners
+   */
+  GrayNodeFoundListenerPList m_gray_node_found_listeners;
+  
+  /**
+   * Holds listeners
+   */
+  BlackNodeFoundListenerPList m_black_node_found_listeners;
+  
+  /**
+   * Holds listeners
+   */
+  GrayNodeFoundListenerPList m_grey_node_found_listeners;
+  
+  /**
+   * Color attribute's name
+   */
+  std::string m_color_attribute;
+  
+  /**
+   * Called when white InnerNode is found.
+   */
+  virtual void white_node_found(InnerNode* n);
+  
+  /**
+   * Called when gray InnerNode is found.
+   */
+  virtual void gray_node_found(InnerNode* n);
+  
+  /**
+   * Called when black InnerNode is found.
+   */
+  virtual void black_node_found(InnerNode* n);
+  
+  /**
+   * Called when all successors of e are processed.
+   */
+  virtual void node_finished(InnerNode* n);
+  
+  /**
+   * Sets color attribute of e to c value .
+   */
+  void set_color(InnerNode* n, Color c)
+  {
+    n->set_attribute<Color>(m_color_attribute,c);
+  }
+  
+  /**
+   * Returns value of color attribute.
+   *
+   * If attribute isn't set it is set to default value WHITE.
+   */
+  Color get_color(InnerNode* n)
+  {
+    return n->get_attribute<Color>(m_color_attribute,WHITE);
+  }
+  
+};
+
+
+#endif	/* _DFS_MSC_GRAPH_TRAVERSER_H */
+

Modified: trunk/src/check/dfs_events_traverser.cpp
===================================================================
--- trunk/src/check/dfs_events_traverser.cpp	2008-07-16 07:16:36 UTC (rev 102)
+++ trunk/src/check/dfs_events_traverser.cpp	2008-07-27 09:20:07 UTC (rev 103)
@@ -17,12 +17,13 @@
  */
 
 #include "check/dfs_events_traverser.h"
+#include "check/utils.h"
 
 const std::string DFSEventsTraverser::color_attribute = "events_traverse_color";
 
 DFSEventsTraverser::~DFSEventsTraverser()
 {
-  
+  cleanup_traversing_att...
 
[truncated message content]

Thread: [Scstudio-commits] SF.net SVN: scstudio:[103] trunk

scstudio-commits