beagled/QueryStringParser.cs

   1 //
   2 // QueryStringParser.cs
   3 //
   4 // Copyright (C) 2004-2005 Novell, Inc.
   5 //
   6
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining a
   9 // copy of this software and associated documentation files (the "Software"),
  10 // to deal in the Software without restriction, including without limitation
  11 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
  12 // and/or sell copies of the Software, and to permit persons to whom the
  13 // Software is furnished to do so, subject to the following conditions:
  14 //
  15 // The above copyright notice and this permission notice shall be included in
  16 // all copies or substantial portions of the Software.
  17 //
  18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24 // DEALINGS IN THE SOFTWARE.
  25 //
  26
  27 using System;
  28 using System.Collections;
  29
  30 using Beagle.Util;
  31
  32 namespace Beagle.Daemon {
  33
  34         public class QueryStringParser {
  35
  36                 private QueryStringParser () { } // a static class
  37
  38                 // Returns an ICollection of QueryPart objects.
  39                 static public ICollection Parse (string query_string)
  40                 {
  41                         ArrayList token_list;
  42                         token_list = new ArrayList ();
  43
  44                         while (true) {
  45                                 Token token = ExtractToken (ref query_string);
  46                                 if (token == null)
  47                                         break;
  48                                 token_list.Add (token);
  49                         }
  50
  51                         return TokensToQueryParts (token_list);
  52                 }
  53
  54                 /////////////////////////////////////////////////////////
  55
  56                 private enum TokenType {
  57                         Unknown,
  58                         StandAlone,
  59                         Plus,
  60                         Minus,
  61                         Operator,
  62                         Meta
  63                 }
  64
  65                 private class Token {
  66                         public TokenType Type = TokenType.Unknown;
  67                         public string    Text;
  68                         public bool      IsQuoted;
  69                 }
  70
  71                 // Our tiny query language:
  72                 // prefix terms by + or - to require or prohibit them
  73                 //
  74
  75                 static private Token ExtractToken (ref string in_string)
  76                 {
  77                         if (in_string == null || in_string.Length == 0)
  78                                 return null;
  79
  80                         // Find the first non-whitespace character.
  81                         int first_pos = -1;
  82                         char first = ' ';
  83                         bool first_is_singleton = false;
  84                         for (int i = 0; i < in_string.Length; ++i) {
  85                                 first = in_string [i];
  86                                 if (! Char.IsWhiteSpace (first)) {
  87                                         first_pos = i;
  88                                         if (i == in_string.Length - 1)
  89                                                 first_is_singleton = true;
  90                                         break;
  91                                 }
  92                         }
  93
  94                         // This is only whitespace, and thus doesn't
  95                         // contain any tokens.
  96                         if (first_pos == -1)
  97                                 return null;
  98
  99                         Token token;
 100                         token = new Token ();
 101
 102                         // Based on the first character, decide what kind of a
 103                         // token this is.  Advance first_pos as necessary to
 104                         // skip special characters (like + and -)
 105                         switch (first) {
 106
 107                         case '+':
 108                                 if (first_is_singleton) {
 109                                         token.Type = TokenType.Meta;
 110                                         token.Text = "DanglingPlus";
 111                                         in_string = null;
 112                                         return token;
 113                                 }
 114
 115                                 token.Type = TokenType.Plus;
 116                                 ++first_pos;
 117                                 break;
 118
 119                         case '-':
 120                                 if (first_is_singleton) {
 121                                         token.Type = TokenType.Meta;
 122                                         token.Text = "DanglingMinus";
 123                                         in_string = null;
 124                                         return token;
 125                                 }
 126
 127                                 token.Type = TokenType.Minus;
 128                                 ++first_pos;
 129                                 break;
 130
 131                         case '"':
 132                                 if (first_is_singleton) {
 133                                         token.Type = TokenType.Meta;
 134                                         token.Text = "DanglingQuote";
 135                                         in_string = null;
 136                                         return token;
 137                                 }
 138
 139                                 token.Type = TokenType.StandAlone;
 140                                 token.IsQuoted = true;
 141                                 ++first_pos;
 142                                 break;
 143
 144                         default:
 145                                 token.Type = TokenType.StandAlone;
 146                                 break;
 147                         }
 148
 149                         char last;
 150                         last = token.IsQuoted ? '"' : ' ';
 151
 152                         int last_pos;
 153                         last_pos = in_string.IndexOf (last, first_pos);
 154
 155                         if (last_pos == -1) {
 156                                 // We don't worry about missing close-quotes.
 157                                 // FIXME: Maybe we should, or at least return a meta-token
 158                                 token.Text = in_string.Substring (first_pos);
 159                                 in_string = null;
 160                         } else {
 161                                 token.Text = in_string.Substring (first_pos, last_pos - first_pos);
 162                                 if (last_pos == in_string.Length-1)
 163                                         in_string = null;
 164                                 else
 165                                         in_string = in_string.Substring (last_pos+1);
 166                         }
 167
 168                         // Trap the OR operator
 169                         if (token.Type == TokenType.StandAlone && token.Text == "OR") {
 170                                 token.Type = TokenType.Operator;
 171                                 token.Text = "Or";
 172                         }
 173
 174                         // Ah, the dreaded "internal error".
 175                         if (token.Type == TokenType.Unknown)
 176                                 throw new Exception ("Internal QueryStringParser.ExtractToken Error");
 177
 178                         return token;
 179                 }
 180
 181                 static private ICollection TokensToQueryParts (ArrayList token_list)
 182                 {
 183                         ArrayList parts;
 184                         parts = new ArrayList ();
 185
 186                         int i = 0;
 187                         ArrayList or_list = null;
 188
 189                         while (i < token_list.Count) {
 190                                 Token token;
 191                                 token = token_list [i] as Token;
 192
 193                                 if (token.Type == TokenType.Meta) {
 194                                         ++i;
 195                                         continue;
 196                                 }
 197
 198                                 // Skip any extra operators
 199                                 if (token.Type == TokenType.Operator) {
 200                                         ++i;
 201                                         continue;
 202                                 }
 203
 204                                 // Assemble a part for this token.
 205
 206                                 QueryPart_Text text_part;
 207                                 text_part = new QueryPart_Text ();
 208                                 text_part.Text = token.Text;
 209
 210                                 if (token.Type == TokenType.Minus)
 211                                         text_part.Logic = QueryPartLogic.Prohibited;
 212                                 else
 213                                         text_part.Logic = QueryPartLogic.Required;
 214
 215                                 if (or_list != null) {
 216                                         or_list.Add (text_part);
 217                                         text_part = null;
 218                                 }
 219
 220                                 Token next_token = null;
 221                                 if (i < token_list.Count - 1)
 222                                         next_token = token_list [i+1] as Token;
 223
 224
 225                                 // If the next token is an or, start an or_list
 226                                 // (if we don't have one already) and skip
 227                                 // ahead to the next part.
 228                                 if (next_token != null
 229                                     && next_token.Type == TokenType.Operator
 230                                     && next_token.Text == "Or") {
 231                                         if (or_list == null) {
 232                                                 or_list = new ArrayList ();
 233                                                 or_list.Add (text_part);
 234                                         }
 235                                         i += 2;
 236                                         continue;
 237                                 }
 238
 239                                 // If we have a non-empty or-list going,
 240                                 // Create the appropriate QueryPart and add it
 241                                 // to the list.
 242                                 if (or_list != null) {
 243                                         QueryPart_Or or_part;
 244                                         or_part = new QueryPart_Or ();
 245                                         or_part.Logic = QueryPartLogic.Required;
 246                                         foreach (QueryPart sub_part in or_list)
 247                                                 or_part.Add (sub_part);
 248                                         parts.Add (or_part);
 249                                         or_list = null;
 250                                 }
 251
 252                                 // Add the next text part
 253                                 if (text_part != null)
 254                                         parts.Add (text_part);
 255
 256                                 ++i;
 257                         }
 258
 259                         // If we ended with an or_parts list, do the right thing.
 260                         if (or_list != null) {
 261                                 QueryPart_Or or_part;
 262                                 or_part = new QueryPart_Or ();
 263                                 or_part.Logic = QueryPartLogic.Required;
 264                                 foreach (QueryPart sub_part in or_list)
 265                                         or_part.Add (sub_part);
 266                         }
 267
 268                         return parts;
 269                 }
 270         }
 271
 272 }