epan/dfilter/syntax-tree.c

   1 /*
   2  * Wireshark - Network traffic analyzer
   3  * By Gerald Combs <gerald@wireshark.org>
   4  * Copyright 2001 Gerald Combs
   5  *
   6  * SPDX-License-Identifier: GPL-2.0-or-later
   7  */
   8
   9 #include "config.h"
  10
  11 #define WS_LOG_DOMAIN LOG_DOMAIN_DFILTER
  12
  13 #include "syntax-tree.h"
  14 #include <wsutil/wmem/wmem.h>
  15 #include <wsutil/str_util.h>
  16 #include <wsutil/glib-compat.h>
  17 #include "sttype-op.h"
  18 #include "sttype-function.h"
  19 #include "dfilter-int.h"
  20
  21 /* Keep track of sttype_t's via their sttype_id_t number */
  22 static sttype_t* type_list[STTYPE_NUM_TYPES];
  23
  24
  25 void
  26 sttype_init(void)
  27 {
  28         sttype_register_field();
  29         sttype_register_function();
  30         sttype_register_number();
  31         sttype_register_pointer();
  32         sttype_register_set();
  33         sttype_register_slice();
  34         sttype_register_string();
  35         sttype_register_opers();
  36 }
  37
  38 void
  39 sttype_cleanup(void)
  40 {
  41         /* nothing to do */
  42 }
  43
  44
  45 void
  46 sttype_register(sttype_t *type)
  47 {
  48         sttype_id_t     type_id;
  49
  50         type_id = type->id;
  51
  52         /* Check input */
  53         ws_assert(type_id < STTYPE_NUM_TYPES);
  54
  55         /* Don't re-register. */
  56         ws_assert(type_list[type_id] == NULL);
  57
  58         type_list[type_id] = type;
  59 }
  60
  61 static sttype_t*
  62 sttype_lookup(sttype_id_t type_id)
  63 {
  64         sttype_t        *result;
  65
  66         /* Check input */
  67         ws_assert(type_id < STTYPE_NUM_TYPES);
  68
  69         result = type_list[type_id];
  70
  71         /* Check output. */
  72         ws_assert(result != NULL);
  73
  74         return result;
  75 }
  76
  77 const char *
  78 sttype_name(sttype_id_t type)
  79 {
  80         switch (type) {
  81                 case STTYPE_UNINITIALIZED: return "UNINITIALIZED";
  82                 case STTYPE_TEST:       return "TEST";
  83                 case STTYPE_LITERAL:    return "LITERAL";
  84                 case STTYPE_UNPARSED:   return "UNPARSED";
  85                 case STTYPE_REFERENCE:  return "REFERENCE";
  86                 case STTYPE_STRING:     return "STRING";
  87                 case STTYPE_CHARCONST:  return "CHARCONST";
  88                 case STTYPE_NUMBER:     return "NUMBER";
  89                 case STTYPE_FIELD:      return "FIELD";
  90                 case STTYPE_FVALUE:     return "FVALUE";
  91                 case STTYPE_SLICE:      return "SLICE";
  92                 case STTYPE_FUNCTION:   return "FUNCTION";
  93                 case STTYPE_SET:        return "SET";
  94                 case STTYPE_PCRE:       return "PCRE";
  95                 case STTYPE_ARITHMETIC: return "ARITHMETIC";
  96                 case STTYPE_NUM_TYPES:  return "NUM_TYPES";
  97         }
  98         return "(unknown sttype)";
  99 }
 100
 101 const char *
 102 stnode_op_name(stnode_op_t op)
 103 {
 104         const char *s = "(null)";
 105
 106         switch(op) {
 107                 case STNODE_OP_NOT:
 108                         s = "TEST_NOT";
 109                         break;
 110                 case STNODE_OP_AND:
 111                         s = "TEST_AND";
 112                         break;
 113                 case STNODE_OP_OR:
 114                         s = "TEST_OR";
 115                         break;
 116                 case STNODE_OP_ALL_EQ:
 117                         s = "TEST_ALL_EQ";
 118                         break;
 119                 case STNODE_OP_ANY_EQ:
 120                         s = "TEST_ANY_EQ";
 121                         break;
 122                 case STNODE_OP_ALL_NE:
 123                         s = "TEST_ALL_NE";
 124                         break;
 125                 case STNODE_OP_ANY_NE:
 126                         s = "TEST_ANY_NE";
 127                         break;
 128                 case STNODE_OP_GT:
 129                         s = "TEST_GT";
 130                         break;
 131                 case STNODE_OP_GE:
 132                         s = "TEST_GE";
 133                         break;
 134                 case STNODE_OP_LT:
 135                         s = "TEST_LT";
 136                         break;
 137                 case STNODE_OP_LE:
 138                         s = "TEST_LE";
 139                         break;
 140                 case STNODE_OP_BITWISE_AND:
 141                         s = "OP_BITWISE_AND";
 142                         break;
 143                 case STNODE_OP_UNARY_MINUS:
 144                         s = "OP_UNARY_MINUS";
 145                         break;
 146                 case STNODE_OP_ADD:
 147                         s = "OP_ADD";
 148                         break;
 149                 case STNODE_OP_SUBTRACT:
 150                         s = "OP_SUBTRACT";
 151                         break;
 152                 case STNODE_OP_MULTIPLY:
 153                         s = "OP_MULTIPLY";
 154                         break;
 155                 case STNODE_OP_DIVIDE:
 156                         s = "OP_DIVIDE";
 157                         break;
 158                 case STNODE_OP_MODULO:
 159                         s = "OP_MODULO";
 160                         break;
 161                 case STNODE_OP_CONTAINS:
 162                         s = "TEST_CONTAINS";
 163                         break;
 164                 case STNODE_OP_MATCHES:
 165                         s = "TEST_MATCHES";
 166                         break;
 167                 case STNODE_OP_IN:
 168                         s = "TEST_IN";
 169                         break;
 170                 case STNODE_OP_NOT_IN:
 171                         s = "TEST_NOT_IN";
 172                         break;
 173                 case STNODE_OP_UNINITIALIZED:
 174                         s = "(uninitialized)";
 175                         break;
 176         }
 177
 178         return s;
 179 }
 180
 181 void
 182 stnode_clear(stnode_t *node)
 183 {
 184         if (node->type) {
 185                 if (node->type->func_free && node->data) {
 186                         node->type->func_free(node->data);
 187                 }
 188         }
 189         else {
 190                 ws_assert(!node->data);
 191         }
 192
 193         node->type = NULL;
 194         node->data = NULL;
 195         g_free(node->repr_display);
 196         node->repr_display = NULL;
 197         g_free(node->repr_debug);
 198         node->repr_debug = NULL;
 199         g_free(node->repr_token);
 200         node->repr_token = NULL;
 201         node->location.col_start = -1;
 202         node->location.col_len = 0;
 203         node->flags = 0;
 204 }
 205
 206 void
 207 stnode_init(stnode_t *node, sttype_id_t type_id, void *data, char *token, df_loc_t loc)
 208 {
 209         sttype_t        *type;
 210
 211         ws_assert(!node->type);
 212         ws_assert(!node->data);
 213         node->repr_display = NULL;
 214         node->repr_debug = NULL;
 215         node->repr_token = token;
 216         node->location = loc;
 217         node->flags = 0;
 218
 219         if (type_id == STTYPE_UNINITIALIZED) {
 220                 node->type = NULL;
 221                 node->data = NULL;
 222         }
 223         else {
 224                 /* Creating an initialized node with a NULL pointer is
 225                  * allowed and needs to be safe. The parser relies on that. */
 226                 type = sttype_lookup(type_id);
 227                 ws_assert(type);
 228                 node->type = type;
 229                 if (type->func_new) {
 230                         node->data = type->func_new(data);
 231                 }
 232                 else {
 233                         node->data = data;
 234                 }
 235         }
 236 }
 237
 238 void
 239 stnode_replace(stnode_t *node, sttype_id_t type_id, void *data)
 240 {
 241         char *token = g_strdup(node->repr_token);
 242         df_loc_t loc = node->location;
 243         uint16_t flags = node->flags;
 244         stnode_clear(node);
 245         stnode_init(node, type_id, data, token, loc);
 246         node->flags = flags;
 247 }
 248
 249 void
 250 stnode_mutate(stnode_t *node, sttype_id_t type_id)
 251 {
 252         //FIXME: Assert there all the same sttype
 253         node->type = sttype_lookup(type_id);
 254         ws_assert(node->type);
 255 }
 256
 257 stnode_t*
 258 stnode_new(sttype_id_t type_id, void *data, char *token, df_loc_t loc)
 259 {
 260         stnode_t *node = g_new0(stnode_t, 1);
 261         stnode_init(node, type_id, data, token, loc);
 262         return node;
 263 }
 264
 265 stnode_t*
 266 stnode_new_empty(sttype_id_t type_id)
 267 {
 268         df_loc_t loc = {-1, 0};
 269         return stnode_new(type_id, NULL, NULL, loc);
 270 }
 271
 272 stnode_t*
 273 stnode_dup(const stnode_t *node)
 274 {
 275         stnode_t *new;
 276
 277         new = g_new(stnode_t, 1);
 278         new->repr_display = NULL;
 279         new->repr_debug = NULL;
 280         new->repr_token = g_strdup(node->repr_token);
 281         new->location = node->location;
 282         new->flags = node->flags;
 283
 284         new->type = node->type;
 285         if (node->type == NULL)
 286                 new->data = NULL;
 287         else if (node->type->func_dup)
 288                 new->data = node->type->func_dup(node->data);
 289         else
 290                 new->data = node->data;
 291
 292         return new;
 293 }
 294
 295 void
 296 stnode_free(stnode_t *node)
 297 {
 298         stnode_clear(node);
 299         g_free(node);
 300 }
 301
 302 const char*
 303 stnode_type_name(stnode_t *node)
 304 {
 305         return sttype_name(node->type->id);
 306 }
 307
 308 sttype_id_t
 309 stnode_type_id(stnode_t *node)
 310 {
 311         if (node->type)
 312                 return node->type->id;
 313         else
 314                 return STTYPE_UNINITIALIZED;
 315 }
 316
 317 void *
 318 stnode_data(stnode_t *node)
 319 {
 320         return node->data;
 321 }
 322
 323 GString *
 324 stnode_string(stnode_t *node)
 325 {
 326         ws_assert(stnode_type_id(node) == STTYPE_STRING);
 327         return stnode_data(node);
 328 }
 329
 330 void *
 331 stnode_steal_data(stnode_t *node)
 332 {
 333         void *data = node->data;
 334         ws_assert(data);
 335         node->data = NULL;
 336         return data;
 337 }
 338
 339 const char *
 340 stnode_token(stnode_t *node)
 341 {
 342         return node->repr_token;
 343 }
 344
 345 df_loc_t
 346 stnode_location(stnode_t *node)
 347 {
 348         return node->location;
 349 }
 350
 351 void
 352 stnode_set_location(stnode_t *node, df_loc_t loc)
 353 {
 354         node->location = loc;
 355 }
 356
 357 bool
 358 stnode_get_flags(stnode_t *node, uint16_t flags)
 359 {
 360         return node->flags & flags;
 361 }
 362
 363 void
 364 stnode_set_flags(stnode_t *node, uint16_t flags)
 365 {
 366         node->flags |= flags;
 367 }
 368
 369 /* Finds the first and last location from a set and creates
 370  * a new location from start of first (col_start) to end of
 371  * last (col_start + col_len). Sets the result to dst. */
 372 void
 373 stnode_merge_location(stnode_t *dst, stnode_t *n1, stnode_t *n2)
 374 {
 375         df_loc_t first, last;
 376         df_loc_t loc2;
 377
 378         first = last = stnode_location(n1);
 379         loc2 = stnode_location(n2);
 380         if (loc2.col_start >= 0 && loc2.col_start > first.col_start)
 381                 last = loc2;
 382         dst->location.col_start = first.col_start;
 383         dst->location.col_len = last.col_start - first.col_start + last.col_len;
 384 }
 385
 386 #define IS_OPERATOR(node) \
 387         (stnode_type_id(node) == STTYPE_TEST || \
 388                 stnode_type_id(node) == STTYPE_ARITHMETIC)
 389
 390 static char *
 391 _node_tostr(stnode_t *node, bool pretty)
 392 {
 393         char *s, *repr;
 394
 395         if (node->type->func_tostr == NULL)
 396                 s = g_strdup("FIXME");
 397         else
 398                 s = node->type->func_tostr(node->data, pretty);
 399
 400         if (pretty)
 401                 return s;
 402
 403         if (IS_OPERATOR(node)) {
 404                 repr = s;
 405         }
 406         else {
 407                 repr = ws_strdup_printf("%s(%s)", stnode_type_name(node), s);
 408                 g_free(s);
 409         }
 410
 411         return repr;
 412 }
 413
 414 const char *
 415 stnode_tostr(stnode_t *node, bool pretty)
 416 {
 417         if (pretty && IS_OPERATOR(node) && node->repr_token != NULL) {
 418                 /* Some operators can have synonyms, like "or" and "||".
 419                  * Show the user the same representation as he typed. */
 420                 g_free(node->repr_display);
 421                 node->repr_display = g_strdup(node->repr_token);
 422                 return node->repr_display;
 423         }
 424
 425         char *str = _node_tostr(node, pretty);
 426
 427         if (pretty) {
 428                 g_free(node->repr_display);
 429                 node->repr_display = str;
 430         }
 431         else {
 432                 g_free(node->repr_debug);
 433                 node->repr_debug = str;
 434         }
 435
 436         return str;
 437 }
 438
 439 static char *
 440 sprint_node(stnode_t *node)
 441 {
 442         wmem_strbuf_t *buf = wmem_strbuf_new(NULL, NULL);
 443
 444         wmem_strbuf_append_printf(buf, "{ ");
 445         wmem_strbuf_append_printf(buf, "type = %s, ", stnode_type_name(node));
 446         wmem_strbuf_append_printf(buf, "data = %s, ", stnode_todebug(node));
 447         wmem_strbuf_append_printf(buf, "location = %ld:%zu",
 448                         node->location.col_start, node->location.col_len);
 449         wmem_strbuf_append_printf(buf, " }");
 450         return wmem_strbuf_finalize(buf);
 451 }
 452
 453 void
 454 log_node_full(enum ws_log_level level,
 455                         const char *file, int line, const char *func,
 456                         stnode_t *node, const char *msg)
 457 {
 458         if (!ws_log_msg_is_active(WS_LOG_DOMAIN, level))
 459                 return;
 460
 461         if (node == NULL) {
 462                 ws_log_write_always_full(WS_LOG_DOMAIN, level,
 463                                         file, line, func, "%s is NULL", msg);
 464                 return;
 465         }
 466
 467         char *str = sprint_node(node);
 468
 469         ws_log_write_always_full(WS_LOG_DOMAIN, level, file, line, func,
 470                                 "%s = %s", msg, str);
 471
 472         g_free(str);
 473 }
 474
 475 void
 476 log_test_full(enum ws_log_level level,
 477                         const char *file, int line, const char *func,
 478                         stnode_t *node, const char *msg)
 479 {
 480         if (!ws_log_msg_is_active(WS_LOG_DOMAIN, level))
 481                 return;
 482
 483         if (node == NULL) {
 484                 ws_log_write_always_full(WS_LOG_DOMAIN, level,
 485                                         file, line, func, "%s is NULL", msg);
 486                 return;
 487         }
 488
 489         stnode_op_t st_op;
 490         stnode_t *st_lhs = NULL, *st_rhs = NULL;
 491         char *lhs = NULL, *rhs = NULL;
 492
 493         sttype_oper_get(node, &st_op, &st_lhs, &st_rhs);
 494
 495         if (st_lhs)
 496                 lhs = sprint_node(st_lhs);
 497         if (st_rhs)
 498                 rhs = sprint_node(st_rhs);
 499
 500         ws_log_write_always_full(WS_LOG_DOMAIN, level, file, line, func,
 501                                 "%s:\n LHS = %s\n RHS = %s",
 502                                 stnode_todebug(node),
 503                                 lhs ? lhs : "NULL",
 504                                 rhs ? rhs : "NULL");
 505
 506         g_free(lhs);
 507         g_free(rhs);
 508 }
 509
 510 static void
 511 indent(wmem_strbuf_t *buf, int level)
 512 {
 513         for (int i = 0; i < level * 2; i++) {
 514                 wmem_strbuf_append_c(buf, ' ');
 515         }
 516         wmem_strbuf_append_printf(buf, "% 2d ", level);
 517 }
 518
 519 static void
 520 visit_tree(wmem_strbuf_t *buf, stnode_t *node, int level)
 521 {
 522         stnode_t *left, *right;
 523         stnode_t *lower, *upper;
 524         GSList *params;
 525         GSList *nodelist;
 526
 527         if (stnode_type_id(node) == STTYPE_TEST ||
 528                         stnode_type_id(node) == STTYPE_ARITHMETIC) {
 529                 wmem_strbuf_append_printf(buf, "%s:\n", stnode_todebug(node));
 530                 sttype_oper_get(node, NULL, &left, &right);
 531                 if (left && right) {
 532                         indent(buf, level + 1);
 533                         visit_tree(buf, left, level + 1);
 534                         wmem_strbuf_append_c(buf, '\n');
 535                         indent(buf, level + 1);
 536                         visit_tree(buf, right, level + 1);
 537                 }
 538                 else if (left) {
 539                         indent(buf, level + 1);
 540                         visit_tree(buf, left, level + 1);
 541                 }
 542                 else if (right) {
 543                         ws_assert_not_reached();
 544                 }
 545         }
 546         else if (stnode_type_id(node) == STTYPE_SET) {
 547                 nodelist = stnode_data(node);
 548                 wmem_strbuf_append_printf(buf, "SET(#%u):\n", g_slist_length(nodelist) / 2);
 549                 while (nodelist) {
 550                         indent(buf, level + 1);
 551                         lower = nodelist->data;
 552                         wmem_strbuf_append(buf, stnode_tostr(lower, false));
 553                         /* Set elements are always in pairs; upper may be null. */
 554                         nodelist = g_slist_next(nodelist);
 555                         ws_assert(nodelist);
 556                         upper = nodelist->data;
 557                         if (upper != NULL) {
 558                                 wmem_strbuf_append(buf, " .. ");
 559                                 wmem_strbuf_append(buf, stnode_tostr(upper, false));
 560                         }
 561                         nodelist = g_slist_next(nodelist);
 562                         if (nodelist != NULL) {
 563                                 wmem_strbuf_append_c(buf, '\n');
 564                         }
 565                 }
 566         }
 567         else if (stnode_type_id(node) == STTYPE_FUNCTION) {
 568                 wmem_strbuf_append_printf(buf, "%s:\n", stnode_todebug(node));
 569                 params = sttype_function_params(node);
 570                 while (params) {
 571                         indent(buf, level + 1);
 572                         visit_tree(buf, params->data, level + 1);
 573                         if (params->next != NULL) {
 574                                 wmem_strbuf_append_c(buf, '\n');
 575                         }
 576                         params = params->next;
 577                 }
 578         }
 579         else {
 580                 wmem_strbuf_append(buf, stnode_todebug(node));
 581         }
 582 }
 583
 584 char *
 585 dump_syntax_tree_str(stnode_t *root)
 586 {
 587         wmem_strbuf_t *buf = wmem_strbuf_new(NULL, NULL);
 588         indent(buf, 0);
 589         visit_tree(buf, root, 0);
 590         return wmem_strbuf_finalize(buf);
 591 }
 592
 593 void
 594 log_syntax_tree(enum ws_log_level level, stnode_t *root, const char *msg, char **cache_ptr)
 595 {
 596         if (!ws_log_msg_is_active(LOG_DOMAIN_DFILTER, level))
 597                 return;
 598
 599         char *str = dump_syntax_tree_str(root);
 600
 601         ws_log_write_always_full(LOG_DOMAIN_DFILTER, level, NULL, -1, NULL,
 602                                 "%s:\n%s", msg, str);
 603
 604         if (cache_ptr) {
 605                 *cache_ptr = str;
 606         }
 607         else {
 608                 g_free(str);
 609         }
 610 }
 611
 612 /*
 613  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 614  *
 615  * Local variables:
 616  * c-basic-offset: 8
 617  * tab-width: 8
 618  * indent-tabs-mode: t
 619  * End:
 620  *
 621  * vi: set shiftwidth=8 tabstop=8 noexpandtab:
 622  * :indentSize=8:tabSize=8:noTabs=false:
 623  */