src/libsystemd-bus/bus-match.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include "bus-internal.h"
  23 #include "bus-message.h"
  24 #include "bus-match.h"
  25 #include "bus-error.h"
  26 #include "bus-util.h"
  27
  28 /* Example:
  29  *
  30  *  A: type=signal,sender=foo,interface=bar
  31  *  B: type=signal,sender=quux,interface=fips
  32  *  C: type=signal,sender=quux,interface=waldo
  33  *  D: type=signal,member=test
  34  *  E: sender=miau
  35  *  F: type=signal
  36  *  G: type=signal
  37  *
  38  *  results in this tree:
  39  *
  40  *  BUS_MATCH_ROOT
  41  *  + BUS_MATCH_MESSAGE_TYPE
  42  *  | ` BUS_MATCH_VALUE: value == signal
  43  *  |   + DBUS_MATCH_SENDER
  44  *  |   | + BUS_MATCH_VALUE: value == foo
  45  *  |   | | ` DBUS_MATCH_INTERFACE
  46  *  |   | |   ` BUS_MATCH_VALUE: value == bar
  47  *  |   | |     ` BUS_MATCH_LEAF: A
  48  *  |   | ` BUS_MATCH_VALUE: value == quux
  49  *  |   |   ` DBUS_MATCH_INTERFACE
  50  *  |   |     | BUS_MATCH_VALUE: value == fips
  51  *  |   |     | ` BUS_MATCH_LEAF: B
  52  *  |   |     ` BUS_MATCH_VALUE: value == waldo
  53  *  |   |       ` BUS_MATCH_LEAF: C
  54  *  |   + DBUS_MATCH_MEMBER
  55  *  |   | ` BUS_MATCH_VALUE: value == test
  56  *  |   |   ` BUS_MATCH_LEAF: D
  57  *  |   + BUS_MATCH_LEAF: F
  58  *  |   ` BUS_MATCH_LEAF: G
  59  *  ` BUS_MATCH_SENDER
  60  *    ` BUS_MATCH_VALUE: value == miau
  61  *      ` BUS_MATCH_LEAF: E
  62  */
  63
  64 static inline bool BUS_MATCH_IS_COMPARE(enum bus_match_node_type t) {
  65         return t >= BUS_MATCH_SENDER && t <= BUS_MATCH_ARG_NAMESPACE_LAST;
  66 }
  67
  68 static inline bool BUS_MATCH_CAN_HASH(enum bus_match_node_type t) {
  69         return (t >= BUS_MATCH_MESSAGE_TYPE && t <= BUS_MATCH_PATH) ||
  70                 (t >= BUS_MATCH_ARG && t <= BUS_MATCH_ARG_LAST);
  71 }
  72
  73 static void bus_match_node_free(struct bus_match_node *node) {
  74         assert(node);
  75         assert(node->parent);
  76         assert(!node->child);
  77         assert(node->type != BUS_MATCH_ROOT);
  78         assert(node->type < _BUS_MATCH_NODE_TYPE_MAX);
  79
  80         if (node->parent->child) {
  81                 /* We are apparently linked into the parent's child
  82                  * list. Let's remove us from there. */
  83                 if (node->prev) {
  84                         assert(node->prev->next == node);
  85                         node->prev->next = node->next;
  86                 } else {
  87                         assert(node->parent->child == node);
  88                         node->parent->child = node->next;
  89                 }
  90
  91                 if (node->next)
  92                         node->next->prev = node->prev;
  93         }
  94
  95         if (node->type == BUS_MATCH_VALUE) {
  96                 /* We might be in the parent's hash table, so clean
  97                  * this up */
  98
  99                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 100                         hashmap_remove(node->parent->compare.children, UINT_TO_PTR(node->value.u8));
 101                 else if (BUS_MATCH_CAN_HASH(node->parent->type) && node->value.str)
 102                         hashmap_remove(node->parent->compare.children, node->value.str);
 103
 104                 free(node->value.str);
 105         }
 106
 107         if (BUS_MATCH_IS_COMPARE(node->type)) {
 108                 assert(hashmap_isempty(node->compare.children));
 109                 hashmap_free(node->compare.children);
 110         }
 111
 112         free(node);
 113 }
 114
 115 static bool bus_match_node_maybe_free(struct bus_match_node *node) {
 116         assert(node);
 117
 118         if (node->child)
 119                 return false;
 120
 121         if (BUS_MATCH_IS_COMPARE(node->type) && !hashmap_isempty(node->compare.children))
 122                 return true;
 123
 124         bus_match_node_free(node);
 125         return true;
 126 }
 127
 128 static bool value_node_test(
 129                 struct bus_match_node *node,
 130                 enum bus_match_node_type parent_type,
 131                 uint8_t value_u8,
 132                 const char *value_str) {
 133
 134         assert(node);
 135         assert(node->type == BUS_MATCH_VALUE);
 136
 137         /* Tests parameters against this value node, doing prefix
 138          * magic and stuff. */
 139
 140         switch (parent_type) {
 141
 142         case BUS_MATCH_MESSAGE_TYPE:
 143                 return node->value.u8 == value_u8;
 144
 145         case BUS_MATCH_SENDER:
 146         case BUS_MATCH_DESTINATION:
 147                 if (streq_ptr(node->value.str, value_str))
 148                         return true;
 149
 150                 /* FIXME: So here's an ugliness: if the match is for a
 151                  * well-known name then we cannot actually check this
 152                  * correctly here. This doesn't matter much for dbus1
 153                  * where no false positives exist, hence we just
 154                  * ignore this case here. For kdbus the messages
 155                  * should contain all well-known names of the sender,
 156                  * hence we can fix things there correctly. */
 157
 158                 if (node->value.str[0] != ':' && value_str && value_str[0] == ':')
 159                         return true;
 160
 161                 return false;
 162
 163         case BUS_MATCH_INTERFACE:
 164         case BUS_MATCH_MEMBER:
 165         case BUS_MATCH_PATH:
 166         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 167                 return streq_ptr(node->value.str, value_str);
 168
 169         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 170                 return namespace_simple_pattern(node->value.str, value_str);
 171
 172         case BUS_MATCH_PATH_NAMESPACE:
 173                 return path_simple_pattern(node->value.str, value_str);
 174
 175         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 176                 return path_complex_pattern(node->value.str, value_str);
 177
 178         default:
 179                 assert_not_reached("Invalid node type");
 180         }
 181 }
 182
 183 static bool value_node_same(
 184                 struct bus_match_node *node,
 185                 enum bus_match_node_type parent_type,
 186                 uint8_t value_u8,
 187                 const char *value_str) {
 188
 189         /* Tests parameters against this value node, not doing prefix
 190          * magic and stuff, i.e. this one actually compares the match
 191          * itself.*/
 192
 193         assert(node);
 194         assert(node->type == BUS_MATCH_VALUE);
 195
 196         switch (parent_type) {
 197
 198         case BUS_MATCH_MESSAGE_TYPE:
 199                 return node->value.u8 == value_u8;
 200
 201         case BUS_MATCH_SENDER:
 202         case BUS_MATCH_DESTINATION:
 203         case BUS_MATCH_INTERFACE:
 204         case BUS_MATCH_MEMBER:
 205         case BUS_MATCH_PATH:
 206         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 207         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 208         case BUS_MATCH_PATH_NAMESPACE:
 209         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 210                 return streq(node->value.str, value_str);
 211
 212         default:
 213                 assert_not_reached("Invalid node type");
 214         }
 215 }
 216
 217 int bus_match_run(
 218                 sd_bus *bus,
 219                 struct bus_match_node *node,
 220                 sd_bus_message *m) {
 221
 222
 223         const char *test_str = NULL;
 224         uint8_t test_u8 = 0;
 225         int r;
 226
 227         assert(m);
 228
 229         if (!node)
 230                 return 0;
 231
 232         if (bus && bus->match_callbacks_modified)
 233                 return 0;
 234
 235         /* Not these special semantics: when traversing the tree we
 236          * usually let bus_match_run() when called for a node
 237          * recursively invoke bus_match_run(). There's are two
 238          * exceptions here though, which are BUS_NODE_ROOT (which
 239          * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
 240          * are invoked anyway by its parent. */
 241
 242         switch (node->type) {
 243
 244         case BUS_MATCH_ROOT:
 245
 246                 /* Run all children. Since we cannot have any siblings
 247                  * we won't call any. The children of the root node
 248                  * are compares or leaves, they will automatically
 249                  * call their siblings. */
 250                 return bus_match_run(bus, node->child, m);
 251
 252         case BUS_MATCH_VALUE:
 253
 254                 /* Run all children. We don't execute any siblings, we
 255                  * assume our caller does that. The children of value
 256                  * nodes are compares or leaves, they will
 257                  * automatically call their siblings */
 258
 259                 assert(node->child);
 260                 return bus_match_run(bus, node->child, m);
 261
 262         case BUS_MATCH_LEAF:
 263
 264                 if (bus) {
 265                         if (node->leaf.last_iteration == bus->iteration_counter)
 266                                 return 0;
 267
 268                         node->leaf.last_iteration = bus->iteration_counter;
 269                 }
 270
 271                 r = sd_bus_message_rewind(m, true);
 272                 if (r < 0)
 273                         return r;
 274
 275                 /* Run the callback. And then invoke siblings. */
 276                 if (node->leaf.callback) {
 277                         _cleanup_bus_error_free_ sd_bus_error error_buffer = SD_BUS_ERROR_NULL;
 278
 279                         r = node->leaf.callback(bus, m, node->leaf.userdata, &error_buffer);
 280                         r = bus_maybe_reply_error(m, r, &error_buffer);
 281                         if (r != 0)
 282                                 return r;
 283                 }
 284
 285                 return bus_match_run(bus, node->next, m);
 286
 287         case BUS_MATCH_MESSAGE_TYPE:
 288                 test_u8 = m->header->type;
 289                 break;
 290
 291         case BUS_MATCH_SENDER:
 292                 test_str = m->sender;
 293                 /* FIXME: resolve test_str from a well-known to a unique name first */
 294                 break;
 295
 296         case BUS_MATCH_DESTINATION:
 297                 test_str = m->destination;
 298                 break;
 299
 300         case BUS_MATCH_INTERFACE:
 301                 test_str = m->interface;
 302                 break;
 303
 304         case BUS_MATCH_MEMBER:
 305                 test_str = m->member;
 306                 break;
 307
 308         case BUS_MATCH_PATH:
 309         case BUS_MATCH_PATH_NAMESPACE:
 310                 test_str = m->path;
 311                 break;
 312
 313         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 314                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
 315                 break;
 316
 317         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 318                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
 319                 break;
 320
 321         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 322                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
 323                 break;
 324
 325         default:
 326                 assert_not_reached("Unknown match type.");
 327         }
 328
 329         if (BUS_MATCH_CAN_HASH(node->type)) {
 330                 struct bus_match_node *found;
 331
 332                 /* Lookup via hash table, nice! So let's jump directly. */
 333
 334                 if (test_str)
 335                         found = hashmap_get(node->compare.children, test_str);
 336                 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
 337                         found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
 338                 else
 339                         found = NULL;
 340
 341                 if (found) {
 342                         r = bus_match_run(bus, found, m);
 343                         if (r != 0)
 344                                 return r;
 345                 }
 346         } else {
 347                 struct bus_match_node *c;
 348
 349                 /* No hash table, so let's iterate manually... */
 350
 351                 for (c = node->child; c; c = c->next) {
 352                         if (!value_node_test(c, node->type, test_u8, test_str))
 353                                 continue;
 354
 355                         r = bus_match_run(bus, c, m);
 356                         if (r != 0)
 357                                 return r;
 358                 }
 359         }
 360
 361         if (bus && bus->match_callbacks_modified)
 362                 return 0;
 363
 364         /* And now, let's invoke our siblings */
 365         return bus_match_run(bus, node->next, m);
 366 }
 367
 368 static int bus_match_add_compare_value(
 369                 struct bus_match_node *where,
 370                 enum bus_match_node_type t,
 371                 uint8_t value_u8,
 372                 const char *value_str,
 373                 struct bus_match_node **ret) {
 374
 375         struct bus_match_node *c = NULL, *n = NULL;
 376         int r;
 377
 378         assert(where);
 379         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 380         assert(BUS_MATCH_IS_COMPARE(t));
 381         assert(ret);
 382
 383         for (c = where->child; c && c->type != t; c = c->next)
 384                 ;
 385
 386         if (c) {
 387                 /* Comparison node already exists? Then let's see if
 388                  * the value node exists too. */
 389
 390                 if (t == BUS_MATCH_MESSAGE_TYPE)
 391                         n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 392                 else if (BUS_MATCH_CAN_HASH(t))
 393                         n = hashmap_get(c->compare.children, value_str);
 394                 else {
 395                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 396                                 ;
 397                 }
 398
 399                 if (n) {
 400                         *ret = n;
 401                         return 0;
 402                 }
 403         } else {
 404                 /* Comparison node, doesn't exist yet? Then let's
 405                  * create it. */
 406
 407                 c = new0(struct bus_match_node, 1);
 408                 if (!c) {
 409                         r = -ENOMEM;
 410                         goto fail;
 411                 }
 412
 413                 c->type = t;
 414                 c->parent = where;
 415                 c->next = where->child;
 416                 if (c->next)
 417                         c->next->prev = c;
 418                 where->child = c;
 419
 420                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 421                         c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
 422                         if (!c->compare.children) {
 423                                 r = -ENOMEM;
 424                                 goto fail;
 425                         }
 426                 } else if (BUS_MATCH_CAN_HASH(t)) {
 427                         c->compare.children = hashmap_new(string_hash_func, string_compare_func);
 428                         if (!c->compare.children) {
 429                                 r = -ENOMEM;
 430                                 goto fail;
 431                         }
 432                 }
 433         }
 434
 435         n = new0(struct bus_match_node, 1);
 436         if (!n) {
 437                 r = -ENOMEM;
 438                 goto fail;
 439         }
 440
 441         n->type = BUS_MATCH_VALUE;
 442         n->value.u8 = value_u8;
 443         if (value_str) {
 444                 n->value.str = strdup(value_str);
 445                 if (!n->value.str) {
 446                         r = -ENOMEM;
 447                         goto fail;
 448                 }
 449         }
 450
 451         n->parent = c;
 452         if (c->compare.children) {
 453
 454                 if (t == BUS_MATCH_MESSAGE_TYPE)
 455                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 456                 else
 457                         r = hashmap_put(c->compare.children, n->value.str, n);
 458
 459                 if (r < 0)
 460                         goto fail;
 461         } else {
 462                 n->next = c->child;
 463                 if (n->next)
 464                         n->next->prev = n;
 465                 c->child = n;
 466         }
 467
 468         *ret = n;
 469         return 1;
 470
 471 fail:
 472         if (c)
 473                 bus_match_node_maybe_free(c);
 474
 475         if (n) {
 476                 free(n->value.str);
 477                 free(n);
 478         }
 479
 480         return r;
 481 }
 482
 483 static int bus_match_find_compare_value(
 484                 struct bus_match_node *where,
 485                 enum bus_match_node_type t,
 486                 uint8_t value_u8,
 487                 const char *value_str,
 488                 struct bus_match_node **ret) {
 489
 490         struct bus_match_node *c, *n;
 491
 492         assert(where);
 493         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 494         assert(BUS_MATCH_IS_COMPARE(t));
 495         assert(ret);
 496
 497         for (c = where->child; c && c->type != t; c = c->next)
 498                 ;
 499
 500         if (!c)
 501                 return 0;
 502
 503         if (t == BUS_MATCH_MESSAGE_TYPE)
 504                 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 505         else if (BUS_MATCH_CAN_HASH(t))
 506                 n = hashmap_get(c->compare.children, value_str);
 507         else {
 508                 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
 509                         ;
 510         }
 511
 512         if (n) {
 513                 *ret = n;
 514                 return 1;
 515         }
 516
 517         return 0;
 518 }
 519
 520 static int bus_match_add_leaf(
 521                 struct bus_match_node *where,
 522                 sd_bus_message_handler_t callback,
 523                 void *userdata,
 524                 uint64_t cookie,
 525                 struct bus_match_node **ret) {
 526
 527         struct bus_match_node *n;
 528
 529         assert(where);
 530         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 531         assert(ret);
 532
 533         n = new0(struct bus_match_node, 1);
 534         if (!n)
 535                 return -ENOMEM;
 536
 537         n->type = BUS_MATCH_LEAF;
 538         n->parent = where;
 539         n->next = where->child;
 540         if (n->next)
 541                 n->next->prev = n;
 542         n->leaf.callback = callback;
 543         n->leaf.userdata = userdata;
 544         n->leaf.cookie = cookie;
 545
 546         where->child = n;
 547
 548         *ret = n;
 549         return 1;
 550 }
 551
 552 static int bus_match_find_leaf(
 553                 struct bus_match_node *where,
 554                 sd_bus_message_handler_t callback,
 555                 void *userdata,
 556                 struct bus_match_node **ret) {
 557
 558         struct bus_match_node *c;
 559
 560         assert(where);
 561         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 562         assert(ret);
 563
 564         for (c = where->child; c; c = c->next) {
 565                 if (c->type == BUS_MATCH_LEAF &&
 566                     c->leaf.callback == callback &&
 567                     c->leaf.userdata == userdata) {
 568                         *ret = c;
 569                         return 1;
 570                 }
 571         }
 572
 573         return 0;
 574 }
 575
 576 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 577         assert(k);
 578
 579         if (n == 4 && startswith(k, "type"))
 580                 return BUS_MATCH_MESSAGE_TYPE;
 581         if (n == 6 && startswith(k, "sender"))
 582                 return BUS_MATCH_SENDER;
 583         if (n == 11 && startswith(k, "destination"))
 584                 return BUS_MATCH_DESTINATION;
 585         if (n == 9 && startswith(k, "interface"))
 586                 return BUS_MATCH_INTERFACE;
 587         if (n == 6 && startswith(k, "member"))
 588                 return BUS_MATCH_MEMBER;
 589         if (n == 4 && startswith(k, "path"))
 590                 return BUS_MATCH_PATH;
 591         if (n == 14 && startswith(k, "path_namespace"))
 592                 return BUS_MATCH_PATH_NAMESPACE;
 593
 594         if (n == 4 && startswith(k, "arg")) {
 595                 int j;
 596
 597                 j = undecchar(k[3]);
 598                 if (j < 0)
 599                         return -EINVAL;
 600
 601                 return BUS_MATCH_ARG + j;
 602         }
 603
 604         if (n == 5 && startswith(k, "arg")) {
 605                 int a, b;
 606                 enum bus_match_node_type t;
 607
 608                 a = undecchar(k[3]);
 609                 b = undecchar(k[4]);
 610                 if (a <= 0 || b < 0)
 611                         return -EINVAL;
 612
 613                 t = BUS_MATCH_ARG + a * 10 + b;
 614                 if (t > BUS_MATCH_ARG_LAST)
 615                         return -EINVAL;
 616
 617                 return t;
 618         }
 619
 620         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 621                 int j;
 622
 623                 j = undecchar(k[3]);
 624                 if (j < 0)
 625                         return -EINVAL;
 626
 627                 return BUS_MATCH_ARG_PATH + j;
 628         }
 629
 630         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 631                 enum bus_match_node_type t;
 632                 int a, b;
 633
 634                 a = undecchar(k[3]);
 635                 b = undecchar(k[4]);
 636                 if (a <= 0 || b < 0)
 637                         return -EINVAL;
 638
 639                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 640                 if (t > BUS_MATCH_ARG_PATH_LAST)
 641                         return -EINVAL;
 642
 643                 return t;
 644         }
 645
 646         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 647                 int j;
 648
 649                 j = undecchar(k[3]);
 650                 if (j < 0)
 651                         return -EINVAL;
 652
 653                 return BUS_MATCH_ARG_NAMESPACE + j;
 654         }
 655
 656         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 657                 enum bus_match_node_type t;
 658                 int a, b;
 659
 660                 a = undecchar(k[3]);
 661                 b = undecchar(k[4]);
 662                 if (a <= 0 || b < 0)
 663                         return -EINVAL;
 664
 665                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 666                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 667                         return -EINVAL;
 668
 669                 return t;
 670         }
 671
 672         return -EINVAL;
 673 }
 674
 675 static int match_component_compare(const void *a, const void *b) {
 676         const struct bus_match_component *x = a, *y = b;
 677
 678         if (x->type < y->type)
 679                 return -1;
 680         if (x->type > y->type)
 681                 return 1;
 682
 683         return 0;
 684 }
 685
 686 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 687         unsigned i;
 688
 689         for (i = 0; i < n_components; i++)
 690                 free(components[i].value_str);
 691
 692         free(components);
 693 }
 694
 695 int bus_match_parse(
 696                 const char *match,
 697                 struct bus_match_component **_components,
 698                 unsigned *_n_components) {
 699
 700         const char *p = match;
 701         struct bus_match_component *components = NULL;
 702         size_t components_allocated = 0;
 703         unsigned n_components = 0, i;
 704         _cleanup_free_ char *value = NULL;
 705         int r;
 706
 707         assert(match);
 708         assert(_components);
 709         assert(_n_components);
 710
 711         while (*p != 0) {
 712                 const char *eq, *q;
 713                 enum bus_match_node_type t;
 714                 unsigned j = 0;
 715                 size_t value_allocated = 0;
 716                 bool escaped = false;
 717                 uint8_t u;
 718
 719                 eq = strchr(p, '=');
 720                 if (!eq)
 721                         return -EINVAL;
 722
 723                 if (eq[1] != '\'')
 724                         return -EINVAL;
 725
 726                 t = bus_match_node_type_from_string(p, eq - p);
 727                 if (t < 0)
 728                         return -EINVAL;
 729
 730                 for (q = eq + 2;; q++) {
 731
 732                         if (*q == 0) {
 733                                 r = -EINVAL;
 734                                 goto fail;
 735                         }
 736
 737                         if (!escaped) {
 738                                 if (*q == '\\') {
 739                                         escaped = true;
 740                                         continue;
 741                                 }
 742                                 if (*q == '\'') {
 743                                         if (value)
 744                                                 value[j] = 0;
 745                                         break;
 746                                 }
 747                         }
 748
 749                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 750                                 r = -ENOMEM;
 751                                 goto fail;
 752                         }
 753
 754                         value[j++] = *q;
 755                         escaped = false;
 756                 }
 757
 758                 if (!value) {
 759                         value = strdup("");
 760                         if (!value) {
 761                                 r = -ENOMEM;
 762                                 goto fail;
 763                         }
 764                 }
 765
 766                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 767                         r = bus_message_type_from_string(value, &u);
 768                         if (r < 0)
 769                                 goto fail;
 770
 771                         free(value);
 772                         value = NULL;
 773                 } else
 774                         u = 0;
 775
 776                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 777                         r = -ENOMEM;
 778                         goto fail;
 779                 }
 780
 781                 components[n_components].type = t;
 782                 components[n_components].value_str = value;
 783                 components[n_components].value_u8 = u;
 784                 n_components++;
 785
 786                 value = NULL;
 787
 788                 if (q[1] == 0)
 789                         break;
 790
 791                 if (q[1] != ',') {
 792                         r = -EINVAL;
 793                         goto fail;
 794                 }
 795
 796                 p = q + 2;
 797         }
 798
 799         /* Order the whole thing, so that we always generate the same tree */
 800         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 801
 802         /* Check for duplicates */
 803         for (i = 0; i+1 < n_components; i++)
 804                 if (components[i].type == components[i+1].type) {
 805                         r = -EINVAL;
 806                         goto fail;
 807                 }
 808
 809         *_components = components;
 810         *_n_components = n_components;
 811
 812         return 0;
 813
 814 fail:
 815         bus_match_parse_free(components, n_components);
 816         return r;
 817 }
 818
 819 int bus_match_add(
 820                 struct bus_match_node *root,
 821                 struct bus_match_component *components,
 822                 unsigned n_components,
 823                 sd_bus_message_handler_t callback,
 824                 void *userdata,
 825                 uint64_t cookie,
 826                 struct bus_match_node **ret) {
 827
 828         unsigned i;
 829         struct bus_match_node *n;
 830         int r;
 831
 832         assert(root);
 833
 834         n = root;
 835         for (i = 0; i < n_components; i++) {
 836                 r = bus_match_add_compare_value(
 837                                 n, components[i].type,
 838                                 components[i].value_u8, components[i].value_str, &n);
 839                 if (r < 0)
 840                         return r;
 841         }
 842
 843         r = bus_match_add_leaf(n, callback, userdata, cookie, &n);
 844         if (r < 0)
 845                 return r;
 846
 847         if (ret)
 848                 *ret = n;
 849
 850         return 0;
 851 }
 852
 853 int bus_match_remove(
 854                 struct bus_match_node *root,
 855                 struct bus_match_component *components,
 856                 unsigned n_components,
 857                 sd_bus_message_handler_t callback,
 858                 void *userdata,
 859                 uint64_t *cookie) {
 860
 861         unsigned i;
 862         struct bus_match_node *n, **gc;
 863         int r;
 864
 865         assert(root);
 866
 867         gc = newa(struct bus_match_node*, n_components);
 868
 869         n = root;
 870         for (i = 0; i < n_components; i++) {
 871                 r = bus_match_find_compare_value(
 872                                 n, components[i].type,
 873                                 components[i].value_u8, components[i].value_str,
 874                                 &n);
 875                 if (r <= 0)
 876                         return r;
 877
 878                 gc[i] = n;
 879         }
 880
 881         r = bus_match_find_leaf(n, callback, userdata, &n);
 882         if (r <= 0)
 883                 return r;
 884
 885         if (cookie)
 886                 *cookie = n->leaf.cookie;
 887
 888         /* Free the leaf */
 889         bus_match_node_free(n);
 890
 891         /* Prune the tree above */
 892         for (i = n_components; i > 0; i --) {
 893                 struct bus_match_node *p = gc[i-1]->parent;
 894
 895                 if (!bus_match_node_maybe_free(gc[i-1]))
 896                         break;
 897
 898                 if (!bus_match_node_maybe_free(p))
 899                         break;
 900         }
 901
 902         return r;
 903 }
 904
 905 void bus_match_free(struct bus_match_node *node) {
 906         struct bus_match_node *c;
 907
 908         if (!node)
 909                 return;
 910
 911         if (BUS_MATCH_CAN_HASH(node->type)) {
 912                 Iterator i;
 913
 914                 HASHMAP_FOREACH(c, node->compare.children, i)
 915                         bus_match_free(c);
 916
 917                 assert(hashmap_isempty(node->compare.children));
 918         }
 919
 920         while ((c = node->child))
 921                 bus_match_free(c);
 922
 923         if (node->type != BUS_MATCH_ROOT)
 924                 bus_match_node_free(node);
 925 }
 926
 927 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
 928         switch (t) {
 929
 930         case BUS_MATCH_ROOT:
 931                 return "root";
 932
 933         case BUS_MATCH_VALUE:
 934                 return "value";
 935
 936         case BUS_MATCH_LEAF:
 937                 return "leaf";
 938
 939         case BUS_MATCH_MESSAGE_TYPE:
 940                 return "type";
 941
 942         case BUS_MATCH_SENDER:
 943                 return "sender";
 944
 945         case BUS_MATCH_DESTINATION:
 946                 return "destination";
 947
 948         case BUS_MATCH_INTERFACE:
 949                 return "interface";
 950
 951         case BUS_MATCH_MEMBER:
 952                 return "member";
 953
 954         case BUS_MATCH_PATH:
 955                 return "path";
 956
 957         case BUS_MATCH_PATH_NAMESPACE:
 958                 return "path_namespace";
 959
 960         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 961                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
 962                 return buf;
 963
 964         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 965                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
 966                 return buf;
 967
 968         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 969                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
 970                 return buf;
 971
 972         default:
 973                 return NULL;
 974         }
 975 }
 976
 977 void bus_match_dump(struct bus_match_node *node, unsigned level) {
 978         struct bus_match_node *c;
 979         _cleanup_free_ char *pfx = NULL;
 980         char buf[32];
 981
 982         if (!node)
 983                 return;
 984
 985         pfx = strrep("  ", level);
 986         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
 987
 988         if (node->type == BUS_MATCH_VALUE) {
 989                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 990                         printf(" <%u>\n", node->value.u8);
 991                 else
 992                         printf(" <%s>\n", node->value.str);
 993         } else if (node->type == BUS_MATCH_ROOT)
 994                 puts(" root");
 995         else if (node->type == BUS_MATCH_LEAF)
 996                 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
 997         else
 998                 putchar('\n');
 999
1000         if (BUS_MATCH_CAN_HASH(node->type)) {
1001                 Iterator i;
1002
1003                 HASHMAP_FOREACH(c, node->compare.children, i)
1004                         bus_match_dump(c, level + 1);
1005         }
1006
1007         for (c = node->child; c; c = c->next)
1008                 bus_match_dump(c, level + 1);
1009 }