src/utils/bamtools_filter_ruleparser.h

   1 // ***************************************************************************
   2 // bamtools_filter_ruleparser.h (c) 2010 Derek Barnett, Erik Garrison
   3 // Marth Lab, Department of Biology, Boston College
   4 // ---------------------------------------------------------------------------
   5 // Last modified: 19 November 2010
   6 // ---------------------------------------------------------------------------
   7 // Provides a compound rule parser for FilterEngine.
   8 // ***************************************************************************
   9
  10 #ifndef BAMTOOLS_FILTER_RULEPARSER_H
  11 #define BAMTOOLS_FILTER_RULEPARSER_H
  12
  13 #include <utils/bamtools_utilities.h>
  14 #include <queue>
  15 #include <stack>
  16 #include <string>
  17
  18 namespace BamTools {
  19
  20 // -------------------------------------------
  21 // char constants
  22
  23 const char LEFT_PARENTHESIS_CHAR  = '(';
  24 const char RIGHT_PARENTHESIS_CHAR = ')';
  25 const char AND_OPERATOR_CHAR      = '&';
  26 const char OR_OPERATOR_CHAR       = '|';
  27 const char NOT_OPERATOR_CHAR      = '!';
  28 const char SPACE_CHAR             = ' ';
  29
  30 // -------------------------------------------
  31 // RuleToken implementation
  32
  33 struct RuleToken {
  34
  35     // enums
  36     enum RuleTokenType { OPERAND = 0
  37                        , AND_OPERATOR
  38                        , OR_OPERATOR
  39                        , NOT_OPERATOR
  40                        , LEFT_PARENTHESIS
  41                        , RIGHT_PARENTHESIS
  42                        };
  43
  44     // data members
  45     RuleTokenType Type;
  46     std::string Value;
  47 };
  48
  49 inline int priority(const RuleToken& token) {
  50     switch ( token.Type ) {
  51         case ( RuleToken::NOT_OPERATOR )      : return 3;
  52         case ( RuleToken::AND_OPERATOR )      : return 2;
  53         case ( RuleToken::OR_OPERATOR  )      : return 1;
  54         case ( RuleToken::LEFT_PARENTHESIS )  : return 0;
  55         case ( RuleToken::RIGHT_PARENTHESIS ) : return 0;
  56         default:
  57             BAMTOOLS_ASSERT_UNREACHABLE;
  58             return -1;
  59     }
  60 }
  61
  62 inline bool isRightAssociative(const RuleToken& token) {
  63     return (token.Type == RuleToken::NOT_OPERATOR ||
  64             token.Type == RuleToken::LEFT_PARENTHESIS);
  65 }
  66
  67 inline bool isLeftAssociative(const RuleToken& token) {
  68     return !isRightAssociative(token);
  69 }
  70
  71 inline bool isLeftParenthesis(const RuleToken& token) {
  72     return ( token.Type == RuleToken::LEFT_PARENTHESIS );
  73 }
  74
  75 inline bool isRightParenthesis(const RuleToken& token) {
  76     return ( token.Type == RuleToken::RIGHT_PARENTHESIS );
  77 }
  78
  79 inline bool isOperand(const RuleToken& token) {
  80     return ( token.Type == RuleToken::OPERAND );
  81 }
  82
  83 inline bool isOperator(const RuleToken& token) {
  84     return ( token.Type == RuleToken::AND_OPERATOR ||
  85              token.Type == RuleToken::OR_OPERATOR  ||
  86              token.Type == RuleToken::NOT_OPERATOR);
  87 }
  88
  89 // -------------------------------------------
  90 // RuleParser implementation
  91
  92 class RuleParser {
  93
  94     // ctor & dtor
  95     public:
  96         RuleParser(const std::string& ruleString)
  97             : m_ruleString(ruleString)
  98         {
  99             // initialize char markers
 100             m_begin = (char*)m_ruleString.c_str();
 101             m_end   = m_begin + m_ruleString.length();
 102             ignoreQuotes();
 103         }
 104
 105         ~RuleParser(void) { }
 106
 107     // public interface
 108     public:
 109         void parse(void);
 110         std::queue<std::string> results(void) const { return m_ruleQueue; }
 111
 112     // internal methods
 113     private:
 114         char getNextChar(void);
 115         void ignoreQuotes(void);
 116         bool readToken(RuleToken& token);
 117         void skipSpaces(void);
 118
 119     // data members
 120     private:
 121         std::string m_ruleString;
 122         char* m_begin;
 123         char* m_current;
 124         char* m_end;
 125
 126         std::queue<std::string> m_ruleQueue;
 127         std::stack<RuleToken> m_operatorStack;
 128 };
 129
 130 inline
 131 char RuleParser::getNextChar(void) {
 132    if ( m_current == m_end ) return 0;
 133    return *m_current++;
 134 }
 135
 136 inline
 137 void RuleParser::ignoreQuotes(void) {
 138     if ( *m_begin == '\"' ) ++m_begin;
 139     if ( *m_end   == '\"' ) --m_end;
 140 }
 141
 142 inline
 143 void RuleParser::parse(void) {
 144
 145     // clear out any prior data
 146     while ( !m_ruleQueue.empty() )
 147         m_ruleQueue.pop();
 148
 149     // skip if no rule to parse
 150     if ( m_ruleString.empty() ) return;
 151
 152     // start at beginning of ruleString
 153     m_current = m_begin;
 154
 155     // iterate through tokens in rule string
 156     RuleToken token;
 157     while ( readToken(token) ) {
 158
 159         if ( token.Value.empty() ) break;
 160
 161         // if token is an operand
 162         if ( isOperand(token) )
 163             m_ruleQueue.push(token.Value);
 164
 165         // if token is an operator
 166         else if ( isOperator(token) ) {
 167
 168             // pop any operators at top of stack with higher priority
 169             while ( !m_operatorStack.empty() ) {
 170                 const RuleToken& opToken = m_operatorStack.top();
 171                 if ( (isLeftAssociative(token) && (priority(token) <= priority(opToken))) ||
 172                      (isRightAssociative(token) && (priority(token) < priority(opToken)))
 173                     )
 174                 {
 175                     m_ruleQueue.push(opToken.Value);
 176                     m_operatorStack.pop();
 177                 }
 178                 else break;
 179             }
 180
 181             // push current operator token onto stack
 182             m_operatorStack.push(token);
 183         }
 184
 185         // if token is left parenthesis
 186         else if ( isLeftParenthesis(token) )
 187             m_operatorStack.push(token);
 188
 189         // if token is right parenthesis
 190         else if ( isRightParenthesis(token) ) {
 191
 192             bool foundLeftParenthesis = false;
 193
 194             // push operators into rule queue until left parenthesis found
 195             while ( !m_operatorStack.empty() && !foundLeftParenthesis ) {
 196                 const RuleToken& opToken = m_operatorStack.top();
 197                 if ( !isLeftParenthesis(opToken) )
 198                     m_ruleQueue.push(opToken.Value);
 199                 else
 200                     foundLeftParenthesis = true;
 201                 m_operatorStack.pop();
 202             }
 203
 204             // no left parenthesis found, error
 205             BAMTOOLS_ASSERT_MESSAGE( foundLeftParenthesis, "ERROR: Mismatched parenthesis in rule string.1");
 206         }
 207
 208         // error: unknown operand
 209         else BAMTOOLS_ASSERT_UNREACHABLE;
 210     }
 211
 212     // while there are still operators on stack
 213     while ( !m_operatorStack.empty() ) {
 214         const RuleToken& token = m_operatorStack.top();
 215         BAMTOOLS_ASSERT_MESSAGE( (!isLeftParenthesis(token) && !isRightParenthesis(token)), "ERROR: Mismatched parenthesis in rule string.2");
 216         m_ruleQueue.push(token.Value);
 217         m_operatorStack.pop();
 218     }
 219 }
 220
 221 inline
 222 bool RuleParser::readToken(RuleToken& token) {
 223
 224     // skip any preceding whitespace
 225     skipSpaces();
 226     if ( m_current == m_end ) return false;
 227
 228     // clear out prior token value
 229     token.Value.clear();
 230
 231     // read chars while still in token
 232     char c = 1;
 233     bool keepReading = true;
 234     bool inOperandString = false;
 235     while ( keepReading && (c != 0) ) {
 236
 237       // get next char
 238       c = getNextChar();
 239       switch (c) {
 240
 241           // current char is '('
 242           case ( LEFT_PARENTHESIS_CHAR ) :
 243               token.Type = RuleToken::LEFT_PARENTHESIS;
 244               token.Value.append(1, LEFT_PARENTHESIS_CHAR);
 245               keepReading = false;
 246               break;
 247
 248           // current char is ')'
 249           case ( RIGHT_PARENTHESIS_CHAR ) :
 250               if ( inOperandString )
 251                   --m_current;
 252               else {
 253                   token.Type = RuleToken::RIGHT_PARENTHESIS;
 254                   token.Value.append(1, RIGHT_PARENTHESIS_CHAR);
 255               }
 256               keepReading = false;
 257               break;
 258
 259           // current char is '&'
 260           case ( AND_OPERATOR_CHAR ) :
 261               if ( inOperandString )
 262                   --m_current;
 263               else {
 264                   token.Type = RuleToken::AND_OPERATOR;
 265                   token.Value.append(1, AND_OPERATOR_CHAR);
 266               }
 267               keepReading = false;
 268               break;
 269
 270           // current char is '|'
 271           case ( OR_OPERATOR_CHAR ) :
 272               if ( inOperandString )
 273                   --m_current;
 274               else {
 275                   token.Type = RuleToken::OR_OPERATOR;
 276                   token.Value.append(1, OR_OPERATOR_CHAR);
 277               }
 278               keepReading = false;
 279               break;
 280
 281           // current char is '!'
 282           case ( NOT_OPERATOR_CHAR ) :
 283               token.Type = RuleToken::NOT_OPERATOR;
 284               token.Value.append(1, NOT_OPERATOR_CHAR);
 285               keepReading = false;
 286               break;
 287
 288           // current char is ' '
 289           case ( SPACE_CHAR ) :
 290               keepReading = false;
 291               break;
 292
 293           // current char is a true value token
 294           default:
 295               if ( c != 0 ) {
 296                   token.Type = RuleToken::OPERAND;
 297                   token.Value.append(1, c);
 298                   inOperandString = true;
 299                   keepReading = true;
 300               }
 301         }
 302     }
 303
 304     return true;
 305 }
 306
 307 inline
 308 void RuleParser::skipSpaces(void) {
 309     while ( m_current != m_end ) {
 310         const char c = *m_current;
 311         if ( c == ' ' || c == '\t' || c == '\r' || c == '\n')
 312             ++m_current;
 313         else break;
 314     }
 315 }
 316
 317 } // namespace BamTools
 318
 319 #endif // BAMTOOLS_FILTER_RULEPARSER_H