Menu
▾
▴
[Scstudio-commits] SF.net SVN: scstudio:[123] trunk
|
From: <got...@us...> - 2008-11-28 23:40:01
|
Revision: 123
http://scstudio.svn.sourceforge.net/scstudio/?rev=123&view=rev
Author: gotthardp
Date: 2008-11-28 23:39:47 +0000 (Fri, 28 Nov 2008)
Log Message:
-----------
Directory structure reorganized.
Modified Paths:
--------------
trunk/CMakeLists.txt
trunk/README
trunk/src/CMakeLists.txt
trunk/src/check/CMakeLists.txt
trunk/src/data/CMakeLists.txt
trunk/src/data/Z120/Z120.cpp
trunk/src/data/Z120/Z120.h
trunk/src/data/counted_ptr.h
trunk/src/data/msc.cpp
trunk/src/data/msc.h
trunk/src/data/msc_modifications.h
trunk/src/data/msc_visual.h
trunk/tests/CMakeLists.txt
trunk/tests/acyclic_checker_test.cpp
trunk/tests/deadlock_checker_test.cpp
trunk/tests/dot_writer.h
trunk/tests/fifo_checker_test.cpp
trunk/tests/livelock_checker_test.cpp
Added Paths:
-----------
trunk/src/check/liveness/
trunk/src/check/liveness/CMakeLists.txt
trunk/src/check/liveness/deadlock_checker.cpp
trunk/src/check/liveness/deadlock_checker.h
trunk/src/check/liveness/livelock_checker.cpp
trunk/src/check/liveness/livelock_checker.h
trunk/src/check/order/
trunk/src/check/order/CMakeLists.txt
trunk/src/check/order/acyclic_checker.cpp
trunk/src/check/order/acyclic_checker.h
trunk/src/check/order/fifo_checker.cpp
trunk/src/check/order/fifo_checker.h
trunk/src/check/pseudocode/
trunk/src/check/pseudocode/CMakeLists.txt
trunk/src/check/pseudocode/causal_closure_initiator.cpp
trunk/src/check/pseudocode/causal_closure_initiator.h
trunk/src/check/pseudocode/msc_duplicators.cpp
trunk/src/check/pseudocode/msc_duplicators.h
trunk/src/check/pseudocode/refnode_finder.cpp
trunk/src/check/pseudocode/refnode_finder.h
trunk/src/check/pseudocode/utils.h
trunk/src/check/pseudocode/visual_closure_initiator.cpp
trunk/src/check/pseudocode/visual_closure_initiator.h
trunk/src/check/race/
trunk/src/check/race/CMakeLists.txt
trunk/src/check/race/bmsc_race_checker.cpp
trunk/src/check/race/bmsc_race_checker.h
trunk/src/check/race/footprint.cpp
trunk/src/check/race/footprint.h
trunk/src/check/race/race_checker.cpp
trunk/src/check/race/race_checker.h
trunk/src/data/checker.h
trunk/src/data/dfs_area_traverser.cpp
trunk/src/data/dfs_area_traverser.h
trunk/src/data/dfs_bmsc_graph_traverser.cpp
trunk/src/data/dfs_bmsc_graph_traverser.h
trunk/src/data/dfs_events_traverser.cpp
trunk/src/data/dfs_events_traverser.h
trunk/src/data/dfs_hmsc_traverser.cpp
trunk/src/data/dfs_hmsc_traverser.h
trunk/src/data/dfs_inner_hmsc_traverser.cpp
trunk/src/data/dfs_inner_hmsc_traverser.h
trunk/src/data/dfs_instance_events_traverser.cpp
trunk/src/data/dfs_instance_events_traverser.h
trunk/src/data/dfs_refnode_hmsc_traverser.cpp
trunk/src/data/dfs_refnode_hmsc_traverser.h
trunk/src/data/dfsb_hmsc_traverser.cpp
trunk/src/data/dfsb_hmsc_traverser.h
Removed Paths:
-------------
trunk/src/check/acyclic_checker.cpp
trunk/src/check/acyclic_checker.h
trunk/src/check/bmsc_race_checker.cpp
trunk/src/check/bmsc_race_checker.h
trunk/src/check/causal_closure_initiator.cpp
trunk/src/check/causal_closure_initiator.h
trunk/src/check/checker.h
trunk/src/check/deadlock_checker.cpp
trunk/src/check/deadlock_checker.h
trunk/src/check/dfs_area_traverser.cpp
trunk/src/check/dfs_area_traverser.h
trunk/src/check/dfs_bmsc_graph_traverser.cpp
trunk/src/check/dfs_bmsc_graph_traverser.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_inner_hmsc_traverser.cpp
trunk/src/check/dfs_inner_hmsc_traverser.h
trunk/src/check/dfs_instance_events_traverser.cpp
trunk/src/check/dfs_instance_events_traverser.h
trunk/src/check/dfs_refnode_hmsc_traverser.cpp
trunk/src/check/dfs_refnode_hmsc_traverser.h
trunk/src/check/dfsb_hmsc_traverser.cpp
trunk/src/check/dfsb_hmsc_traverser.h
trunk/src/check/fifo_checker.cpp
trunk/src/check/fifo_checker.h
trunk/src/check/footprint.cpp
trunk/src/check/footprint.h
trunk/src/check/livelock_checker.cpp
trunk/src/check/livelock_checker.h
trunk/src/check/msc_duplicators.cpp
trunk/src/check/msc_duplicators.h
trunk/src/check/race_checker.cpp
trunk/src/check/race_checker.h
trunk/src/check/refnode_finder.cpp
trunk/src/check/refnode_finder.h
trunk/src/check/utils.h
trunk/src/check/visual_closure_initiator.cpp
trunk/src/check/visual_closure_initiator.h
Property Changed:
----------------
trunk/CMakeLists.txt
trunk/src/CMakeLists.txt
trunk/src/check/CMakeLists.txt
trunk/src/data/CMakeLists.txt
trunk/src/data/Z120/CMakeLists.txt
trunk/src/data/Z120/Z120.cpp
trunk/src/data/Z120/Z120.h
trunk/src/data/Z120/main.cpp
trunk/src/data/msc_modifications.h
trunk/tests/CMakeLists.txt
trunk/tests/acyclic_checker_test.cpp
trunk/tests/deadlock_checker_test.cpp
trunk/tests/dot_writer.h
trunk/tests/fifo_checker_test.cpp
trunk/tests/livelock_checker_test.cpp
Modified: trunk/CMakeLists.txt
===================================================================
--- trunk/CMakeLists.txt 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/CMakeLists.txt 2008-11-28 23:39:47 UTC (rev 123)
@@ -9,8 +9,8 @@
INCLUDE(${CMAKE_ROOT}/Modules/Dart.cmake)
INCLUDE_DIRECTORIES(src)
-ADD_SUBDIRECTORY(src .)
-ADD_SUBDIRECTORY(tests .)
+ADD_SUBDIRECTORY(src)
+ADD_SUBDIRECTORY(tests)
-# $Id: CMakeLists.txt,v 1.7 2008/11/06 15:16:29 gotthardp Exp $
+# $Id$
Property changes on: trunk/CMakeLists.txt
___________________________________________________________________
Added: svn:keywords
+ Id
Added: svn:eol-style
+ native
Modified: trunk/README
===================================================================
--- trunk/README 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/README 2008-11-28 23:39:47 UTC (rev 123)
@@ -16,6 +16,7 @@
view/ Applications.
visio/ Microsoft Visio plug-in.
test/ Console application for tests under Unix/Linux.
+ tests/ Automated regression tests.
To get the latest sources
svn co https://scstudio.svn.sourceforge.net/svnroot/scstudio/trunk scstudio
Modified: trunk/src/CMakeLists.txt
===================================================================
--- trunk/src/CMakeLists.txt 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/CMakeLists.txt 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,3 +1,4 @@
ADD_SUBDIRECTORY(data)
ADD_SUBDIRECTORY(check)
+# $Id$
Property changes on: trunk/src/CMakeLists.txt
___________________________________________________________________
Added: svn:keywords
+ Id
Added: svn:eol-style
+ native
Modified: trunk/src/check/CMakeLists.txt
===================================================================
--- trunk/src/check/CMakeLists.txt 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/CMakeLists.txt 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,22 +1,8 @@
-#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(dfsb_hmsc_traverser STATIC dfsb_hmsc_traverser.cpp)
-ADD_LIBRARY(dfs_instance_events_traverser STATIC dfs_instance_events_traverser.cpp)
-ADD_LIBRARY(dfs_bmsc_graph_traverser STATIC dfs_bmsc_graph_traverser.cpp)
-ADD_LIBRARY(refnode_finder STATIC refnode_finder.cpp)
+ADD_SUBDIRECTORY(pseudocode)
-#order relation
-#ADD_LIBRARY(causal_closure_initiator STATIC causal_closure_initiator.cpp)
-ADD_LIBRARY(visual_closure_initiator STATIC visual_closure_initiator.cpp)
+# plug-ins
+ADD_SUBDIRECTORY(liveness)
+ADD_SUBDIRECTORY(order)
+# ADD_SUBDIRECTORY(race)
-#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(livelock_checker STATIC livelock_checker.cpp)
-#ADD_LIBRARY(race_checker STATIC race_checker.cpp)
-
-#other
-#ADD_LIBRARY(footprint STATIC footprint.cpp)
+# $Id$
Property changes on: trunk/src/check/CMakeLists.txt
___________________________________________________________________
Added: svn:keywords
+ Id
Deleted: trunk/src/check/acyclic_checker.cpp
===================================================================
--- trunk/src/check/acyclic_checker.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/acyclic_checker.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,53 +0,0 @@
-/*
- * 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 "check/acyclic_checker.h"
-
-AcyclicCheckerPtr AcyclicChecker::m_instance;
-
-BMsc* AcyclicChecker::create_counter_example(const EventPList& path)
-{
- BMsc* bmsc = new BMsc(path.front()->get_instance()->get_bmsc());
- //TODO: construction of counter example
- return bmsc;
-}
-
-BMscPtr AcyclicChecker::check(BMscPtr bmsc, ChannelMapperPtr chm)
-{
- AcyclicCheckerListener listener;
- DFSEventsTraverser traverser;
- traverser.add_white_event_found_listener(&listener);
- traverser.add_gray_event_found_listener(&listener);
- traverser.add_event_finished_listener(&listener);
- BMscPtr result;
- try
- {
- traverser.traverse(bmsc);
- }
- catch(CycleDetectedException& cde)
- {
- result = create_counter_example(listener.get_path());
- traverser.cleanup_traversing_attributes();
- }
- return result;
-}
-
-void AcyclicChecker::cleanup_attributes()
-{
-
-}
Deleted: trunk/src/check/acyclic_checker.h
===================================================================
--- trunk/src/check/acyclic_checker.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/acyclic_checker.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,110 +0,0 @@
-/*
- * 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 "check/checker.h"
-#include "data/msc.h"
-#include "check/dfs_events_traverser.h"
-
-class AcyclicChecker;
-
-typedef counted_ptr<AcyclicChecker> AcyclicCheckerPtr;
-
-class AcyclicCheckerListener:
-public WhiteEventFoundListener,
-public GrayEventFoundListener,
-public EventFinishedListener
-{
-
-protected:
-
- EventPList m_path;
-
-public:
-
- void on_white_event_found(Event* e)
- {
- m_path.push_back(e);
- }
-
- void on_gray_event_found(Event* e)
- {
- m_path.push_back(e);
- throw CycleDetectedException();
- }
-
- void on_event_finished(Event* e)
- {
- m_path.pop_back();
- }
-
- const EventPList& get_path()
- {
- return m_path;
- }
-
-};
-
-class AcyclicChecker: public Checker, public BMscChecker
-{
-
-protected:
-
- /**
- * Common instance.
- */
- static AcyclicCheckerPtr m_instance;
-
- BMsc* create_counter_example(const EventPList& path);
-
- AcyclicChecker()
- {
- }
-
-public:
-
- ~AcyclicChecker()
- {
- }
-
- /**
- * Checks whether bmsc has acyclic events' dependecy
- */
- BMscPtr check(BMscPtr bmsc, ChannelMapperPtr chm);
-
- /**
- * Cleans up no more needed attributes.
- */
- void cleanup_attributes();
-
- /**
- * Supports all mappers
- */
- bool is_supported(ChannelMapperPtr chm)
- {
- return true;
- }
-
- static AcyclicCheckerPtr instance()
- {
- if(!m_instance.get())
- m_instance = new AcyclicChecker();
- return m_instance;
- }
-
- };
-
Deleted: trunk/src/check/bmsc_race_checker.cpp
===================================================================
--- trunk/src/check/bmsc_race_checker.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/bmsc_race_checker.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,172 +0,0 @@
-/*
- * 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 "check/bmsc_race_checker.h"
-
-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)
-{
- BMsc* bmsc = new BMsc(e1->get_instance()->get_bmsc());
- InstancePtr common_instance = new Instance(bmsc,e1->get_instance());
- bmsc->add_instance(common_instance);
- BoolVector& e2_causal = m_causal_initiator.get_causal_closure(e2);
- size_t e1_index = m_visual_initiator.get_topology_index(e1);
- MscMessagePtr e1_message;
- if(e1->is_send())
- e1_message = new MscMessage(
- common_instance.get(),NULL,e1->get_message().get());
- else
- e1_message = new MscMessage(
- NULL,common_instance.get(),e1->get_message().get());
- MscMessagePtr e2_message;
- if(e2->is_send())
- e2_message = new MscMessage(
- common_instance.get(),NULL,e2->get_message().get());
- else
- e2_message = new MscMessage(
- NULL,common_instance.get(),e2->get_message().get());
- //e2 << e1
- if(e2_causal[e1_index])
- {
- StrictOrderAreaPtr common_strict = new StrictOrderArea(
- common_instance.get());
- StrictEventPtr e1_strict = new StrictEvent(common_strict.get(),e1_message,e1);
- StrictEventPtr e2_strict = new StrictEvent(common_strict.get(),e2_message,e2);
- common_strict->set_first(e1_strict);
- e1_strict->set_successor(e2_strict);
- common_instance->set_first(common_strict);
- }
- //e2 || e1
- else
- {
- CoregionAreaPtr common_coregion = new CoregionArea(common_instance.get());
- CoregionEvent* e1_coregion = new CoregionEvent(
- common_coregion.get(),e1_message,e1);
- CoregionEvent* e2_coregion = new CoregionEvent(
- common_coregion.get(),e2_message,e2);
- common_coregion->add_minimal_event(e1_coregion);
- common_coregion->add_minimal_event(e2_coregion);
- common_instance->set_first(common_coregion);
- }
- return bmsc;
-}
-
-BMscPtr BMscRaceChecker::check(BMscPtr bmsc, ChannelMapperPtr mapper)
-{
- DFSEventsTraverser traverser;
- TopologicalOrderListener topology_listener;
- traverser.add_event_finished_listener(this);
- traverser.traverse(bmsc);
- EventPVector topology(
- topology_listener.get_topology().begin(),
- topology_listener.get_topology().end()
- );
- m_visual_initiator.initialize(topology);
- m_causal_initiator.initialize(topology,m_visual_initiator,mapper);
- OrderCheckerListener order_checker_listener(&m_visual_initiator);
- DFSInstanceEventsTraverser instance_traverser;
- for(size_t i = 0; i < topology.size(); i++)
- {
- //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
- {
- 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());
- }
- }
- return BMscPtr();
-}
-
-void BMscRaceChecker::cleanup_attributes()
-{
- m_visual_initiator.cleanup_attributes();
- m_causal_initiator.cleanup_attributes();
- while(!m_modified_instaces.empty())
- {
- Instance* i = m_modified_instaces.front();
- m_modified_instaces.pop_front();
- i->remove_attribute<EventPList>(m_instance_events_attribute);
- }
-}
Deleted: trunk/src/check/bmsc_race_checker.h
===================================================================
--- trunk/src/check/bmsc_race_checker.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/bmsc_race_checker.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,74 +0,0 @@
-/*
- * 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 _BMSC_RACE_CHECKER_H
-#define _BMSC_RACE_CHECKER_H
-
-#include "data/msc.h"
-#include "check/dfs_events_traverser.h"
-#include "check/visual_closure_initiator.h"
-#include "check/causal_closure_initiator.h"
-
-typedef std::list<Instance*> InstancePList;
-
-class BMscRaceChecker:
-public BMscChecker,
-public TopologicalOrderListener
-{
-
-protected:
-
- VisualClosureInitiator m_visual_initiator;
-
- CausalClosureInitiator m_causal_initiator;
-
- static const std::string m_instance_events_attribute;
-
- InstancePList m_modified_instaces;
-
- EventPList& get_instance_events(Instance* i)
- {
- static EventPList empty;
- return i->get_attribute<EventPList>(m_instance_events_attribute,empty);
- }
-
- /**
- * It was found that e1<e2 but not e1<<e2
- */
- BMsc* create_counter_example(Event* e1, Event* e2);
-
-public:
-
- BMscRaceChecker()
- {
-
- }
-
- BMscPtr check(BMscPtr bmsc, ChannelMapperPtr mapper);
-
- virtual void on_event_finished(Event* event)
- {
- TopologicalOrderListener::on_event_finished(event);
- //used to compare only ordering of events at the same instance
- get_instance_events(event->get_instance()).push_front(event);
- }
-
- void cleanup_attributes();
-
-};
-#endif /* _BMSC_RACE_CHECKER_H */
Deleted: trunk/src/check/causal_closure_initiator.cpp
===================================================================
--- trunk/src/check/causal_closure_initiator.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/causal_closure_initiator.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,106 +0,0 @@
-/*
- * 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/causal_closure_initiator.h"
-
-void CausalClosureInitiator::cleanup_attributes()
-{
- while(!m_modified_events.empty())
- {
- Event* e = m_modified_events.top();
- e->remove_attribute<BoolVector>(m_causal_closure_attribute);
- m_modified_events.pop();
- }
-}
-
-void CausalClosureInitiator::initialize(const EventPVector& events,
- VisualClosureInitiator& visual_closure_init, ChannelMapperPtr mapper)
-{
- //initialize matrix
- size_t events_count = events.size();
- EventPList::const_iterator i;
- //closure[x][y]==true <=> x << y
- std::vector<BoolVector*> closure(events_count);
- for(size_t i=0;i<events_count;i++)
- {
- Event* i_event = events[i];
- BoolVector& causal_closure = get_causal_closure(i_event);
- causal_closure.resize(events_count,false);
- closure[i] = &causal_closure;
- m_modified_events.push(i_event);
- //for any event e: e << e
- causal_closure[i] = true;
- //send event << receive matching event
- if(i_event->is_send() && i_event->is_matched())
- causal_closure[visual_closure_init.get_topology_index(
- i_event->get_matching_event())] = true;
- }
- for(size_t i=0;i<events_count;i++)
- {
- Event* i_event = events[i];
- BoolVector& i_causal_closure = *closure[i];
- BoolVector& i_visual_closure = visual_closure_init.get_visual_closure(i_event);
- for(size_t j = 0; j < events_count; j++)
- {
- Event* j_event = events[j];
- //i_event and j_event are from the same instance, j_event is send event and
- //i_event < j_event
- if(i_event->get_instance()==j_event->get_instance() &&
- j_event->is_send() && i_visual_closure[j])
- {
- i_causal_closure[j] = true;
- }
- //i_event and j_event are send events of the same channel and i_event<j_event
- else if(i_event->is_send() && i_event->is_matched() &&
- j_event->is_matched() && mapper->same_channel(i_event,j_event) &&
- i_visual_closure[j])
- {
- get_causal_closure(i_event->get_matching_event())[
- visual_closure_init.get_topology_index(j_event->get_matching_event())
- ] = true;
- }
- }
- }
- square_closure(closure);
-}
-
-void CausalClosureInitiator::square_closure(std::vector<BoolVector*>& closure)
-{
- size_t events_count = closure.size();
- bool changed = false;
- do
- {
- for(size_t i=0; i<events_count; i++)
- for(size_t j=0; j<events_count; j++)
- if(!(*closure[i])[j] && multiply(closure,i,j))
- (*closure[i])[j] = changed = true;
- }
- while(changed);
-}
-
-bool CausalClosureInitiator::multiply(std::vector<BoolVector*>& closure, size_t row, size_t column)
-{
- for(size_t index=0;index<closure.size();index++)
- {
- if((*closure[row])[index] && (*closure[index])[column])
- return true;
- }
- return false;
-}
Deleted: trunk/src/check/causal_closure_initiator.h
===================================================================
--- trunk/src/check/causal_closure_initiator.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/causal_closure_initiator.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,103 +0,0 @@
-/*
- * 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 _CAUSAL_CLOSURE_INITIATOR_H
-#define _CAUSAL_CLOSURE_INITIATOR_H
-
-#include <stack>
-#include <vector>
-
-#include "data/msc.h"
-#include "check/dfs_instance_events_traverser.h"
-#include "check/visual_closure_initiator.h"
-
-typedef std::stack<Event*> EventPStack;
-
-class CausalClosureInitiator
-{
-
-protected:
-
- /**
- * Used for cleaning up attributes.
- */
- EventPStack m_modified_events;
-
- /**
- * Name of causal closure attribute.
- */
- std::string m_causal_closure_attribute;
-
- /**
- * Logically multiply closure by itself.
- */
- void square_closure(std::vector<BoolVector*>& closure);
-
- /**
- * Logical multiplication of row and column (indeces) of square matrix closure.
- */
- bool multiply(std::vector<BoolVector*>& closure, size_t row, size_t column);
-
-public:
-
- /**
- * Sets explicit names of attributes
- */
- CausalClosureInitiator(
- const std::string& causal_closure_attribute = "causal_closure")
- {
- m_causal_closure_attribute = causal_closure_attribute;
- }
-
-
- /**
- * Cleans up set attributes.
- */
- ~CausalClosureInitiator()
- {
- cleanup_attributes();
- }
-
- /**
- * Getter of causal closure attribute of e.
- */
- BoolVector& get_causal_closure(Event* e)
- {
- static BoolVector empty(1,false);
- return e->get_attribute<BoolVector>(m_causal_closure_attribute,empty);
- }
-
- /**
- * Computes causal closure.
- *
- * A visual_closure_init must be initialized - initialize method must be
- * called before.
- *
- * @param events - topologically sorted events used for visual_closure_init's initialization
- * @param visual_closure_init - initialized VisualClosureInitiator
- */
- void initialize(const EventPVector& events,
- VisualClosureInitiator& visual_closure_init, ChannelMapperPtr mapper);
-
- /**
- * Cleans up set attributes.
- */
- void cleanup_attributes();
-
-};
-#endif /* _CAUSAL_CLOSURE_INITIATOR_H */
Deleted: trunk/src/check/checker.h
===================================================================
--- trunk/src/check/checker.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/checker.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,389 +0,0 @@
-/*
-* 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 _CHECKER_H
-#define _CHECKER_H
-
-#include <exception>
-#include <map>
-
-#include "data/msc.h"
-#include "data/counted_ptr.h"
-
-class ChannelMapper;
-class Checker;
-class HMscChecker;
-class BMscChecker;
-
-typedef counted_ptr<ChannelMapper> ChannelMapperPtr;
-typedef counted_ptr<Checker> CheckerPtr;
-typedef counted_ptr<HMscChecker> HMscCheckerPtr;
-typedef counted_ptr<BMscChecker> BMscCheckerPtr;
-
-/**
- * Basic abstract class for all checking algorithms.
- */
-class Checker
-{
-
-public:
-
- /**
- * Removes no more needed attributes.
- *
- * Descendat of this class should remove attributes of MscElements that are no
- * more needed. This method should be called after finish of algorithm.
- */
- virtual void cleanup_attributes()=0;
-
- /**
- * Checks whether Checker supports given ChannelMapper.
- *
- * Deafult behaviour is false for all mappers, but it is neccessary to check
- * out this behaviour in individual checkers.
- */
- virtual bool is_supported(ChannelMapperPtr chm)=0;
-
- virtual ~Checker()
- {
-
- }
-};
-
-/**
-* Basic abstract class for checking algorithms of HMsc.
-*/
-class HMscChecker
-{
-
-protected:
-
- /**
- * Hidden constructor.
- */
- HMscChecker()
- {
- }
-
-public:
-
- ~HMscChecker()
- {
- }
-
- /**
- * Checks HMsc against specific property.
- *
- * Returns MscPathPtr with violating example if there is any in hmsc
- * otherwise HMscPathPtr is undefined.
- * @param hmsc - HMsc to be checked
- * @param mapper - ChannelMapper which is chosen as delivery semantic
- */
- virtual HMscPtr check(HMscPtr hmsc, ChannelMapperPtr mapper)=0;
-};
-
-/**
-* Basic abstract class for checking algorithms of BMsc.
-*/
-class BMscChecker
-{
-
-protected:
-
- /**
- * Singleton instance.
- */
- static BMscCheckerPtr m_checker;
-
-public:
-
- /**
- * Checks BMsc against specific property.
- *
- * Returns BMscPtr with violating example if there is any in bmsc otherwise
- * BMscPtr is undefined.
- * @param bmsc - BMsc to be checked
- * @param mapper - ChannelMapper which is chosen as delivery semantic
- */
- virtual BMscPtr check(BMscPtr bmsc, ChannelMapperPtr mapper)=0;
-};
-
-/**
- * Abstract class whose purpose is to decide whether two Messages belongs to the
- * same channel or not and assign to a message ID of channel which the message
- * belongs to. This class shortly defines delivery semantic.
- */
-class ChannelMapper
-{
-
-public:
-
- virtual ~ChannelMapper()
- {
-
- }
-
- /**
- * Returns true if e1's message belongs to the same channel as e2's message.
- */
- virtual bool same_channel(const Event* e1, const Event* e2) const=0;
-
- /**
- * Returns index of channel which event's message belongs into.
- *
- * @warning event must have set message
- */
- virtual size_t channel(const Event* event)=0;
-
- /**
- * Returns number of different channels mapped by this channel mapper
- */
- virtual size_t get_channel_count()=0;
-
- /**
- * Returns copy of this channel mapper without registered channels.
- *
- * Usefull if you need to have the same functionality of the original mapper,
- * but you don't want to work with all registered events by the original one.
- * This approach may increase efficiency in some cases.
- */
- virtual ChannelMapperPtr copy()=0;
-};
-
-/**
- * Basic implementation of ChannelMapper.
- */
-template<typename MessagePart>
-class GeneralMapper:public ChannelMapper
-{
-
-public:
-
- typedef std::map<MessagePart,size_t> ChannelMap;
-
-protected:
-
- /**
- * Common instance of GeneralMapper.
- */
- static counted_ptr<GeneralMapper<MessagePart> > m_instance;
-
- /**
- * Holds identificators of channels represented by MessagePart of MscMessage.
- */
- std::map<MessagePart,size_t> m_channels;
-
- /**
- * Use GeneralMapper::instance() to obtain instance of GeneralMapper
- */
- GeneralMapper(){};
-
-public:
-
- /**
- * Returns true if m1 belongs to the same channel as m2.
- */
- bool same_channel(const Event* e1, const Event* e2) const
- {
- return MessagePart::same_channel(e1,e2);
- }
-
- /**
- * Returns index of channel which event's message belongs into.
- */
- size_t channel(const Event* event)
- {
- MessagePart part(event);
- typename ChannelMap::iterator i = m_channels.find(part);
- if(i==m_channels.end())
- {
- size_t id = m_channels.size();
- m_channels[part] = id;
- return id;
- }
- return i->second;
- }
-
- /**
- * Returns common instance of ChannelMapper
- */
- static counted_ptr<GeneralMapper<MessagePart> > instance()
- {
- if(m_instance.get()==NULL)
- {
- counted_ptr<GeneralMapper<MessagePart> > p(new GeneralMapper<MessagePart>());
- m_instance = p;
- }
- return m_instance;
- }
-
- /**
- * Returns number of channel registered by this channel mapper
- */
- size_t get_channel_count()
- {
- return m_channels.size();
- }
-
- /**
- * Returns copy of this channel mapper without registered channels.
- *
- * Usefull if you need to have the same functionality of the original mapper,
- * but you don't want to work with all registered events by the original one.
- */
- ChannelMapperPtr copy()
- {
- return ChannelMapperPtr(new GeneralMapper<MessagePart>());
- }
-
-};
-
-/**
- * Used in GeneralMapper template to decide whether two messages belongs to the
- * same channel (delivery semantic).
- *
- * For decision send and receive instances' labels are used.
- *
- * To see delivery semantic of this class see operator<() and same_channel()
- * methods of this class.
- */
-class SRMessagePart
-{
-
- std::string m_sender;
-
- std::string m_receiver;
-
-public:
-
- SRMessagePart(const Event* e)
- {
- m_sender = e->get_sender_label();
- m_receiver = e->get_receiver_label();
- }
-
- /**
- * Used in std::map as comparision function
- */
- bool operator<(const SRMessagePart& mp) const
- {
- int s = m_sender.compare(mp.m_sender);
- int r = m_receiver.compare(mp.m_receiver);
- return s<0 || s+r<0;
- }
-
- /**
- * Channels of message m1 and m2 are same if and only if m1 has got same
- * sender and receiver as m2.
- */
- static bool same_channel(const Event* e1, const Event* e2)
- {
- if((e1->is_send() && e2->is_send()) || (e1->is_receive() && e2->is_receive()))
- {
- return e1->get_sender_label()==e2->get_sender_label() &&
- e2->get_receiver_label()==e2->get_receiver_label();
- }
- return false;
- }
-};
-
-/**
- * Used in GeneralMapper template to decide whether two messages belongs to the
- * same channel (delivery semantic).
- *
- * For decision send and receive instances' labels and message label are used.
- *
- * To see delivery semantic of this class see operator<() and same_channel()
- * methods of this class.
- */
-class SRLMessagePart {
-
- std::string m_sender;
-
- std::string m_receiver;
-
- std::string m_label;
-
-public:
-
- SRLMessagePart(const Event* e)
- {
- m_sender = e->get_sender_label();
- m_receiver = e->get_receiver_label();
- m_label = e->get_message()->get_label();
- }
-
- bool operator<(const SRLMessagePart& mp) const
- {
- int s = m_sender.compare(mp.m_sender);
- int r = m_receiver.compare(mp.m_receiver);
- int l = m_label.compare(mp.m_label);
- return s<0 || (s==0 && (r<0 || (r==0 && l<0)));
- }
-
- /**
- * Channels of message of e1 and e2 are same if and only if e1 has got same
- * sender, receiver and label as e2.
- */
- static bool same_channel(const Event* e1,const Event* e2)
- {
- return e1->get_sender_label()==e2->get_sender_label() &&
- e1->get_receiver_label()==e2->get_receiver_label() &&
- e1->get_message()->get_label()==e2->get_message()->get_label();
- }
-};
-
-typedef GeneralMapper<SRMessagePart> SRChannelMapper;
-typedef GeneralMapper<SRLMessagePart> SRLChannelMapper;
-
-typedef counted_ptr<SRChannelMapper> SRChannelMapperPtr;
-typedef counted_ptr<SRLChannelMapper> SRLChannelMapperPtr;
-
-template <class T>
-counted_ptr<GeneralMapper<T> > GeneralMapper<T>::m_instance;
-
-enum Color
-{
- WHITE,
- GRAY,
- BLACK
-};
-
-/**
- * Trohwn when acyclic relation is required and cycle was found.
- */
-class CycleDetectedException:public std::exception
-{
- virtual const char* what() const throw()
- {
- return "Acyclic graph expected but there was found cycle";
- }
-};
-
-/**
- * Thrown when unsupported channel mapper acquired.
- */
-class UnsupportedMapperException:public std::exception
-{
- virtual const char* what() const throw()
- {
- return "Unsupported channel mapper";
- }
-};
-#endif /* _CHECKER_H */
-
Deleted: trunk/src/check/deadlock_checker.cpp
===================================================================
--- trunk/src/check/deadlock_checker.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/deadlock_checker.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,184 +0,0 @@
-/*
- * 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 "dfsb_hmsc_traverser.h"
-
-
-#include "check/deadlock_checker.h"
-
-DeadlockCheckerPtr DeadlockChecker::m_instance;
-
-DeadlockFreeMarker::DeadlockFreeMarker(DeadlockListener* dl):m_dl(dl)
-{
-
-}
-
-void DeadlockFreeMarker::on_white_node_found(HMscNode* n)
-{
- bool& deadlock_free = m_dl->get_deadlock_free(n);
- deadlock_free = true;
-}
-
-DeadlockListener::DeadlockListener(
- const std::string& deadlock_free_attribute,
- const std::string& depth_attribute):
- m_current_depth(0),
- m_deadlock_free_attribute(deadlock_free_attribute),
- m_depth_attribute(depth_attribute)
- {
- m_marker = DeadlockFreeMarker(this);
- m_marker_traverser.add_white_node_found_listener(&m_marker);
- }
-
-bool& DeadlockListener::get_deadlock_free(HMscNode* node)
-{
- bool status;
- bool& deadlock_free = node->get_attribute<bool>(m_deadlock_free_attribute,false,status);
- if(status)
- {
- m_modified.push_back(node);
- }
- return deadlock_free;
-}
-
-size_t& DeadlockListener::get_depth(HMscNode* node)
-{
- return node->get_attribute<size_t>(m_depth_attribute,0);
-}
-
-void DeadlockListener::on_white_node_found(HMscNode* node)
-{
- //set depth attribute
- m_current_depth++;
- get_depth(node) = m_current_depth;
- if (dynamic_cast<ReferenceNode*> (node))
- {
- m_depths.push(m_current_depth);
- }
- //set deadlock free attribute
- bool& deadlock_free = get_deadlock_free(node);
- if (dynamic_cast<EndNode*>(node))
- {
- mark_deadlock_free(node);
- }
-}
-
-void DeadlockListener::on_node_finished(HMscNode* node)
-{
- if (dynamic_cast<ReferenceNode*> (node) ||
- dynamic_cast<StartNode*> (node))
- {
- if (!get_deadlock_free(node))
- {
- throw DeadlockException();
- }
- //this node is no more on traversing stack
- m_depths.pop();
- }
- m_current_depth--;
-}
-
-void DeadlockListener::on_gray_node_found(HMscNode* node)
-{
- //m_depths can be empty
- if (!m_depths.empty())
- {
- //depth of node is surely set (in on_white_node_found())
- size_t node_depth = get_depth(node);
- size_t top_reference_depth = m_depths.top();
- //there is some ReferenceNode on path from node to previous white HMscNode
- if (top_reference_depth >= m_current_depth)
- {
- mark_deadlock_free(node);
- }
- }
-}
-
-void DeadlockListener::mark_deadlock_free(HMscNode* node)
-{
- m_marker_traverser.traverse(node);
-}
-
-void DeadlockListener::cleanup_attributes()
-{
- while (!m_modified.empty())
- {
- m_modified.back()->remove_attribute<bool>(m_deadlock_free_attribute);
- m_modified.back()->remove_attribute<size_t>(m_depth_attribute);
- m_modified.pop_back();
- }
-}
-
-HMscPtr DeadlockChecker::create_counter_example(const MscElementPListList& path)
-{
-// InnerNodePListList::const_iterator hmscs_it;
-// HMscPtr result;
-// for (hmscs_it = path.begin(); hmscs_it != path.end(); hmscs_it++)
-// {
-// 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++)
-// {
-// if (last_node == NULL)
-// {
-// 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;
-// }
-// }
-// }
-// return result;
- HMscPtr example = new HMsc("counter example");
- return example;
-}
-
-HMscPtr DeadlockChecker::check(HMscPtr hmsc, ChannelMapperPtr chm)
-{
- //this will be used do show eventual counterexample
- HMscPtr p;
- DeadlockListener listener;
- DFSHMscTraverser traverser;
- traverser.add_white_node_found_listener(&listener);
- traverser.add_gray_node_found_listener(&listener);
- traverser.add_node_finished_listener(&listener);
- try
- {
- traverser.traverse(hmsc);
- }
- catch (DeadlockException)
- {
- p = create_counter_example(traverser.get_reached_elements());
- traverser.cleanup_traversing_attributes();
- }
- return p;
-}
-
-void DeadlockChecker::cleanup_attributes()
-{
-}
Deleted: trunk/src/check/deadlock_checker.h
===================================================================
--- trunk/src/check/deadlock_checker.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/deadlock_checker.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,156 +0,0 @@
-/*
- * 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 <string>
-#include <stack>
-#include <exception>
-
-#include "check/checker.h"
-#include "data/msc.h"
-#include "data/counted_ptr.h"
-#include "check/dfs_hmsc_traverser.h"
-#include "check/dfsb_hmsc_traverser.h"
-
-class DeadlockChecker;
-class DeadlockListener;
-
-typedef counted_ptr<DeadlockChecker> DeadlockCheckerPtr;
-
-class DeadlockException:public std::exception
-{
-
-public:
-
- const char* what()
- {
- return "There was found deadlock in HMsc";
- }
-};
-
-class DeadlockFreeMarker:public WhiteNodeFoundListener
-{
-
- DeadlockListener* m_dl;
-
-public:
-
- DeadlockFreeMarker(DeadlockListener* dl=NULL);
-
- void on_white_node_found(HMscNode* n);
-
-};
-
-class DeadlockListener:
-public WhiteNodeFoundListener,
-public GrayNodeFoundListener,
-public NodeFinishedListener
-{
-
-protected:
-
- /**
- * Depth of last found white HMscNode in Depth First Search tree
- */
- size_t m_current_depth;
-
- /**
- * Depths of founded ReferenceNodes
- */
- std::stack<size_t> m_depths;
-
- std::string m_deadlock_free_attribute;
-
- std::string m_depth_attribute;
-
- HMscNodePList m_modified;
-
- DFSBHMscTraverser m_marker_traverser;
-
- DeadlockFreeMarker m_marker;
-
- size_t& get_depth(HMscNode* node);
-
-public:
-
- DeadlockListener(
- const std::string& deadlock_free_attribute ="dl:deadlock_free",
- const std::string& depth_attribute ="dl:depth");
-
- void on_white_node_found(HMscNode* node);
-
- void on_node_finished(HMscNode* node);
-
- void on_gray_node_found(HMscNode* node);
-
- void mark_deadlock_free(HMscNode* node);
-
- void cleanup_attributes();
-
- bool& get_deadlock_free(HMscNode* node);
-
- ~DeadlockListener()
- {
- cleanup_attributes();
- }
-};
-
-class DeadlockChecker: public Checker, public HMscChecker
-{
-
-protected:
-
- /**
- * Common instance.
- */
- static DeadlockCheckerPtr m_instance;
-
- DeadlockChecker(){};
-
- HMscPtr create_counter_example(const MscElementPListList& path);
-
-public:
-
- /**
- * Checks whether hmsc satisfy deadlock free property.
- */
- HMscPtr check(HMscPtr hmsc, ChannelMapperPtr chm);
-
- /**
- * Cleans up no more needed attributes.
- */
- void cleanup_attributes();
-
- /**
- * Supports all mappers
- */
- bool is_supported(ChannelMapperPtr chm)
- {
- return true;
- }
-
- ~DeadlockChecker(){}
-
- static DeadlockCheckerPtr instance()
- {
- if(!m_instance.get())
- m_instance = new DeadlockChecker();
- return m_instance;
- }
-
- };
-
Deleted: trunk/src/check/dfs_area_traverser.cpp
===================================================================
--- trunk/src/check/dfs_area_traverser.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/dfs_area_traverser.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,89 +0,0 @@
-/*
- * 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 "check/dfs_area_traverser.h"
-
-DFSAreaTraverser::DFSAreaTraverser(const std::string& color):
-DFSEventsTraverser(color)
-{
-
-}
-
-void DFSAreaTraverser::traverse_area(EventArea* area)
-{
- if(!area) return;
- StrictOrderArea* strict = dynamic_cast<StrictOrderArea*>(area);
- if(strict)
- {
- if(!strict->is_empty())
- traverse_strict_event(strict->get_first().get());
- }
- else
- {
- CoregionArea* coregion = dynamic_cast<CoregionArea*>(area);
- const CoregionEventPSet& minimals = coregion->get_minimal_events();
- CoregionEventPSet::const_iterator min;
- for(min=minimals.begin(); min!=minimals.end(); min++)
- traverse_coregion_event(*min);
- }
-}
-
-void DFSAreaTraverser::traverse(BMscPtr bmsc)
-{
- InstancePtrList::const_iterator instance;
- const InstancePtrList& instances = bmsc->get_instances();
- for(instance=instances.begin(); instance!=instances.end(); instance++)
- {
- EventArea* area = (*instance)->get_first().get();
- while(area)
- {
- traverse_area(area);
- area = area->get_next().get();
- }
- }
- cleanup_traversing_attributes();
-}
-
-void DFSAreaTraverser::traverse_coregion_event(CoregionEvent* event)
-{
- m_reached_elements.push_back(event);
- if(!is_processed(event))
- {
- const CoregEventRelPtrSet& successors = event->get_successors();
- CoregEventRelPtrSet::const_iterator successor;
- for(successor=successors.begin(); successor!=successors.end(); successor++)
- {
- m_reached_elements.push_back((*successor).get());
- traverse_coregion_event((*successor)->get_successor());
- m_reached_elements.pop_back();
- }
- event_finished(event);
- }
-}
-
-void DFSAreaTraverser::traverse_strict_event(StrictEvent* event)
-{
- m_reached_elements.push_back(event);
- if(!is_processed(event))
- {
- if(event->get_successor().get())
- traverse_strict_event(event->get_successor().get());
- event_finished(event);
- }
-}
-
Deleted: trunk/src/check/dfs_area_traverser.h
===================================================================
--- trunk/src/check/dfs_area_traverser.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/dfs_area_traverser.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,55 +0,0 @@
-/*
- * 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_AREA_TRAVERSER_H
-#define _DFS_AREA_TRAVERSER_H
-
-#include "check/dfs_instance_events_traverser.h"
-
-/**
- * Processes EventAreas' events in sequence and do not follow matching events
- * during traversing.
- *
- * Single EventAreas are traversed in depth first search manner.
- */
-class DFSAreaTraverser:public DFSEventsTraverser
-{
-
-public:
-
- DFSAreaTraverser(const std::string& color="color");
-
- void traverse(BMscPtr bmsc);
-
-protected:
-
- void traverse_area(EventArea* area);
-
- /**
- * Doesn't continue in traversing next EventArea in case of event hasn't got
- * any successors.
- */
- void traverse_coregion_event(CoregionEvent* event);
-
- void traverse_strict_event(StrictEvent* event);
-
-};
-
-
-#endif /* _DFS_AREA_TRAVERSER_H */
-
Deleted: trunk/src/check/dfs_bmsc_graph_traverser.cpp
===================================================================
--- trunk/src/check/dfs_bmsc_graph_traverser.cpp 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/dfs_bmsc_graph_traverser.cpp 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,222 +0,0 @@
-/*
- * 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"
-
-void DFSListenersContainer::white_node_found(HMscNode* 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);
-}
-
-void DFSListenersContainer::gray_node_found(HMscNode* 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 DFSListenersContainer::black_node_found(HMscNode* 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 DFSListenersContainer::node_finished(HMscNode* n)
-{
- NodeFinishedListenerPList::iterator l;
- for(l=m_node_finished_listeners.begin();l!=m_node_finished_listeners.end();l++)
- (*l)->on_node_finished(n);
-}
-
-DFSListenersContainer::~DFSListenersContainer()
-{
-
-}
-
-DFSBMscGraphTraverser::~DFSBMscGraphTraverser()
-{
- cleanup_traversing_attributes();
-}
-
-void DFSBMscGraphTraverser::traverse(HMscPtr hmsc)
-{
- push_top_attributes();
- traverse_node(hmsc->get_start().get());
- cleanup_traversing_attributes();
-}
-
-void DFSBMscGraphTraverser::traverse(HMscNode* node)
-{
- push_top_attributes();
- traverse_node(node);
- cleanup_traversing_attributes();
-}
-
-bool DFSBMscGraphTraverser::traverse_node(HMscNode* node)
-{
- m_reached_elements.back().push_back(node);
- if(is_processed(node))
- {
- return false;
- }
- white_node_found(node);
- ReferenceNode* ref_node = dynamic_cast<ReferenceNode*>(node);
- bool ending_successors;
- if(ref_node!=NULL)
- {
- ending_successors = traverse_reference_node(ref_node);
- }
- else
- {
- ConnectionNode* conn_node = dynamic_cast<ConnectionNode*>(node);
- if(conn_node)
- {
- ending_successors = traverse_successors(conn_node);
- }
- else
- {
- StartNode* start_node = dynamic_cast<StartNode*>(node);
- if(start_node)
- {
- ending_successors = traverse_successors(start_node);
- }
- else
- {
- //node is supposed to be EndNode
- ending_successors = true;
- }
- }
- }
- node_finished(node);
- return ending_successors;
-}
-
-bool DFSBMscGraphTraverser::traverse_reference_node(ReferenceNode* ref_node)
-{
- HMscPtr hmsc = ref_node->get_hmsc();
- bool inner = true;
- if(hmsc.get()!=NULL)
- {
- //this line ensures (yet another one) that HMsc will be traversed as many times
- //as it is referenced
- push_top_attributes();
- //node's successors aren't traversed if end node wasn't found in hmsc
- inner = traverse_node(hmsc->get_start().get());
- //this line ensures (yet another one) that HMsc will traversed as many times
- //as it is referenced
- cleanup_top_attributes();
- }
- return inner && traverse_successors(ref_node);
-}
-
-bool DFSBMscGraphTraverser::traverse_successors(PredecessorNode* predecessor)
-{
- bool end_found = false;
- NodeRelationPtrSet::const_iterator relation;
- for(relation=predecessor->get_successors().begin();
- relation!=predecessor->get_successors().end();relation++)
- {
- const NodeRelationPtr& rel = *relation;
- m_reached_elements.back().push_back(rel.get());
- end_found = traverse_node(dynamic_cast<HMscNode*>(rel->get_successor())) || end_found;
- m_reached_elements.back().pop_back();
- }
- return end_found;
-}
-
-bool DFSBMscGraphTraverser::is_processed(HMscNode* node)
-{
- Color c = get_color(node);
- if(c==BLACK)
- {
- black_node_found(node);
- return true;
- }
- if(c==GRAY)
- {
- gray_node_found(node);
- return true;
- }
- return false;
-}
-
-void DFSBMscGraphTraverser::cleanup_traversing_attributes()
-{
- while(!m_colored_nodes.empty())
- {
- cleanup_top_attributes();
- }
-}
-
-void DFSBMscGraphTraverser::white_node_found(HMscNode* n)
-{
- DFSListenersContainer::white_node_found(n);
- set_color(n,GRAY);
-}
-
-void DFSBMscGraphTraverser::gray_node_found(HMscNode* n)
-{
- DFSListenersContainer::gray_node_found(n);
- m_reached_elements.back().pop_back();
-}
-
-void DFSBMscGraphTraverser::black_node_found(HMscNode* n)
-{
- DFSListenersContainer::black_node_found(n);
- m_reached_elements.back().pop_back();
-}
-
-void DFSBMscGraphTraverser::node_finished(HMscNode* n)
-{
- DFSListenersContainer::node_finished(n);
- m_reached_elements.back().pop_back();
- set_color(n,BLACK);
-}
-
-void DFSBMscGraphTraverser::cleanup_top_attributes()
-{
- HMscNodePList& top = m_colored_nodes.back();
- HMscNodePList::iterator event;
- for(event=top.begin();event!=top.end();event++)
- (*event)->remove_attribute<Color>(m_color_attribute);
- m_colored_nodes.pop_back();
- m_reached_elements.pop_back();
-}
-
-void DFSBMscGraphTraverser::push_top_attributes()
-{
- m_colored_nodes.push_back(HMscNodePList());
- m_reached_elements.push_back(MscElementPList());
-}
-
-Color DFSBMscGraphTraverser::get_color(HMscNode* n)
-{
- bool just_set;
- Color c = n->get_attribute<Color>(m_color_attribute,WHITE,just_set);
- if(just_set)
- {
- m_colored_nodes.back().push_back(n);
- }
- return c;
-}
-
Deleted: trunk/src/check/dfs_bmsc_graph_traverser.h
===================================================================
--- trunk/src/check/dfs_bmsc_graph_traverser.h 2008-11-28 20:26:06 UTC (rev 122)
+++ trunk/src/check/dfs_bmsc_graph_traverser.h 2008-11-28 23:39:47 UTC (rev 123)
@@ -1,465 +0,0 @@
-/*
- * 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<HMscNode*> HMscNodePList;
-typedef std::list<HMscNodePList> HMscNodePListList;
-typedef std::list<MscElement*> MscElementPList;
-typedef std::list<MscElementPList> MscElementPListList;
-
-
-/**
- * Listener of founded white HMscNode
- */
-class WhiteNodeFoundListener
-{
-public:
-
- virtual ~WhiteNodeFoundListener()
- {
-
- }
-
- virtual void on_white_node_found(HMscNode* n)=0;
-};
-
-/**
- * Listener of founded gray HMscNode
- */
-class GrayNodeFoundListener
-{
-public:
-
- virtual ~GrayNodeFoundListener()
- {
-
- }
-
- virtual void on_gray_node_found(HMscNode* n)=0;
-};
-
-/**
- * Listener of founded black HMscNode
- */
-class BlackNodeFoundListener
-{
-public:
-
- virtual ~BlackNodeFoundListener()
- {
-
- }
-
- virtual void on_black_node_found(HMscNode* n)=0;
-};
-
-/**
- * Listener of finished HMscNode
- */
-class NodeFinishedListener
-{
-public:
-
- virtual ~NodeFinishedListener()
- {
-
- }
-
- virtual void on_node_finished(HMscNode* node)=0;
-};
-
-/**
- * Auxiliary listener of founded white HMscNode.
- *
- * Extend this listener to process only ReferenceNodes during traversing.
- */
-class WhiteRefNodeFoundListener:public WhiteNodeFoundListener
-{
-public:
-
- virtual ~WhiteRefNodeFoundListener()
- {
-
- }
-
- virtual void on_white_node_found(HMscNode* 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 HMscNode.
- *
- * Extend this listener to process only ReferenceNodes during traversing.
- */
-class GrayRefNodeFoundListener:public GrayNodeFoundListener
-{
-public:
-
- virtual ~GrayRefNodeFoundListener()
- {
-
- }
-
- virtual void on_gray_node_found(HMscNode* n){
- Ref...
[truncated message content] |
