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