%{
#include "rbd_textual_parser/rbd_textual_parser_includes.h"
#include <string>
#include <sstream>
#include <cstdio>
#include <iostream>
#include "basic_types/searchable_list"
#include "basic_types/bijection.h"
using namespace std;
#ifdef RBD_PARSER_DEBUG
extern string rbd_textual_parser_debug_string;
#endif // RBD_PARSER_DEBUG
extern int rbd_textual_parser_lineno;
extern int rbd_textual_parser_lex();
extern void rbd_textual_parser_error(string s);
extern void rbd_textual_parser_scanner_initialize(FILE* in_input_file);
const Block Block_By_Identifier(const string &in_identifier);
const Block_Set Block_Identifier_List_To_Block_Set(const list<string> &in_identifiers);
const bool Cycle_Exists(searchable_list<Block>& path);
const bool Path_Exists(searchable_list<Block>& path, const Block& block);
const bool Component_Blocks_Already_Declared(const Block_Set &in_block_set);
void Ensure_No_Cycles_In_Inputs();
void Ensure_Proper_Structure();
const string Get_Identifier_For_Block(const Block &in_block);
RBD parsed_rbd;
bijection<string, Block> identifiers_to_blocks;
bijection<string, Component> identifiers_to_components;
const string Get_Identifier_For_Block(const Block &in_block);
string NOT_FOUND("<NOT FOUND>");
class Rule;
extern string chosen_rule;
extern map<string, Rule*> name_to_rule;
extern void Print_Strings(ostream &in_stream, Rule* in_rule);
%}
%union {
string* text;
Block* block;
int token;
list<string>* text_list;
Block_Set* block_set;
}
%token <text> BLOCK_IDENTIFIER
%token <text> COMPONENT_IDENTIFIER
%type <text> component_identifier_nonterminal
%type <text> block_identifier_nonterminal
%token COMPONENT
%token BLOCK
%token CONTAINS
%token OUTPUTSTO
%token SEMICOLON
%token EQUALS
%type <text_list> block_identifier_list
%token END_OF_FILE
%%
rbd:
component_def_list block_output_def_list eof {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed component defs. and block outputs.\n";
#endif // RBD_PARSER_DEBUG
};
eof:
END_OF_FILE {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed the end of the file.\n";
#endif // RBD_PARSER_DEBUG
// Print_Strings(cout, name_to_rule["rbd"]);
// This check is stronger than that in the specification.
// Ensure_Proper_Structure checks that every block has a path to the
// source and sink nodes, rather than there being *some* path to the
// source and sink node.
Ensure_Proper_Structure();
Ensure_No_Cycles_In_Inputs();
};
component_def_list:
component_def {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a component.\n";
#endif // RBD_PARSER_DEBUG
} |
component_def_list component_def {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed multiple components.\n";
#endif // RBD_PARSER_DEBUG
};
component_def:
COMPONENT component_identifier_nonterminal CONTAINS block_identifier_list SEMICOLON {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a component, identifier: \"" + *$2 + "\"\n";
#endif // RBD_PARSER_DEBUG
// Check for duplicate definition
if (identifiers_to_components.find(*$2) != identifiers_to_components.end())
{
string error = "Component \"" + *$2 +
"\" has already been defined. This definition will be ignored.";
rbd_textual_parser_error(error);
}
else
{
Block_Set block_set = Block_Identifier_List_To_Block_Set(*$4);
if (block_set.find(parsed_rbd.Get_Source_Block()) != block_set.end() ||
block_set.find(parsed_rbd.Get_Sink_Block()) != block_set.end())
{
string error = "Component \"" + *$2 +
"\" can not list the source or sink block as a reliability block." +
" This definition will be ignored.";
rbd_textual_parser_error(error);
}
else if (Component_Blocks_Already_Declared(block_set))
{
string error = "Component \"" + *$2 +
"\" uses one or more reliability blocks which " +
"have already been declared for another component. " +
"This definition will be ignored.";
rbd_textual_parser_error(error);
}
else
{
Component component;
identifiers_to_components[*$2] = component;
parsed_rbd.Insert_Component(component);
parsed_rbd.Set_Component_Description(component,*$2);
parsed_rbd.Set_Phys_To_Log_Map(component,block_set);
}
}
delete $2;
delete $4;
}
{
if (!m_error_occurred)
{
Component component = identifiers_to_components[*$2];
identifiers_to_components.erase(*$2);
parsed_rbd.Remove_Component(component);
parsed_rbd.Remove_Component_Description(component);
parsed_rbd.Remove_Phys_To_Log_Map(component);
for (list<string>::const_iterator it = $4->begin(); it != $4->end(); it++)
if (!parsed_rbd.Block_Is_Referenced(Block_By_Identifier(*it)))
identifiers_to_blocks.erase(*it);
}
delete $2;
delete $4;
};
block_output_def_list:
source_block_output_def nonsource_block_output_def_list;
nonsource_block_output_def_list:
block_output_def {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block's output.\n";
#endif // RBD_PARSER_DEBUG
} |
block_output_def nonsource_block_output_def_list {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed multiple blocks' outputs.\n";
#endif // RBD_PARSER_DEBUG
};
source_block_output_def:
BLOCK "source" OUTPUTSTO block_identifier_list SEMICOLON {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed the source block's output, identifier: \"source\"\n";
#endif // RBD_PARSER_DEBUG
Block_Set output_blocks = Block_Identifier_List_To_Block_Set(*$4);
parsed_rbd.Set_Block_Outputs(parsed_rbd.Get_Source_Block(),output_blocks);
parsed_rbd.Set_Block_Description(parsed_rbd.Get_Source_Block(),"source");
delete $4;
}
{
parsed_rbd.Remove_Block_Outputs(parsed_rbd.Get_Source_Block());
parsed_rbd.Remove_Block_Description(parsed_rbd.Get_Source_Block());
for (list<string>::const_iterator it = $4->begin(); it != $4->end(); it++)
if (!parsed_rbd.Block_Is_Referenced(Block_By_Identifier(*it)))
identifiers_to_blocks.erase(*it);
delete $4;
};
block_output_def:
BLOCK block_identifier_nonterminal OUTPUTSTO block_identifier_list SEMICOLON {
#ifdef RBD_PARSER_DEBUG
if ($2 != NULL)
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block's output, identifier: \"" + Get_Identifier_For_Block(*$2) + "\"\n";
else
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed an invalid block's output.\n";
#endif // RBD_PARSER_DEBUG
Block block = Block_By_Identifier(*$2);
// For symmetry breaking during RBD generation. We have to be careful here
// because the generator will generate b9 before b10, but b9 > b10. This
// code assumes "b#" block identifiers
bool out_of_order = false;
for (Block_Set::iterator it = parsed_rbd.Get_Reliability_Blocks().begin();
it != parsed_rbd.Get_Reliability_Blocks().end(); it++) {
if (!parsed_rbd.Block_Has_Outputs(*it))
continue;
string block_name = Get_Identifier_For_Block(*it);
istringstream last_number_string(block_name.substr(1,block_name.size()) +
" " + $2->substr(1,$2->size()));
int block_number, new_block_number;
last_number_string >> block_number >> new_block_number;
if (block_number > new_block_number) {
out_of_order = true;
break;
}
}
if (out_of_order) {
string error = "Block output definition \"" + *$2 +
"\" is not in order. This definition will be ignored.";
rbd_textual_parser_error(error);
}
else if (*$2 == "sink")
{
string error = (string)"A sink block can not have output blocks. " +
"This definition will be ignored.";
rbd_textual_parser_error(error);
}
else if (parsed_rbd.Block_Has_Outputs(block))
{
string error = "Outputs for block \"" + *$2 +
"\" have already been defined. This definition will be ignored.";
rbd_textual_parser_error(error);
}
else if (*$2 != "source" && *$2 != "sink" &&
!parsed_rbd.Containing_Component_Exists(block))
{
string error = "There is no component for block \"" + *$2 +
"\". This output block will be ignored.";
rbd_textual_parser_error(error);
}
else
{
if (*$2 != "source" && *$2 != "sink")
parsed_rbd.Insert_Reliability_Block(block);
Block_Set output_blocks = Block_Identifier_List_To_Block_Set(*$4);
parsed_rbd.Set_Block_Outputs(block,output_blocks);
parsed_rbd.Set_Block_Description(block,*$2);
}
delete $2;
delete $4;
}
{
Block block = Block_By_Identifier(*$2);
if (!m_error_occurred)
{
if (*$2 != "source" && *$2 != "sink")
parsed_rbd.Remove_Reliability_Block(block);
parsed_rbd.Remove_Block_Outputs(block);
parsed_rbd.Remove_Block_Description(block);
}
if (!parsed_rbd.Block_Is_Referenced(block))
identifiers_to_blocks.erase(*$2);
for (list<string>::const_iterator it = $4->begin(); it != $4->end(); it++)
if (!parsed_rbd.Block_Is_Referenced(Block_By_Identifier(*it)))
identifiers_to_blocks.erase(*it);
delete $2;
delete $4;
};
component_identifier_nonterminal:
COMPONENT_IDENTIFIER {
#ifdef RBD_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a component identifier: \"" + temp_string.str() + "\"\n";
#endif // RBD_PARSER_DEBUG
$$ = new string(*$1);
delete $1;
};
block_identifier_list:
block_identifier_nonterminal {
#ifdef RBD_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block identifier\n";
#endif // RBD_PARSER_DEBUG
$$ = new list<string>;
$$->push_back(*$1);
delete $1;
} |
block_identifier_list block_identifier_nonterminal {
#ifdef RBD_PARSER_DEBUG
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed multiple block identifiers\n";
#endif // RBD_PARSER_DEBUG
$$ = $1;
// For symmetry breaking during RBD generation. We have to be careful here
// because the generator will generate b9 before b10, but b9 > b10. This
// code assumes "b#" block identifiers
if ($$->size() > 0) {
istringstream last_number_string($$->back().substr(1,$$->back().size()) +
" " + $2->substr(1,$2->size()));
int last_number, new_number;
last_number_string >> last_number >> new_number;
if (last_number > new_number) {
string error = "Block \"" + *$2 + "\" is not in order.";
rbd_textual_parser_error(error);
}
}
bool already_listed = false;
for (list<string>::const_iterator it = $$->begin(); it != $$->end(); it++)
if (*it == *$2) {
already_listed = true;
break;
}
if (already_listed) {
string error = "Block \"" + *$2 + "\" has already been listed. This reference will be ignored.";
rbd_textual_parser_error(error);
} else
$$->push_back(*$2);
delete $2;
};
block_identifier_nonterminal:
BLOCK_IDENTIFIER {
#ifdef RBD_PARSER_DEBUG
ostringstream temp_string;
temp_string << *$1;
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block identifier: \"" + temp_string.str() + "\"\n";
#endif // RBD_PARSER_DEBUG
$$ = new string(*$1);
delete $1;
} |
"source" {
#ifdef RBD_PARSER_DEBUG
ostringstream temp_string;
temp_string << "source";
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block identifier: \"" + temp_string.str() + "\"\n";
#endif // RBD_PARSER_DEBUG
$$ = new string("source");
} |
"sink" {
#ifdef RBD_PARSER_DEBUG
ostringstream temp_string;
temp_string << "sink";
rbd_textual_parser_debug_string += "RBD_PARSER: Parsed a block identifier: \"" + temp_string.str() + "\"\n";
#endif // RBD_PARSER_DEBUG
$$ = new string("sink");
};
/* ----------------------------------------------------------------- */
%%
void rbd_textual_parser_parser_initialize(FILE *in_input_file)
{
rbd_textual_parser_scanner_initialize(in_input_file);
parsed_rbd.Clear();
identifiers_to_blocks.clear();
rbd_textual_parser_lineno = 1;
}
/*
* Given a identifier, determines if the identifier has been associated with
* an block. If it has, a copy of the block is returned. If it hasn't, then a
* new block is created.
*/
const Block Block_By_Identifier(const string &in_identifier)
{
// So at this point in_identifier is not a source or sink
Block block;
if (identifiers_to_blocks.find(in_identifier) != identifiers_to_blocks.end())
{
// Already encountered this identifier and created a block for it
block = (identifiers_to_blocks.find(in_identifier))->second;
}
else
{
if (in_identifier == "source")
block = parsed_rbd.Get_Source_Block();
if (in_identifier == "sink")
block = parsed_rbd.Get_Sink_Block();
identifiers_to_blocks[in_identifier] = block;
}
return block;
}
/*
* Converts a list of identifiers into a set of blocks by looking up the
* events associated with the identifiers
*/
const Block_Set Block_Identifier_List_To_Block_Set(const list<string> &in_identifiers)
{
Block_Set block_set;
for (list<string>::const_iterator it = in_identifiers.begin();
it != in_identifiers.end();it++)
{
Block block = Block_By_Identifier(*it);
block_set.insert(block);
}
return block_set;
}
const bool Component_Blocks_Already_Declared(const Block_Set &in_block_set)
{
for (set<Component>::const_iterator cit =
parsed_rbd.Get_Components().begin();
cit != parsed_rbd.Get_Components().end(); cit++)
for (Block_Set::const_iterator bit = in_block_set.begin();
bit != in_block_set.end(); bit++)
if (parsed_rbd.Get_Phys_To_Log_Map(*cit).find(*bit) !=
parsed_rbd.Get_Phys_To_Log_Map(*cit).end())
return true;
return false;
}
// in_path should contain the starting block at the beginning of the search.
// At the end of the search it will contain a path containing a cycle,
// excluding the last repeated block of the cycle
const bool Cycle_Exists(searchable_list<Block>& in_path)
{
Block last_block = in_path.back();
Dests_Map dests = parsed_rbd.Get_Dests_Map();
if (dests.find(last_block) == dests.end())
return false;
Block_Set outputs = parsed_rbd.Get_Dests_Map()(last_block);
for (Block_Set::const_iterator it = outputs.begin(); it != outputs.end();
it++)
{
if (in_path.find(*it) != in_path.end())
return true;
in_path.push_back(*it);
if (Cycle_Exists(in_path))
return true;
in_path.pop_back();
}
return false;
}
void Ensure_No_Cycles_In_Inputs()
{
// Check source
{
searchable_list<Block> path;
path.push_back(parsed_rbd.Get_Source_Block());
if (Cycle_Exists(path))
{
string error = "\"source\" is input to itself.";
rbd_textual_parser_error(error);
}
}
for (Block_Set::iterator it = parsed_rbd.Get_Reliability_Blocks().begin();
it != parsed_rbd.Get_Reliability_Blocks().end(); it++)
{
searchable_list<Block> path;
path.push_back(*it);
if (Cycle_Exists(path))
{
string error = '"' + Get_Identifier_For_Block(*it) +
"\" is input to itself.";
rbd_textual_parser_error(error);
}
}
}
// in_path should contain the starting block at the beginning of the search.
// At the end of the search it will contain the path to the block, excluding
// the block itself.
const bool Path_Exists(searchable_list<Block>& in_path, const Block &block)
{
Block last_block = in_path.back();
Dests_Map dests = parsed_rbd.Get_Dests_Map();
if (dests.find(last_block) == dests.end())
return false;
Block_Set outputs = parsed_rbd.Get_Dests_Map()(last_block);
for (Block_Set::const_iterator it = outputs.begin(); it != outputs.end();
it++)
{
// Don't let cycles crash us
if (in_path.find(*it) != in_path.end())
continue;
if (*it == block)
return true;
in_path.push_back(*it);
if (Path_Exists(in_path, block))
return true;
in_path.pop_back();
}
return false;
}
void Ensure_Proper_Structure()
{
// Check that blocks referenced in component definitions are defined
for (set<Component>::const_iterator cit =
parsed_rbd.Get_Components().begin();
cit != parsed_rbd.Get_Components().end(); cit++)
for (Block_Set::const_iterator bit =
parsed_rbd.Get_Phys_To_Log_Map(*cit).begin();
bit != parsed_rbd.Get_Phys_To_Log_Map(*cit).end(); bit++)
if (parsed_rbd.Get_Reliability_Blocks().find(*bit) ==
parsed_rbd.Get_Reliability_Blocks().end())
{
string error = "The block \"" + Get_Identifier_For_Block(*bit) +
"\" is referenced by a component definition but is not defined.";
rbd_textual_parser_error(error);
}
// Check that blocks referenced in block definitions are defined
{
for (Block_Set::const_iterator it2 =
parsed_rbd.Get_Block_Outputs(parsed_rbd.Get_Source_Block()).begin();
it2 != parsed_rbd.Get_Block_Outputs(parsed_rbd.Get_Source_Block()).end(); it2++)
if (*it2 != parsed_rbd.Get_Sink_Block() &&
parsed_rbd.Get_Reliability_Blocks().find(*it2) ==
parsed_rbd.Get_Reliability_Blocks().end())
{
string error = "The block \"" + Get_Identifier_For_Block(*it2) +
"\" is referenced by a block definition but is not defined.";
rbd_textual_parser_error(error);
}
}
for (Block_Set::const_iterator it1 =
parsed_rbd.Get_Reliability_Blocks().begin();
it1 != parsed_rbd.Get_Reliability_Blocks().end(); it1++)
for (Block_Set::const_iterator it2 =
parsed_rbd.Get_Block_Outputs(*it1).begin();
it2 != parsed_rbd.Get_Block_Outputs(*it1).end(); it2++)
if (*it2 != parsed_rbd.Get_Sink_Block() &&
parsed_rbd.Get_Reliability_Blocks().find(*it2) ==
parsed_rbd.Get_Reliability_Blocks().end())
{
string error = "The block \"" + Get_Identifier_For_Block(*it2) +
"\" is referenced by a block definition but is not defined.";
rbd_textual_parser_error(error);
}
for (Block_Set::iterator it = parsed_rbd.Get_Reliability_Blocks().begin();
it != parsed_rbd.Get_Reliability_Blocks().end(); it++)
{
// Check source to block
{
searchable_list<Block> path;
path.push_back(parsed_rbd.Get_Source_Block());
if (!Path_Exists(path, *it))
{
string error = "There is no path from the source block to \"" +
Get_Identifier_For_Block(*it) + "\".";
rbd_textual_parser_error(error);
}
}
// Check block to sink
{
searchable_list<Block> path;
path.push_back(*it);
if (!Path_Exists(path, parsed_rbd.Get_Sink_Block()))
{
string error = "There is no path \"" +
Get_Identifier_For_Block(*it) + "\" to the sink block.";
rbd_textual_parser_error(error);
}
}
}
}
const string Get_Identifier_For_Block(const Block &in_block)
{
if (identifiers_to_blocks.inverse_find(in_block) != identifiers_to_blocks.end())
{
return identifiers_to_blocks.inverse_apply(in_block);
}
else
{
return NOT_FOUND;
}
}
/*
Sample main file
#include <string>
#include <cstdio>
#include "rbd_textual_parser/rbd_textual_parser_includes.h"
#include "y.tab.h"
extern FILE *rbd_textual_parser_in;
extern int rbd_textual_parser_parse();
extern void rbd_textual_parser_parser_initialize(FILE* in_input_file);
int main(int argc, char *argv[]) {
rbd_textual_parser_in = fopen(argv[1], "r");
rbd_textual_parser_parser_initialize(rbd_textual_parser_in);
rbd_textual_parser_parse();
// Not freed by yacc
free(rbd_textual_parser_ss);
rbd_textual_parser_ss = NULL;
free(rbd_textual_parser_vs);
rbd_textual_parser_vs = NULL;
fclose(rbd_textual_parser_in);
if (rbd_textual_parser_error_string != "")
printf("ERRORS!\n%s", rbd_textual_parser_error_string.c_str());
return 0;
}
*/