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