%{
#include <string>
#include <set>
using namespace std;
#include "fault_tree_textual_parser/fault_tree_textual_parser_includes.h"
#include "basic_types/bijection.h"
#ifdef FT_PARSER_DEBUG
extern string fault_tree_textual_parser_debug_string;
#endif // FT_PARSER_DEBUG
extern int fault_tree_textual_parser_lineno;
extern int fault_tree_textual_parser_lex();
extern void fault_tree_textual_parser_error(string s);
extern void fault_tree_textual_parser_scanner_initialize(FILE* in_input_file);
const Event Event_By_Identifier(const string &in_identifier);
const Input_Sequence Identifier_List_To_Input_Sequence(const list<string> &in_identifiers);
bool Cycle_Already_Reported(const searchable_list<Event>& in_cycle, const set< searchable_list<Event> >& in_cycles_reported);
void Check_For_Cycles_Recursive(const searchable_list<Event>& in_path, set< searchable_list<Event> >& in_cycles_reported);
void Ensure_No_Cycles_In_Inputs();
void Ensure_Corresponding_References_And_Definitions();
void Ensure_Spare_Gate_Inputs_Are_Basic_Events();
void Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates();
void Ensure_FDEP_Trigger_Is_Not_Replicated();
void Ensure_FDEP_Dependents_Are_Basic_Events();
const string Get_Identifier_For_Event(const Event &in_event);
Fault_Tree parsed_fault_tree;
bijection<string, Event> identifiers_to_events;
extern void Ensure_Valid_System_Event();
// This is an additional check to avoid generating lots of unconstrained
// trees. We would need to update the grammar to get this.
void Ensure_Connectedness();
void Compute_Reachable_Events(const Event& in_event, set<Event>& in_subgraph);
Threshold fault_tree_textual_parser_threshold;
Event fault_tree_textual_parser_trigger;
string NOT_FOUND("<NOT FOUND>");
set<string> declarations;
%}
%union {
string* text;
Natural* natural;
Replication* replication;
char* character;
Event* event;
int token;
list<string>* text_list;
Threshold* threshold;
}
%token <text> IDENTIFIER
%token <natural> NATURAL
%token <natural> ZERO
%type <replication> replication_parameter
%type <threshold> threshold_parameter
%type <text> identifier_nonterminal
%token SYSTEM_EVENT
%token AND
%token OR
%token THRESHOLD
%token PAND
%token SPARE
%token SEQ
%token FDEP
%token BE
%token SEMICOLON
%token MAXIMUM
%token TRIGGER
%token EQUALS
%token REPLICATION
%type <natural> natural_nonterminal
%type <token> constraint_type_and_parameter_specifier
%type <token> gate_type_and_parameter_specifier
%type <text_list> identifier_list
%type <event> trigger_parameter
%token END_OF_FILE
%%
fault_tree:
system_event gate_or_basic_event eof {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a gate or basic event.\n";
#endif // FT_PARSER_DEBUG
} |
system_event gate_or_basic_event node_list eof {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed multiple gates and basic events.\n";
#endif // FT_PARSER_DEBUG
};
system_event:
SYSTEM_EVENT EQUALS identifier_nonterminal SEMICOLON {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "Parsed a system event.\n";
#endif // FT_PARSER_DEBUG
Event system_event = Event_By_Identifier(*$3);
parsed_fault_tree.Set_Event_Description(system_event,*$3);
parsed_fault_tree.Set_System_Event(system_event);
delete $3;
}
{
Event system_event = Event_By_Identifier(*$3);
if (parsed_fault_tree.Event_Not_Referenced(system_event))
parsed_fault_tree.Remove_Event_Description(system_event);
parsed_fault_tree.Unset_System_Event();
delete $3;
};
eof:
END_OF_FILE {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed the end of the file.\n";
#endif // FT_PARSER_DEBUG
// This is a check which is specific to the textual language.
Ensure_Corresponding_References_And_Definitions();
// Now do the various checks for consistency as specified in the formal
// definition of fault trees. Other checks (e.g. gates have replication
// of 1) are not necessary because they are handled during creation of
// the fault tree.
Ensure_Valid_System_Event();
Ensure_No_Cycles_In_Inputs();
Ensure_Spare_Gate_Inputs_Are_Basic_Events();
Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates();
Ensure_FDEP_Trigger_Is_Not_Replicated();
Ensure_FDEP_Dependents_Are_Basic_Events();
// This is an additional check to avoid generating lots of unconstrained
// trees. We would need to update the grammar to get this.
Ensure_Connectedness();
};
gate_or_basic_event:
gate {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a gate\n";
#endif // FT_PARSER_DEBUG
} |
basic_event {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a basic event\n";
#endif // FT_PARSER_DEBUG
};
node_list:
node {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a node\n";
#endif // FT_PARSER_DEBUG
} |
node_list node {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed multiple nodes\n";
#endif // FT_PARSER_DEBUG
};
node:
gate {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a gate\n";
#endif // FT_PARSER_DEBUG
} |
constraint {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed constraint\n";
#endif // FT_PARSER_DEBUG
} |
basic_event {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed basic event\n";
#endif // FT_PARSER_DEBUG
} |
// Try to go on to the next definition if we hit an error
error SEMICOLON
;
gate:
identifier_nonterminal gate_type_and_parameter_specifier identifier_list SEMICOLON {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a gate, identifier: \"" + *$1 + "\"\n";
#endif // FT_PARSER_DEBUG
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "Gate \"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event gate = Event_By_Identifier(*$1);
parsed_fault_tree.Set_Event_Description(gate,*$1);
Input_Sequence inputs = Identifier_List_To_Input_Sequence(*$3);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = inputs.begin(), an_input_identifier = (*$3).begin();
an_input_event != inputs.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Set_Gate_Inputs(gate,inputs);
switch ($2)
{
case AND :
parsed_fault_tree.Insert_And_Gate(gate);
break;
case OR :
parsed_fault_tree.Insert_Or_Gate(gate);
break;
case THRESHOLD :
parsed_fault_tree.Insert_Threshold_Gate(gate,fault_tree_textual_parser_threshold);
break;
case PAND :
parsed_fault_tree.Insert_Pand_Gate(gate);
break;
case SPARE :
parsed_fault_tree.Insert_Spare_Gate(gate);
break;
default :
fault_tree_textual_parser_error("Parser is broken: gate_type_and_parameter_specifier returned unknown type");
}
}
delete $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event gate = Event_By_Identifier(*$1);
Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(gate);
parsed_fault_tree.Remove_Gate_Inputs(gate);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = inputs.begin(); an_input_event != inputs.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
switch ($2)
{
case AND :
parsed_fault_tree.Remove_And_Gate(gate);
break;
case OR :
parsed_fault_tree.Remove_Or_Gate(gate);
break;
case THRESHOLD :
parsed_fault_tree.Remove_Threshold_Gate(gate);
break;
case PAND :
parsed_fault_tree.Remove_Pand_Gate(gate);
break;
case SPARE :
parsed_fault_tree.Remove_Spare_Gate(gate);
break;
default :
assert(false);
}
if (parsed_fault_tree.Event_Not_Referenced(gate))
parsed_fault_tree.Remove_Event_Description(gate);
}
delete $1;
};
identifier_nonterminal:
IDENTIFIER {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an identifier: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
$$ = $1;
};
gate_type_and_parameter_specifier:
AND {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an AND gate\n";
#endif // FT_PARSER_DEBUG
$$ = AND;
} |
OR {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an OR gate\n";
#endif // FT_PARSER_DEBUG
$$ = OR;
} |
THRESHOLD threshold_parameter {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a THRESHOLD gate\n";
#endif // FT_PARSER_DEBUG
// Using a global this way is really ugly, but I need to pass back
// the threshold value somehow.
fault_tree_textual_parser_threshold = *$2;
delete $2;
$$ = THRESHOLD;
} |
PAND {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an PAND gate\n";
#endif // FT_PARSER_DEBUG
$$ = PAND;
} |
SPARE {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a SPARE gate\n";
#endif // FT_PARSER_DEBUG
$$ = SPARE;
};
threshold_parameter:
MAXIMUM EQUALS natural_nonterminal {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$3;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a threshold max: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
$$ = new Threshold(*$3);
delete $3;
};
natural_nonterminal:
ZERO {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a zero: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
$$ = new Natural(*$1);
delete $1;
} |
NATURAL {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a natural number: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
$$ = new Natural(*$1);
delete $1;
};
identifier_list:
identifier_nonterminal {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an identifier: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
$$ = new list<string>;
$$->push_back(*$1);
delete $1;
} |
identifier_list identifier_nonterminal {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed multiple identifiers\n";
#endif // FT_PARSER_DEBUG
if ( find($1->begin(),$1->end(),*$2) != $1->end() )
{
string error = '"' + *$2 +
"\" is listed twice in this identifier list." +
" The second definition will be ignored.";
fault_tree_textual_parser_error(error);
delete $1;
}
else
{
$$ = $1;
$$->push_back(*$2);
}
delete $2;
};
constraint:
identifier_nonterminal constraint_type_and_parameter_specifier identifier_list SEMICOLON {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a constraint: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "Constraint \"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
if ($2 == SEQ)
{
Input_Sequence seq = Identifier_List_To_Input_Sequence(*$3);
if (parsed_fault_tree.Get_SEQ_Constraints().find(seq) !=
parsed_fault_tree.Get_SEQ_Constraints().end())
{
string error = "\"" + *$1 +
"\" has already been defined as \"" +
parsed_fault_tree.Get_SEQ_Description(seq) + "\". This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = seq.begin(), an_input_identifier = (*$3).begin();
an_input_event != seq.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Insert_SEQ_Constraint(seq);
parsed_fault_tree.Set_SEQ_Description(seq,*$1);
}
}
else if ($2 == FDEP)
{
// Using a global this way is really ugly, but I need to pass back
// the threshold value somehow.
Input_Sequence dependents = Identifier_List_To_Input_Sequence(*$3);
Functional_Dependency an_fdep;
an_fdep.Set_Trigger(fault_tree_textual_parser_trigger);
an_fdep.Set_Dependents(dependents);
if (parsed_fault_tree.Get_FDEP_Constraints().find(an_fdep) !=
parsed_fault_tree.Get_FDEP_Constraints().end())
{
string error = "\"" + *$1 +
"\" has already been defined as \"" +
parsed_fault_tree.Get_FDEP_Description(an_fdep) + "\". This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Input_Sequence::const_iterator an_input_event;
list<string>::const_iterator an_input_identifier;
for (an_input_event = dependents.begin(), an_input_identifier = (*$3).begin();
an_input_event != dependents.end();
an_input_event++, an_input_identifier++)
{
parsed_fault_tree.Set_Event_Description(*an_input_event,*an_input_identifier);
}
parsed_fault_tree.Insert_FDEP_Constraint(an_fdep);
parsed_fault_tree.Set_FDEP_Description(an_fdep,*$1);
}
}
else
{
fault_tree_textual_parser_error("Parser is broken: constraint_type_and_parameter_specifier returned unknown type");
}
}
delete $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
if ($2 == SEQ)
{
Input_Sequence seq = Identifier_List_To_Input_Sequence(*$3);
parsed_fault_tree.Remove_SEQ_Constraint(seq);
parsed_fault_tree.Remove_SEQ_Description(seq);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = seq.begin(); an_input_event != seq.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
}
else if ($2 == FDEP)
{
/* Using a global this way is really ugly, but I need to pass back
the trigger somehow. */
Input_Sequence dependents =
Identifier_List_To_Input_Sequence(*$3);
Functional_Dependency an_fdep;
an_fdep.Set_Trigger(fault_tree_textual_parser_trigger);
an_fdep.Set_Dependents(dependents);
parsed_fault_tree.Remove_FDEP_Constraint(an_fdep);
parsed_fault_tree.Remove_FDEP_Description(an_fdep);
Input_Sequence::const_iterator an_input_event;
for (an_input_event = dependents.begin(); an_input_event != dependents.end(); an_input_event++)
{
if (parsed_fault_tree.Event_Not_Referenced(*an_input_event))
parsed_fault_tree.Remove_Event_Description(*an_input_event);
}
}
else
assert(false);
}
delete $1;
delete $3;
};
constraint_type_and_parameter_specifier:
SEQ {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a SEQ\n";
#endif // FT_PARSER_DEBUG
$$ = SEQ;
} |
FDEP trigger_parameter {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an FDEP\n";
#endif // FT_PARSER_DEBUG
$$ = FDEP;
fault_tree_textual_parser_trigger = *$2;
delete $2;
};
trigger_parameter:
TRIGGER EQUALS identifier_nonterminal {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed an FDEP trigger: \"" + *$3 + "\"\n";
#endif // FT_PARSER_DEBUG
parsed_fault_tree.Set_Event_Description(Event_By_Identifier(*$3),*$3);
$$ = new Event(Event_By_Identifier(*$3));
delete $3;
}
{
if (parsed_fault_tree.Event_Not_Referenced(Event_By_Identifier(*$3)))
parsed_fault_tree.Remove_Event_Description(Event_By_Identifier(*$3));
delete $3;
};
basic_event:
identifier_nonterminal BE SEMICOLON {
#ifdef FT_PARSER_DEBUG
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a non-replicated basic event: \"" + *$1 + "\"\n";
#endif // FT_PARSER_DEBUG
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "Basic event \"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Insert_Basic_Event(basic_event,1);
parsed_fault_tree.Set_Event_Description(basic_event,*$1);
}
delete $1;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Remove_Basic_Event(basic_event);
if (parsed_fault_tree.Event_Not_Referenced(basic_event))
parsed_fault_tree.Remove_Event_Description(basic_event);
}
delete $1;
} |
identifier_nonterminal BE replication_parameter SEMICOLON {
#ifdef FT_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$3;
fault_tree_textual_parser_debug_string += "DFT_PARSER: Parsed a replicated basic event: \"" + *$1 +
"\", with a replication of: \"" + temp_string.str() + "\"\n";
#endif // FT_PARSER_DEBUG
// Check for duplicate definition
if (declarations.find(*$1) != declarations.end())
{
string error = "Basic event \"" + *$1 +
"\" has already been defined. This definition will be ignored.";
fault_tree_textual_parser_error(error);
}
else
{
declarations.insert(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Insert_Basic_Event(basic_event,*$3);
parsed_fault_tree.Set_Event_Description(basic_event,*$1);
}
delete $1;
delete $3;
}
{
if (!m_error_occurred)
{
declarations.erase(*$1);
Event basic_event = Event_By_Identifier(*$1);
parsed_fault_tree.Remove_Basic_Event(basic_event);
if (parsed_fault_tree.Event_Not_Referenced(basic_event))
parsed_fault_tree.Remove_Event_Description(basic_event);
}
delete $1;
};
replication_parameter:
REPLICATION EQUALS NATURAL {
$$ = new Replication(*$3);
delete $3;
};
//-----------------------------------------------------------------------------
%%
void fault_tree_textual_parser_parser_initialize(FILE* in_input_file)
{
fault_tree_textual_parser_scanner_initialize(in_input_file);
declarations.clear();
parsed_fault_tree.Clear();
identifiers_to_events.clear();
fault_tree_textual_parser_lineno = 1;
}
//-----------------------------------------------------------------------------
/*
* Given a identifier, determines if the identifier has been associated with
* an event. If it has, a copy of the event is returned. If it hasn't, then a
* new event is created.
*/
const Event Event_By_Identifier(const string &in_identifier)
{
Event event;
if (identifiers_to_events.find(in_identifier) != identifiers_to_events.end())
{
// Already encountered this identifier and created an event for it
event = (identifiers_to_events.find(in_identifier))->second;
}
else
{
// Add the new event and identifier
identifiers_to_events[in_identifier] = event;
}
return event;
}
// ---------------------------------------------------------------------------
/*
* Converts a list of identifiers into an input sequence by looking up the
* events associated with the identifiers
*/
const Input_Sequence Identifier_List_To_Input_Sequence(const list<string> &in_identifiers)
{
Input_Sequence inputs;
for (list<string>::const_iterator it = in_identifiers.begin();
it != in_identifiers.end();it++)
{
Event event = Event_By_Identifier(*it);
inputs.push_back(event);
}
return inputs;
}
// ---------------------------------------------------------------------------
bool Cycle_Already_Reported(const searchable_list<Event>& in_cycle, const set< searchable_list<Event> >& in_cycles_reported)
{
set< searchable_list<Event> >::const_iterator a_cycle_reported;
for(a_cycle_reported = in_cycles_reported.begin(); a_cycle_reported != in_cycles_reported.end(); a_cycle_reported++)
{
// If the lengths aren't the same, it's obviously not a match
if ((*a_cycle_reported).size() != in_cycle.size())
continue;
// Find the start of the cycle, if there is one
searchable_list<Event>::const_iterator start_of_cycle = (*a_cycle_reported).find(in_cycle.front());
if (start_of_cycle == (*a_cycle_reported).end())
continue;
// Now compare the cycles
bool cycles_are_the_same = true;
searchable_list<Event>::const_iterator compare_event = start_of_cycle;
searchable_list<Event>::const_iterator check_event;
for(check_event = in_cycle.begin(); check_event != in_cycle.end(); check_event++)
{
if (*check_event != *compare_event)
{
cycles_are_the_same = false;
break;
}
compare_event++;
if (compare_event == (*a_cycle_reported).end())
compare_event = (*a_cycle_reported).begin();
}
if (cycles_are_the_same)
return true;
}
return false;
}
// ---------------------------------------------------------------------------
void Check_For_Cycles_Recursive(const searchable_list<Event>& in_path, set< searchable_list<Event> >& in_cycles_reported)
{
if(parsed_fault_tree.Get_Gates().find(in_path.back()) == parsed_fault_tree.Get_Gates().end())
return;
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(in_path.back()).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(in_path.back()).end(); an_input++)
{
if (in_path.find(*an_input) != in_path.end())
{
searchable_list<Event> cycle;
searchable_list<Event>::const_iterator start = in_path.find(*an_input);
cycle.insert(cycle.end(),start,in_path.end());
if(!Cycle_Already_Reported(cycle, in_cycles_reported))
{
string error = "There is a cycle in the fault tree: " + parsed_fault_tree.Get_Event_Description(*an_input);
searchable_list<Event>::const_iterator a_cycle_event;
a_cycle_event = cycle.begin();
a_cycle_event++;
for(;a_cycle_event != cycle.end(); a_cycle_event++)
error += " -> " + parsed_fault_tree.Get_Event_Description(*a_cycle_event);
error += " -> " + parsed_fault_tree.Get_Event_Description(cycle.front());
fault_tree_textual_parser_error(error);
in_cycles_reported.insert(cycle);
}
continue;
}
searchable_list<Event> new_path = in_path;
new_path.push_back(*an_input);
Check_For_Cycles_Recursive(new_path, in_cycles_reported);
}
}
// ---------------------------------------------------------------------------
void Ensure_Valid_System_Event()
{
// Check the system level event
if (parsed_fault_tree.Get_Events().find(parsed_fault_tree.Get_System_Event()) ==
parsed_fault_tree.Get_Events().end())
{
string error = "The system level event named " +
parsed_fault_tree.Get_Event_Description(parsed_fault_tree.Get_System_Event()) +
" is not in the fault tree.";
fault_tree_textual_parser_error(error);
}
}
// ---------------------------------------------------------------------------
void Ensure_No_Cycles_In_Inputs()
{
set< searchable_list<Event> > cycles_already_reported;
set<Event>::const_iterator an_event;
for(an_event = parsed_fault_tree.Get_Events().begin(); an_event != parsed_fault_tree.Get_Events().end(); an_event++)
{
searchable_list<Event> path;
path.push_back(*an_event);
Check_For_Cycles_Recursive(path, cycles_already_reported);
}
}
// ---------------------------------------------------------------------------
void Ensure_Corresponding_References_And_Definitions()
{
const set<Event> events = parsed_fault_tree.Get_Events();
const set<Event> gates = parsed_fault_tree.Get_Gates();
set<Event>::const_iterator aGate;
for (aGate = gates.begin(); aGate != gates.end(); aGate++)
{
const Input_Sequence inputs = parsed_fault_tree.Get_Gate_Inputs(*aGate);
Input_Sequence::const_iterator anInput;
for (anInput = inputs.begin();anInput != inputs.end();anInput++)
{
if (events.find(*anInput) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*anInput) +
"\" is an input to gate \"" +
parsed_fault_tree.Get_Event_Description(*aGate) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
}
}
}
const set<Input_Sequence> seqs = parsed_fault_tree.Get_SEQ_Constraints();
set<Input_Sequence>::const_iterator aSeq;
for (aSeq = seqs.begin(); aSeq != seqs.end(); aSeq++)
{
const Input_Sequence inputs = *aSeq;
Input_Sequence::const_iterator anInput;
for (anInput = inputs.begin();anInput != inputs.end();anInput++)
{
if (events.find(*anInput) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*anInput) +
"\" is an input to sequence enforcer \"" +
parsed_fault_tree.Get_SEQ_Description(*aSeq) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
}
}
}
const set<Functional_Dependency> fdeps = parsed_fault_tree.Get_FDEP_Constraints();
set<Functional_Dependency>::const_iterator an_fdep;
for (an_fdep = fdeps.begin(); an_fdep != fdeps.end(); an_fdep++)
{
const Event trigger = (*an_fdep).Get_Trigger();
const Input_Sequence dependents = (*an_fdep).Get_Dependents();
if (events.find(trigger) == events.end())
{
string error = '"' + Get_Identifier_For_Event(trigger) +
"\" is a trigger for the functional dependency \"" +
parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
}
Input_Sequence::const_iterator aDependent;
for (aDependent = dependents.begin();aDependent != dependents.end();aDependent++)
{
if (events.find(*aDependent) == events.end())
{
string error = '"' + Get_Identifier_For_Event(*aDependent) +
"\" is a dependent input to the functional dependency \"" +
parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" but is not defined.";
fault_tree_textual_parser_error(error);
}
}
}
}
// ---------------------------------------------------------------------------
void Ensure_Spare_Gate_Inputs_Are_Basic_Events()
{
set<Event>::const_iterator a_spare_gate;
for(a_spare_gate = parsed_fault_tree.Get_Spare_Gates().begin(); a_spare_gate != parsed_fault_tree.Get_Spare_Gates().end(); a_spare_gate++)
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).end(); an_input++)
{
set<Event> gates_basic_event_is_input_to = parsed_fault_tree.Get_Gates_Event_Is_Input_To(*an_input);
set<Event>::const_iterator a_gate_input_to;
for(a_gate_input_to = gates_basic_event_is_input_to.begin(); a_gate_input_to != gates_basic_event_is_input_to.end(); a_gate_input_to++)
{
if(parsed_fault_tree.Get_Spare_Gates().find(*a_gate_input_to) == parsed_fault_tree.Get_Spare_Gates().end())
{
string error = "The input \"" + parsed_fault_tree.Get_Event_Description(*an_input) +
"\" for spare gate \"" + parsed_fault_tree.Get_Event_Description(*a_spare_gate) +
"\" is also input to the gate \"" + parsed_fault_tree.Get_Event_Description(*a_gate_input_to) +
"\" which is not a spare gate.";
fault_tree_textual_parser_error(error);
}
}
}
}
}
// ---------------------------------------------------------------------------
void Ensure_Spare_Gate_Inputs_Only_Input_To_Spare_Gates()
{
set<Event>::const_iterator a_spare_gate;
for(a_spare_gate = parsed_fault_tree.Get_Spare_Gates().begin(); a_spare_gate != parsed_fault_tree.Get_Spare_Gates().end(); a_spare_gate++)
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).begin(); an_input != parsed_fault_tree.Get_Gate_Inputs(*a_spare_gate).end(); an_input++)
{
if(parsed_fault_tree.Get_Basic_Events().find(*an_input) == parsed_fault_tree.Get_Basic_Events().end())
{
string error = "The input \"" + parsed_fault_tree.Get_Event_Description(*an_input) +
"\" for spare gate \"" + parsed_fault_tree.Get_Event_Description(*a_spare_gate) +
"\" is not a basic event.";
fault_tree_textual_parser_error(error);
}
}
}
}
// ---------------------------------------------------------------------------
void Ensure_FDEP_Trigger_Is_Not_Replicated()
{
set<Functional_Dependency>::const_iterator an_fdep;
for(an_fdep = parsed_fault_tree.Get_FDEP_Constraints().begin(); an_fdep != parsed_fault_tree.Get_FDEP_Constraints().end(); an_fdep++)
{
if(parsed_fault_tree.Get_Replication((*an_fdep).Get_Trigger()) > (Natural)1)
{
string error = "The trigger input \"" + parsed_fault_tree.Get_Event_Description((*an_fdep).Get_Trigger()) +
"\" for the functional dependency \"" + parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" has a replication greater than 1.";
fault_tree_textual_parser_error(error);
}
}
}
// ---------------------------------------------------------------------------
void Ensure_FDEP_Dependents_Are_Basic_Events()
{
set<Functional_Dependency>::const_iterator an_fdep;
for(an_fdep = parsed_fault_tree.Get_FDEP_Constraints().begin(); an_fdep != parsed_fault_tree.Get_FDEP_Constraints().end(); an_fdep++)
{
Input_Sequence::const_iterator a_dependent;
for(a_dependent = (*an_fdep).Get_Dependents().begin(); a_dependent != (*an_fdep).Get_Dependents().end(); a_dependent++)
{
if(parsed_fault_tree.Get_Basic_Events().find(*a_dependent) == parsed_fault_tree.Get_Basic_Events().end())
{
string error = "The depedent input \"" + parsed_fault_tree.Get_Event_Description(*a_dependent) +
"\" for the functional dependency \"" + parsed_fault_tree.Get_FDEP_Description(*an_fdep) +
"\" is not a basic event.";
fault_tree_textual_parser_error(error);
}
}
}
}
// ---------------------------------------------------------------------------
const string Get_Identifier_For_Event(const Event &in_event)
{
if (identifiers_to_events.inverse_find(in_event) != identifiers_to_events.end())
return identifiers_to_events.inverse_apply(in_event);
else
return NOT_FOUND;
}
// ---------------------------------------------------------------------------
void Ensure_Connectedness()
{
list< set< Event > > reachable_subsets;
// First compute the reachable events for each event
set<Event>::const_iterator an_event;
for(an_event = parsed_fault_tree.Get_Events().begin(); an_event != parsed_fault_tree.Get_Events().end(); an_event++)
{
set<Event> subgraph;
Compute_Reachable_Events(*an_event, subgraph);
reachable_subsets.push_back(subgraph);
}
// Now merge the subsets
list< set< Event > >::iterator a_subset;
a_subset = reachable_subsets.begin();
while(a_subset != reachable_subsets.end())
{
bool merged = false;
list< set< Event > >::iterator a_later_subset = a_subset;
a_later_subset++;
while(a_later_subset != reachable_subsets.end())
{
set<Event> intersection;
set_intersection(a_subset->begin(), a_subset->end(),
a_later_subset->begin(), a_later_subset->end(),
inserter(intersection,intersection.begin()));
if (intersection.size() != 0)
{
set_union(a_subset->begin(), a_subset->end(),
a_later_subset->begin(), a_later_subset->end(),
inserter(*a_subset,a_subset->begin()));
merged = true;
list< set< Event > >::iterator the_next_subset = a_later_subset;
the_next_subset++;
reachable_subsets.erase(a_later_subset);
a_later_subset = the_next_subset;
}
else
{
a_later_subset++;
}
}
if (merged)
{
merged = false;
}
else
{
a_subset++;
}
}
#if !NDEBUG
// Sanity check on our connectedness algorithm
for(a_subset = reachable_subsets.begin(); a_subset != reachable_subsets.end(); a_subset++)
{
list< set< Event > >::iterator a_later_subset = a_subset;
for(a_later_subset++; a_later_subset != reachable_subsets.end(); a_later_subset++)
{
set<Event> intersection;
set_intersection(a_subset->begin(), a_subset->end(),
a_later_subset->begin(), a_later_subset->end(),
inserter(intersection,intersection.begin()));
assert(intersection.size() == 0);
}
}
#endif // !NDEBUG
if (reachable_subsets.size() != 1)
fault_tree_textual_parser_error("The fault tree is not fully connected");
}
// ---------------------------------------------------------------------------
void Compute_Reachable_Events(const Event& in_event, set<Event>& in_subgraph)
{
if (in_subgraph.find(in_event) != in_subgraph.end())
return;
in_subgraph.insert(in_event);
// If it's a gate, recurse into the inputs
if(parsed_fault_tree.Get_Gates().find(in_event) != parsed_fault_tree.Get_Gates().end())
{
Input_Sequence::const_iterator an_input;
for(an_input = parsed_fault_tree.Get_Gate_Inputs(in_event).begin();
an_input != parsed_fault_tree.Get_Gate_Inputs(in_event).end();
an_input++)
{
Compute_Reachable_Events(*an_input, in_subgraph);
}
}
// Check to see if it's the input to a sequence enforcer
set<Input_Sequence>::const_iterator an_seq;
for(an_seq = parsed_fault_tree.Get_SEQ_Constraints().begin();
an_seq != parsed_fault_tree.Get_SEQ_Constraints().end();
an_seq++)
{
if (an_seq->find(in_event) != an_seq->end())
{
Input_Sequence::const_iterator an_input;
for(an_input = an_seq->begin(); an_input != an_seq->end(); an_input++)
{
Compute_Reachable_Events(*an_input,in_subgraph);
}
}
}
// Check to see if it's a dependent or trigger for a functional dependency
set<Functional_Dependency>::const_iterator a_functional_dependency;
for(a_functional_dependency = parsed_fault_tree.Get_FDEP_Constraints().begin();
a_functional_dependency != parsed_fault_tree.Get_FDEP_Constraints().end();
a_functional_dependency++)
{
if ((a_functional_dependency->Get_Trigger() == in_event) ||
(a_functional_dependency->Get_Dependents().find(in_event) !=
a_functional_dependency->Get_Dependents().end()))
{
Compute_Reachable_Events(a_functional_dependency->Get_Trigger(),in_subgraph);
Input_Sequence::const_iterator an_input;
for(an_input = a_functional_dependency->Get_Dependents().begin();
an_input != a_functional_dependency->Get_Dependents().end();
an_input++)
{
Compute_Reachable_Events(*an_input,in_subgraph);
}
}
}
}
// ---------------------------------------------------------------------------
/*
Sample main file
#include <string>
#include <cstdio>
#include "fault_tree_textual_parser/fault_tree_textual_parser_includes.h"
#include "y.tab.h"
extern FILE *fault_tree_textual_parser_in;
extern int fault_tree_textual_parser_parse();
extern void fault_tree_textual_parser_parser_initialize(FILE *in_input_file);
int main(int argc, char *argv[]) {
fault_tree_textual_parser_in = fopen(argv[1], "r");
fault_tree_textual_parser_parser_initialize(fault_tree_textual_parser_in);
fault_tree_textual_parser_parse();
// Not freed by yacc
free(fault_tree_textual_parser_ss);
fault_tree_textual_parser_ss = NULL;
free(fault_tree_textual_parser_vs);
fault_tree_textual_parser_vs = NULL;
fclose(fault_tree_textual_parser_in);
if (fault_tree_textual_parser_error_string != "")
printf("ERRORS!\n%s", fault_tree_textual_parser_error_string.c_str());
return 0;
}
*/