1#ifdef HAVE_CONFIG_H 2#include "config.h" 3#endif 4 5#include <stdlib.h> 6#include <string.h> 7#include <stdio.h> 8 9#include "err.h" 10#include "query.h" 11 12static const query_field_t* find_field(const char* name, 13 const query_field_t* fields); 14static int arith_query(query_node_t* query, void* target); 15static int string_query(query_node_t* query, void* target); 16 17static query_node_t* match_specifier(const char* query, 18 const char** cursor, 19 const query_field_t* fields); 20static query_node_t* group_match(const char* query, 21 const char** cursor, 22 const query_field_t* fields); 23static query_node_t* single_match(const char* query, 24 const char** cursor, 25 const query_field_t* fields); 26static int get_field_name(const char** pcursor, 27 const char* query, 28 char* name, 29 int len); 30static int get_opcode(const char** pcursor, 31 const char* query, 32 char* name, 33 int len); 34static query_node_t* match_number(const query_field_t* field, 35 char not, char opcode, 36 const char** pcursor, 37 const char* query); 38static query_node_t* match_string(const query_field_t* field, 39 char not, char opcode, 40 const char** pcursor, 41 const char* query); 42char* query_unescape(const char* query); 43 44query_node_t* query_build(const char* query, const query_field_t* fields) 45{ 46 query_node_t* left = 0; 47 char* raw = query_unescape(query); 48 const char* cursor = raw; 49 query_node_t* right = 0; 50 query_type_t join; 51 52 if(0 == (left = match_specifier(query, &cursor, fields))) 53 goto error; 54 55 while(*cursor) 56 { 57 query_node_t* con; 58 59 switch(*cursor) 60 { 61 case '+': 62 case ' ': join = qot_and; break; 63 case ',': join = qot_or; break; 64 default: 65 DPRINTF(E_LOG,L_QRY, "Illegal character '%c' (0%o) at index %d: %s\n", 66 *cursor, *cursor, cursor - raw, raw); 67 goto error; 68 } 69 70 cursor++; 71 72 if(0 == (right = match_specifier(raw, &cursor, fields))) 73 goto error; 74 75 con = (query_node_t*) calloc(1, sizeof(*con)); 76 con->type = join; 77 con->left.node = left; 78 con->right.node = right; 79 80 left = con; 81 } 82 83 if(query != raw) 84 free(raw); 85 86 return left; 87 88 error: 89 if(left != 0) 90 query_free(left); 91 if(raw != query) 92 free(raw); 93 94 return NULL; 95} 96 97static query_node_t* match_specifier(const char* query, 98 const char** cursor, 99 const query_field_t* fields) 100{ 101 switch(**cursor) 102 { 103 case '\'': return single_match(query, cursor, fields); 104 case '(': return group_match(query, cursor, fields); 105 } 106 107 DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n", 108 **cursor, **cursor, *cursor - query, query); 109 return NULL; 110} 111 112static query_node_t* group_match(const char* query, 113 const char** pcursor, 114 const query_field_t* fields) 115{ 116 query_node_t* left = 0; 117 query_node_t* right = 0; 118 query_node_t* join = 0; 119 query_type_t opcode; 120 const char* cursor = *pcursor; 121 122 /* skip the opening ')' */ 123 ++cursor; 124 125 if(0 == (left = single_match(query, &cursor, fields))) 126 return NULL; 127 128 switch(*cursor) 129 { 130 case '+': 131 case ' ': 132 opcode = qot_and; 133 break; 134 135 case ',': 136 opcode = qot_or; 137 break; 138 139 default: 140 DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n", 141 *cursor, *cursor, cursor - query, query); 142 goto error; 143 } 144 145 if(0 == (right = single_match(query, &cursor, fields))) 146 goto error; 147 148 if(*cursor != ')') 149 { 150 DPRINTF(E_LOG,L_QRY,"Illegal character '%c' (0%o) at index %d: %s\n", 151 *cursor, *cursor, cursor - query, query); 152 goto error; 153 } 154 155 *pcursor = cursor + 1; 156 157 join = (query_node_t*) calloc(1, sizeof(*join)); 158 join->type = opcode; 159 join->left.node = left; 160 join->right.node = right; 161 162 return join; 163 164 error: 165 if(0 != left) 166 query_free(left); 167 if(0 != right) 168 query_free(right); 169 170 return 0; 171} 172 173static query_node_t* single_match(const char* query, 174 const char** pcursor, 175 const query_field_t* fields) 176{ 177 char fname[64]; 178 const query_field_t* field; 179 char not = 0; 180 char op = 0; 181 query_node_t* node = 0; 182 183 /* skip opening ' */ 184 (*pcursor)++; 185 186 /* collect the field name */ 187 if(!get_field_name(pcursor, query, fname, sizeof(fname))) 188 return NULL; 189 190 if(**pcursor == '!') 191 { 192 not = '!'; 193 ++(*pcursor); 194 } 195 196 if(strchr(":+-", **pcursor)) 197 { 198 op = **pcursor; 199 ++(*pcursor); 200 } 201 else 202 { 203 DPRINTF(E_LOG,L_QRY,"Illegal Operator: %c (0%o) at index %d: %s\n", 204 **pcursor, **pcursor, *pcursor - query, query); 205 return NULL; 206 } 207 208 if(0 == (field = find_field(fname, fields))) 209 { 210 DPRINTF(E_LOG,L_QRY,"Unknown field: %s\n", fname); 211 return NULL; 212 } 213 214 switch(field->type) 215 { 216 case qft_i32: 217 case qft_i64: 218 node = match_number(field, not, op, pcursor, query); 219 break; 220 221 case qft_string: 222 node = match_string(field, not, op, pcursor, query); 223 break; 224 225 default: 226 DPRINTF(E_LOG,L_QRY,"Invalid field type: %d\n", field->type); 227 break; 228 } 229 230 if(**pcursor != '\'') 231 { 232 DPRINTF(E_LOG,L_QRY,"Illegal Character: %c (0%o) index %d: %s\n", 233 **pcursor, **pcursor, *pcursor - query, query); 234 query_free(node); 235 node = 0; 236 } 237 else 238 ++(*pcursor); 239 240 return node; 241} 242 243static int get_field_name(const char** pcursor, 244 const char* query, 245 char* name, 246 int len) 247{ 248 const char* cursor = *pcursor; 249 250 if(!isalpha(*cursor)) 251 return 0; 252 253 while(isalpha(*cursor) || *cursor == '.') 254 { 255 if(--len <= 0) 256 { 257 DPRINTF(E_LOG,L_QRY,"token length exceeded at offset %d: %s\n", 258 cursor - query, query); 259 return 0; 260 } 261 262 *name++ = *cursor++; 263 } 264 265 *pcursor = cursor; 266 267 *name = 0; 268 269 return 1; 270} 271 272static query_node_t* match_number(const query_field_t* field, 273 char not, char opcode, 274 const char** pcursor, 275 const char* query) 276{ 277 query_node_t* node = (query_node_t*) calloc(1, sizeof(*node)); 278 279 switch(opcode) 280 { 281 case ':': 282 node->type = not ? qot_ne : qot_eq; 283 break; 284 case '+': 285 case ' ': 286 node->type = not ? qot_le : qot_gt; 287 break; 288 case '-': 289 node->type = not ? qot_ge : qot_lt; 290 break; 291 } 292 293 node->left.field = field; 294 295 switch(field->type) 296 { 297 case qft_i32: 298 node->right.i32 = strtol(*pcursor, (char**) pcursor, 10); 299 break; 300 case qft_i64: 301 node->right.i64 = strtoll(*pcursor, (char**) pcursor, 10); 302 break; 303 } 304 305 if(**pcursor != '\'') 306 { 307 DPRINTF(E_LOG,L_QRY,"Illegal char in number '%c' (0%o) at index %d: %s\n", 308 **pcursor, **pcursor, *pcursor - query, query); 309 free(node); 310 return 0; 311 } 312 313 return node; 314} 315 316static query_node_t* match_string(const query_field_t* field, 317 char not, char opcode, 318 const char** pcursor, 319 const char* query) 320{ 321 char match[64]; 322 char* dst = match; 323 int left = sizeof(match); 324 const char* cursor = *pcursor; 325 query_type_t op = qot_is; 326 query_node_t* node; 327 328 if(opcode != ':') 329 { 330 DPRINTF(E_LOG,L_QRY,"Illegal operation on string: %c at index %d: %s\n", 331 opcode, cursor - query - 1); 332 return NULL; 333 } 334 335 if(*cursor == '*') 336 { 337 op = qot_ends; 338 cursor++; 339 } 340 341 while(*cursor && *cursor != '\'') 342 { 343 if(--left == 0) 344 { 345 DPRINTF(E_LOG,L_QRY,"string too long at index %d: %s\n", 346 cursor - query, query); 347 return NULL; 348 } 349 350 if(*cursor == '\\') 351 { 352 switch(*++cursor) 353 { 354 case '*': 355 case '\'': 356 case '\\': 357 *dst++ = *cursor++; 358 break; 359 default: 360 DPRINTF(E_LOG,L_QRY,"Illegal escape: %c (0%o) at index %d: %s\n", 361 *cursor, *cursor, cursor - query, query); 362 return NULL; 363 } 364 } 365 else 366 *dst++ = *cursor++; 367 } 368 369 if(dst[-1] == '*') 370 { 371 op = (op == qot_is) ? qot_begins : qot_contains; 372 dst--; 373 } 374 375 *dst = 0; 376 377 node = (query_node_t*) calloc(1, sizeof(*node)); 378 node->type = op; 379 node->left.field = field; 380 node->right.str = strdup(match); 381 382 *pcursor = cursor; 383 384 return node; 385} 386 387int query_test(query_node_t* query, void* target) 388{ 389 switch(query->type) 390 { 391 /* conjunction */ 392 case qot_and: 393 return (query_test(query->left.node, target) && 394 query_test(query->right.node, target)); 395 396 case qot_or: 397 return (query_test(query->left.node, target) || 398 query_test(query->right.node, target)); 399 400 /* negation */ 401 case qot_not: 402 return !query_test(query->left.node, target); 403 404 /* arithmetic */ 405 case qot_eq: 406 case qot_ne: 407 case qot_le: 408 case qot_lt: 409 case qot_ge: 410 case qot_gt: 411 return arith_query(query, target); 412 413 /* string */ 414 case qot_is: 415 case qot_begins: 416 case qot_ends: 417 case qot_contains: 418 return string_query(query, target); 419 break; 420 421 /* constants */ 422 case qot_const: 423 return query->left.constant; 424 } 425} 426 427void query_free(query_node_t* query) 428{ 429 if(0 != query) 430 { 431 switch(query->type) 432 { 433 /* conjunction */ 434 case qot_and: 435 case qot_or: 436 query_free(query->left.node); 437 query_free(query->right.node); 438 break; 439 440 /* negation */ 441 case qot_not: 442 query_free(query->left.node); 443 break; 444 445 /* arithmetic */ 446 case qot_eq: 447 case qot_ne: 448 case qot_le: 449 case qot_lt: 450 case qot_ge: 451 case qot_gt: 452 break; 453 454 /* string */ 455 case qot_is: 456 case qot_begins: 457 case qot_ends: 458 case qot_contains: 459 free(query->right.str); 460 break; 461 462 /* constants */ 463 case qot_const: 464 break; 465 466 default: 467 DPRINTF(E_LOG,L_QRY,"Illegal query type: %d\n", query->type); 468 break; 469 } 470 471 free(query); 472 } 473} 474 475static const query_field_t* find_field(const char* name, const query_field_t* fields) 476{ 477 while(fields->name && strcasecmp(fields->name, name)) 478 fields++; 479 480 if(fields->name == 0) 481 { 482 DPRINTF(E_LOG,L_QRY,"Illegal query field: %s\n", name); 483 return NULL; 484 } 485 486 return fields; 487} 488 489static int arith_query(query_node_t* query, void* target) 490{ 491 const query_field_t* field = query->left.field; 492 493 switch(field->type) 494 { 495 case qft_i32: 496 { 497 int tv = * (int*) ((size_t) target + field->offset); 498 499 tv -= query->right.i32; 500 501 switch(query->type) 502 { 503 case qot_eq: return tv == 0; 504 case qot_ne: return tv != 0; 505 case qot_le: return tv <= 0; 506 case qot_lt: return tv < 0; 507 case qot_ge: return tv >= 0; 508 case qot_gt: return tv > 0; 509 default: 510 DPRINTF(E_LOG,L_QRY,"illegal query type: %d\n", query->type); 511 break; 512 } 513 } 514 break; 515 516 case qft_i64: 517 { 518 long long tv = * (long long*) ((size_t) target + field->offset); 519 520 tv -= query->right.i32; 521 522 switch(query->type) 523 { 524 case qot_eq: return tv == 0; 525 case qot_ne: return tv != 0; 526 case qot_le: return tv <= 0; 527 case qot_lt: return tv < 0; 528 case qot_ge: return tv >= 0; 529 case qot_gt: return tv > 0; 530 default: 531 DPRINTF(E_LOG,L_QRY,"illegal query type: %d\n", query->type); 532 break; 533 } 534 } 535 break; 536 537 default: 538 DPRINTF(E_LOG,L_QRY,"illegal field type: %d\n", field->type); 539 break; 540 } 541 542 return 0; 543} 544 545static int string_query(query_node_t* query, void* target) 546{ 547 const query_field_t* field = query->left.field; 548 const char* ts; 549 550 if(field->type != qft_string) 551 { 552 DPRINTF(E_LOG,L_QRY,"illegal field type: %d\n", field->type); 553 return 0; 554 } 555 556 ts = * (const char**) ((size_t) target + field->offset); 557 558 if(0 == ts) 559 return strlen(query->right.str) == 0; 560 561 switch(query->type) 562 { 563 case qot_is: 564 return !strcasecmp(query->right.str, ts); 565 566 case qot_begins: 567 return !strncasecmp(query->right.str, ts, strlen(query->right.str)); 568 569 case qot_ends: 570 { 571 int start = strlen(ts) - strlen(query->right.str); 572 573 if(start < 0) 574 return 0; 575 576 return !strcasecmp(query->right.str, ts + start); 577 } 578 579 case qot_contains: 580 return (int) strcasestr(ts, query->right.str); /* returns null if not found */ 581 582 default: 583 DPRINTF(E_LOG,L_QRY,"Illegal query type: %d\n", query->type); 584 break; 585 } 586 587 return 0; 588} 589 590void query_dump(FILE* fp, query_node_t* query, int depth) 591{ 592 static const char* labels[] = { 593 "NOP", 594 "and", 595 "or", 596 "not", 597 "==", 598 "!=", 599 "<=", 600 "<", 601 ">=", 602 ">", 603 "eq", 604 "beginswith", 605 "endwith", 606 "contains", 607 "constant" 608 }; 609 610#ifndef DEBUG 611 return; 612#endif 613 614 switch(query->type) 615 { 616 case qot_and: 617 case qot_or: 618 fprintf(fp, "%*s(%s\n", depth, "", labels[query->type]); 619 query_dump(fp, query->left.node, depth + 4); 620 query_dump(fp, query->right.node, depth + 4); 621 fprintf(fp, "%*s)\n", depth, ""); 622 break; 623 624 case qot_not: 625 fprintf(fp, "%*s(not\n", depth, ""); 626 query_dump(fp, query->left.node, depth + 4); 627 fprintf(fp, "%*s)\n", depth, ""); 628 break; 629 630 /* arithmetic */ 631 case qot_eq: 632 case qot_ne: 633 case qot_le: 634 case qot_lt: 635 case qot_ge: 636 case qot_gt: 637 if(query->left.field->type == qft_i32) 638 fprintf(fp, "%*s(%s %s %d)\n", 639 depth, "", labels[query->type], 640 query->left.field->name, query->right.i32); 641 else 642 fprintf(fp, "%*s(%s %s %q)\n", 643 depth, "", labels[query->type], 644 query->left.field->name, query->right.i64); 645 break; 646 647 /* string */ 648 case qot_is: 649 case qot_begins: 650 case qot_ends: 651 case qot_contains: 652 fprintf(fp, "%*s(%s %s \"%s\")\n", 653 depth, "", labels[query->type], 654 query->left.field->name, query->right.str); 655 break; 656 657 /* constants */ 658 case qot_const: 659 fprintf(fp, "%*s(%s)\n", depth, "", query->left.constant ? "true" : "false"); 660 break; 661 } 662 663} 664 665char* query_unescape(const char* src) 666{ 667 char* copy = malloc(strlen(src) + 1); 668 char* dst = copy; 669 670 while(*src) 671 { 672 if(*src == '%') 673 { 674 int val = 0; 675 676 if(*++src) 677 { 678 if(isdigit(*src)) 679 val = val * 16 + *src - '0'; 680 else 681 val = val * 16 + tolower(*src) - 'a' + 10; 682 } 683 684 if(*++src) 685 { 686 if(isdigit(*src)) 687 val = val * 16 + *src - '0'; 688 else 689 val = val * 16 + tolower(*src) - 'a' + 10; 690 } 691 692 src++; 693 *dst++ = val; 694 } 695 else 696 *dst++ = *src++; 697 } 698 699 *dst++ = 0; 700 701 return copy; 702} 703