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