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