Pileus Git - ~andy/gtk/blob - gtk/gtkcssselector.c

   1 /* GTK - The GIMP Toolkit
   2  * Copyright (C) 2011 Benjamin Otte <otte@gnome.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include "config.h"
  19
  20 #include "gtkcssselectorprivate.h"
  21
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "gtkcssprovider.h"
  26 #include "gtkstylecontextprivate.h"
  27
  28 typedef struct _GtkCssSelectorClass GtkCssSelectorClass;
  29
  30 struct _GtkCssSelectorClass {
  31   const char        *name;
  32
  33   void              (* print)       (const GtkCssSelector       *selector,
  34                                      GString                    *string);
  35   gboolean          (* match)       (const GtkCssSelector       *selector,
  36                                      const GtkCssMatcher        *matcher);
  37   void              (* tree_match)  (const GtkCssSelectorTree   *tree,
  38                                      const GtkCssMatcher        *matcher,
  39                                      GHashTable                  *res);
  40   GtkCssChange      (* get_change)  (const GtkCssSelector       *selector);
  41
  42   guint         increase_id_specificity :1;
  43   guint         increase_class_specificity :1;
  44   guint         increase_element_specificity :1;
  45   guint         is_simple :1;
  46   guint         must_keep_order :1; /* Due to region weirdness these must be kept before a DESCENDANT, so don't reorder */
  47 };
  48
  49 struct _GtkCssSelector
  50 {
  51   const GtkCssSelectorClass *class;       /* type of check this selector does */
  52   gconstpointer              data;        /* data for matching:
  53                                              - interned string for CLASS, NAME and ID
  54                                              - GUINT_TO_POINTER() for PSEUDOCLASS_REGION/STATE */
  55 };
  56
  57 struct _GtkCssSelectorTree
  58 {
  59   GtkCssSelector selector;
  60   GtkCssSelectorTree *parent;
  61   GtkCssSelectorTree *previous;
  62   GtkCssSelectorTree *siblings;
  63   gpointer *matches; /* pointers that we return as matches if selector matches */
  64 };
  65
  66 static gboolean
  67 gtk_css_selector_equal (const GtkCssSelector *a,
  68                         const GtkCssSelector *b)
  69 {
  70   return
  71     a->class == b->class &&
  72     a->data == b->data;
  73 }
  74
  75 static guint
  76 gtk_css_selector_hash (const GtkCssSelector *selector)
  77 {
  78   return GPOINTER_TO_UINT (selector->class) ^ GPOINTER_TO_UINT (selector->data);
  79 }
  80
  81 static void
  82 gtk_css_selector_tree_found_match (const GtkCssSelectorTree *tree,
  83                                    GHashTable *res)
  84 {
  85   int i;
  86
  87   if (tree->matches)
  88     {
  89       for (i = 0; tree->matches[i] != NULL; i++)
  90         g_hash_table_insert (res, tree->matches[i], tree->matches[i]);
  91     }
  92 }
  93
  94 static void
  95 gtk_css_selector_tree_match (const GtkCssSelectorTree *tree,
  96                              const GtkCssMatcher  *matcher,
  97                              GHashTable *res)
  98 {
  99   if (tree == NULL)
 100     return;
 101
 102   tree->selector.class->tree_match (tree, matcher, res);
 103 }
 104
 105 static gboolean
 106 gtk_css_selector_match (const GtkCssSelector *selector,
 107                         const GtkCssMatcher  *matcher)
 108 {
 109   if (selector == NULL)
 110     return TRUE;
 111
 112   return selector->class->match (selector, matcher);
 113 }
 114
 115 static GtkCssChange
 116 gtk_css_selector_get_change (const GtkCssSelector *selector)
 117 {
 118   if (selector == NULL)
 119     return 0;
 120
 121   return selector->class->get_change (selector);
 122 }
 123
 124 static const GtkCssSelector *
 125 gtk_css_selector_previous (const GtkCssSelector *selector)
 126 {
 127   selector = selector + 1;
 128
 129   return selector->class ? selector : NULL;
 130 }
 131
 132 /* DESCENDANT */
 133
 134 static void
 135 gtk_css_selector_descendant_print (const GtkCssSelector *selector,
 136                                    GString              *string)
 137 {
 138   g_string_append_c (string, ' ');
 139 }
 140
 141 static gboolean
 142 gtk_css_selector_descendant_match (const GtkCssSelector *selector,
 143                                    const GtkCssMatcher  *matcher)
 144 {
 145   GtkCssMatcher ancestor;
 146
 147   while (_gtk_css_matcher_get_parent (&ancestor, matcher))
 148     {
 149       matcher = &ancestor;
 150
 151       if (gtk_css_selector_match (gtk_css_selector_previous (selector), matcher))
 152         return TRUE;
 153     }
 154
 155   return FALSE;
 156 }
 157
 158 static void
 159 gtk_css_selector_descendant_tree_match (const GtkCssSelectorTree *tree,
 160                                         const GtkCssMatcher  *matcher,
 161                                         GHashTable *res)
 162 {
 163   GtkCssMatcher ancestor;
 164   const GtkCssSelectorTree *prev;
 165
 166   while (_gtk_css_matcher_get_parent (&ancestor, matcher))
 167     {
 168       matcher = &ancestor;
 169
 170       for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 171         gtk_css_selector_tree_match (prev, matcher, res);
 172
 173       /* any matchers are dangerous here, as we may loop forever, but
 174          we can terminate now as all possible matches have already been added */
 175       if (_gtk_css_matcher_matches_any (matcher))
 176         break;
 177     }
 178 }
 179
 180 static GtkCssChange
 181 gtk_css_selector_descendant_get_change (const GtkCssSelector *selector)
 182 {
 183   return _gtk_css_change_for_child (gtk_css_selector_get_change (gtk_css_selector_previous (selector)));
 184 }
 185
 186 static const GtkCssSelectorClass GTK_CSS_SELECTOR_DESCENDANT = {
 187   "descendant",
 188   gtk_css_selector_descendant_print,
 189   gtk_css_selector_descendant_match,
 190   gtk_css_selector_descendant_tree_match,
 191   gtk_css_selector_descendant_get_change,
 192   FALSE, FALSE, FALSE, FALSE, FALSE
 193 };
 194
 195 /* CHILD */
 196
 197 static void
 198 gtk_css_selector_child_print (const GtkCssSelector *selector,
 199                               GString              *string)
 200 {
 201   g_string_append (string, " > ");
 202 }
 203
 204 static gboolean
 205 gtk_css_selector_child_match (const GtkCssSelector *selector,
 206                               const GtkCssMatcher  *matcher)
 207 {
 208   GtkCssMatcher parent;
 209
 210   if (!_gtk_css_matcher_get_parent (&parent, matcher))
 211     return FALSE;
 212
 213   return gtk_css_selector_match (gtk_css_selector_previous (selector), &parent);
 214 }
 215
 216 static void
 217 gtk_css_selector_child_tree_match (const GtkCssSelectorTree *tree,
 218                                    const GtkCssMatcher  *matcher,
 219                                    GHashTable *res)
 220 {
 221   GtkCssMatcher parent;
 222   const GtkCssSelectorTree *prev;
 223
 224   if (!_gtk_css_matcher_get_parent (&parent, matcher))
 225     return;
 226
 227   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 228     gtk_css_selector_tree_match (prev, &parent, res);
 229 }
 230
 231 static GtkCssChange
 232 gtk_css_selector_child_get_change (const GtkCssSelector *selector)
 233 {
 234   return _gtk_css_change_for_child (gtk_css_selector_get_change (gtk_css_selector_previous (selector)));
 235 }
 236
 237 static const GtkCssSelectorClass GTK_CSS_SELECTOR_CHILD = {
 238   "child",
 239   gtk_css_selector_child_print,
 240   gtk_css_selector_child_match,
 241   gtk_css_selector_child_tree_match,
 242   gtk_css_selector_child_get_change,
 243   FALSE, FALSE, FALSE, FALSE, FALSE
 244 };
 245
 246 /* SIBLING */
 247
 248 static void
 249 gtk_css_selector_sibling_print (const GtkCssSelector *selector,
 250                                 GString              *string)
 251 {
 252   g_string_append (string, " ~ ");
 253 }
 254
 255 static gboolean
 256 gtk_css_selector_sibling_match (const GtkCssSelector *selector,
 257                                 const GtkCssMatcher  *matcher)
 258 {
 259   GtkCssMatcher previous;
 260
 261   while (_gtk_css_matcher_get_previous (&previous, matcher))
 262     {
 263       matcher = &previous;
 264
 265       if (gtk_css_selector_match (gtk_css_selector_previous (selector), matcher))
 266         return TRUE;
 267     }
 268
 269   return FALSE;
 270 }
 271
 272 static void
 273 gtk_css_selector_sibling_tree_match (const GtkCssSelectorTree *tree,
 274                                      const GtkCssMatcher  *matcher,
 275                                      GHashTable *res)
 276 {
 277   GtkCssMatcher previous;
 278   const GtkCssSelectorTree *prev;
 279
 280   while (_gtk_css_matcher_get_previous (&previous, matcher))
 281     {
 282       matcher = &previous;
 283
 284       for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 285         gtk_css_selector_tree_match (prev, matcher, res);
 286
 287       /* any matchers are dangerous here, as we may loop forever, but
 288          we can terminate now as all possible matches have already been added */
 289       if (_gtk_css_matcher_matches_any (matcher))
 290         break;
 291     }
 292 }
 293
 294 static GtkCssChange
 295 gtk_css_selector_sibling_get_change (const GtkCssSelector *selector)
 296 {
 297   return _gtk_css_change_for_sibling (gtk_css_selector_get_change (gtk_css_selector_previous (selector)));
 298 }
 299
 300 static const GtkCssSelectorClass GTK_CSS_SELECTOR_SIBLING = {
 301   "sibling",
 302   gtk_css_selector_sibling_print,
 303   gtk_css_selector_sibling_match,
 304   gtk_css_selector_sibling_tree_match,
 305   gtk_css_selector_sibling_get_change,
 306   FALSE, FALSE, FALSE, FALSE, FALSE
 307 };
 308
 309 /* ADJACENT */
 310
 311 static void
 312 gtk_css_selector_adjacent_print (const GtkCssSelector *selector,
 313                                  GString              *string)
 314 {
 315   g_string_append (string, " + ");
 316 }
 317
 318 static gboolean
 319 gtk_css_selector_adjacent_match (const GtkCssSelector *selector,
 320                                  const GtkCssMatcher  *matcher)
 321 {
 322   GtkCssMatcher previous;
 323
 324   if (!_gtk_css_matcher_get_previous (&previous, matcher))
 325     return FALSE;
 326
 327   return gtk_css_selector_match (gtk_css_selector_previous (selector), &previous);
 328 }
 329
 330 static void
 331 gtk_css_selector_adjacent_tree_match (const GtkCssSelectorTree *tree,
 332                                       const GtkCssMatcher  *matcher,
 333                                       GHashTable *res)
 334 {
 335   GtkCssMatcher previous;
 336   const GtkCssSelectorTree *prev;
 337
 338   if (!_gtk_css_matcher_get_previous (&previous, matcher))
 339     return;
 340
 341   matcher = &previous;
 342
 343   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 344     gtk_css_selector_tree_match (prev, matcher, res);
 345 }
 346
 347 static GtkCssChange
 348 gtk_css_selector_adjacent_get_change (const GtkCssSelector *selector)
 349 {
 350   return _gtk_css_change_for_sibling (gtk_css_selector_get_change (gtk_css_selector_previous (selector)));
 351 }
 352
 353 static const GtkCssSelectorClass GTK_CSS_SELECTOR_ADJACENT = {
 354   "adjacent",
 355   gtk_css_selector_adjacent_print,
 356   gtk_css_selector_adjacent_match,
 357   gtk_css_selector_adjacent_tree_match,
 358   gtk_css_selector_adjacent_get_change,
 359   FALSE, FALSE, FALSE, FALSE, FALSE
 360 };
 361
 362 /* ANY */
 363
 364 static void
 365 gtk_css_selector_any_print (const GtkCssSelector *selector,
 366                             GString              *string)
 367 {
 368   g_string_append_c (string, '*');
 369 }
 370
 371 static gboolean
 372 gtk_css_selector_any_match (const GtkCssSelector *selector,
 373                             const GtkCssMatcher  *matcher)
 374 {
 375   const GtkCssSelector *previous = gtk_css_selector_previous (selector);
 376
 377   if (previous &&
 378       previous->class == &GTK_CSS_SELECTOR_DESCENDANT &&
 379       _gtk_css_matcher_has_regions (matcher))
 380     {
 381       if (gtk_css_selector_match (gtk_css_selector_previous (previous), matcher))
 382         return TRUE;
 383     }
 384
 385   return gtk_css_selector_match (previous, matcher);
 386 }
 387
 388 static void
 389 gtk_css_selector_any_tree_match (const GtkCssSelectorTree *tree,
 390                                  const GtkCssMatcher  *matcher,
 391                                  GHashTable *res)
 392 {
 393   const GtkCssSelectorTree *prev, *prev2;
 394
 395   gtk_css_selector_tree_found_match (tree, res);
 396
 397   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 398     {
 399       if (prev->selector.class == &GTK_CSS_SELECTOR_DESCENDANT &&
 400           _gtk_css_matcher_has_regions (matcher))
 401         {
 402           for (prev2 = prev->previous; prev2 != NULL; prev2 = prev2->siblings)
 403             gtk_css_selector_tree_match (prev2, matcher, res);
 404         }
 405
 406       gtk_css_selector_tree_match (prev, matcher, res);
 407     }
 408 }
 409
 410 static GtkCssChange
 411 gtk_css_selector_any_get_change (const GtkCssSelector *selector)
 412 {
 413   return gtk_css_selector_get_change (gtk_css_selector_previous (selector));
 414 }
 415
 416 static const GtkCssSelectorClass GTK_CSS_SELECTOR_ANY = {
 417   "any",
 418   gtk_css_selector_any_print,
 419   gtk_css_selector_any_match,
 420   gtk_css_selector_any_tree_match,
 421   gtk_css_selector_any_get_change,
 422   FALSE, FALSE, FALSE, TRUE, TRUE
 423 };
 424
 425 /* NAME */
 426
 427 static void
 428 gtk_css_selector_name_print (const GtkCssSelector *selector,
 429                              GString              *string)
 430 {
 431   g_string_append (string, selector->data);
 432 }
 433
 434 static gboolean
 435 gtk_css_selector_name_match (const GtkCssSelector *selector,
 436                              const GtkCssMatcher  *matcher)
 437 {
 438   if (!_gtk_css_matcher_has_name (matcher, selector->data))
 439     return FALSE;
 440
 441   return gtk_css_selector_match (gtk_css_selector_previous (selector), matcher);
 442 }
 443
 444 static void
 445 gtk_css_selector_name_tree_match (const GtkCssSelectorTree *tree,
 446                                   const GtkCssMatcher  *matcher,
 447                                   GHashTable *res)
 448 {
 449   const GtkCssSelectorTree *prev;
 450
 451   if (!_gtk_css_matcher_has_name (matcher, tree->selector.data))
 452     return;
 453
 454   gtk_css_selector_tree_found_match (tree, res);
 455
 456   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 457     gtk_css_selector_tree_match (prev, matcher, res);
 458 }
 459
 460
 461 static GtkCssChange
 462 gtk_css_selector_name_get_change (const GtkCssSelector *selector)
 463 {
 464   return gtk_css_selector_get_change (gtk_css_selector_previous (selector)) | GTK_CSS_CHANGE_NAME;
 465 }
 466
 467 static const GtkCssSelectorClass GTK_CSS_SELECTOR_NAME = {
 468   "name",
 469   gtk_css_selector_name_print,
 470   gtk_css_selector_name_match,
 471   gtk_css_selector_name_tree_match,
 472   gtk_css_selector_name_get_change,
 473   FALSE, FALSE, TRUE, TRUE, FALSE
 474 };
 475
 476 /* REGION */
 477
 478 static void
 479 gtk_css_selector_region_print (const GtkCssSelector *selector,
 480                                GString              *string)
 481 {
 482   g_string_append (string, selector->data);
 483 }
 484
 485 static gboolean
 486 gtk_css_selector_region_match (const GtkCssSelector *selector,
 487                                const GtkCssMatcher  *matcher)
 488 {
 489   const GtkCssSelector *previous;
 490
 491   if (!_gtk_css_matcher_has_region (matcher, selector->data, 0))
 492     return FALSE;
 493
 494   previous = gtk_css_selector_previous (selector);
 495   if (previous && previous->class == &GTK_CSS_SELECTOR_DESCENDANT &&
 496       gtk_css_selector_match (gtk_css_selector_previous (previous), matcher))
 497     return TRUE;
 498
 499   return gtk_css_selector_match (previous, matcher);
 500 }
 501
 502 static void
 503 gtk_css_selector_region_tree_match (const GtkCssSelectorTree *tree,
 504                                     const GtkCssMatcher  *matcher,
 505                                     GHashTable *res)
 506 {
 507   const GtkCssSelectorTree *prev, *prev2;
 508
 509   if (!_gtk_css_matcher_has_region (matcher, tree->selector.data, 0))
 510     return;
 511
 512   gtk_css_selector_tree_found_match (tree, res);
 513
 514   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 515     {
 516       if (prev->selector.class == &GTK_CSS_SELECTOR_DESCENDANT)
 517         {
 518           for (prev2 = prev->previous; prev2 != NULL; prev2 = prev2->siblings)
 519             gtk_css_selector_tree_match (prev2, matcher, res);
 520         }
 521
 522       gtk_css_selector_tree_match (prev, matcher, res);
 523     }
 524 }
 525
 526 static GtkCssChange
 527 gtk_css_selector_region_get_change (const GtkCssSelector *selector)
 528 {
 529   GtkCssChange change;
 530
 531   change = gtk_css_selector_get_change (gtk_css_selector_previous (selector));
 532   change |= GTK_CSS_CHANGE_REGION;
 533   change |= _gtk_css_change_for_child (change);
 534
 535   return change;
 536 }
 537
 538 static const GtkCssSelectorClass GTK_CSS_SELECTOR_REGION = {
 539   "region",
 540   gtk_css_selector_region_print,
 541   gtk_css_selector_region_match,
 542   gtk_css_selector_region_tree_match,
 543   gtk_css_selector_region_get_change,
 544   FALSE, FALSE, TRUE, TRUE, TRUE
 545 };
 546
 547 /* CLASS */
 548
 549 static void
 550 gtk_css_selector_class_print (const GtkCssSelector *selector,
 551                               GString              *string)
 552 {
 553   g_string_append_c (string, '.');
 554   g_string_append (string, g_quark_to_string (GPOINTER_TO_UINT (selector->data)));
 555 }
 556
 557 static gboolean
 558 gtk_css_selector_class_match (const GtkCssSelector *selector,
 559                               const GtkCssMatcher  *matcher)
 560 {
 561   if (!_gtk_css_matcher_has_class (matcher, GPOINTER_TO_UINT (selector->data)))
 562     return FALSE;
 563
 564   return gtk_css_selector_match (gtk_css_selector_previous (selector), matcher);
 565 }
 566
 567 static void
 568 gtk_css_selector_class_tree_match (const GtkCssSelectorTree *tree,
 569                                    const GtkCssMatcher  *matcher,
 570                                    GHashTable *res)
 571 {
 572   const GtkCssSelectorTree *prev;
 573
 574   if (!_gtk_css_matcher_has_class (matcher, GPOINTER_TO_UINT (tree->selector.data)))
 575     return;
 576
 577   gtk_css_selector_tree_found_match (tree, res);
 578
 579   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 580     gtk_css_selector_tree_match (prev, matcher, res);
 581 }
 582
 583 static GtkCssChange
 584 gtk_css_selector_class_get_change (const GtkCssSelector *selector)
 585 {
 586   return gtk_css_selector_get_change (gtk_css_selector_previous (selector)) | GTK_CSS_CHANGE_CLASS;
 587 }
 588
 589 static const GtkCssSelectorClass GTK_CSS_SELECTOR_CLASS = {
 590   "class",
 591   gtk_css_selector_class_print,
 592   gtk_css_selector_class_match,
 593   gtk_css_selector_class_tree_match,
 594   gtk_css_selector_class_get_change,
 595   FALSE, TRUE, FALSE, TRUE, FALSE
 596 };
 597
 598 /* ID */
 599
 600 static void
 601 gtk_css_selector_id_print (const GtkCssSelector *selector,
 602                            GString              *string)
 603 {
 604   g_string_append_c (string, '#');
 605   g_string_append (string, selector->data);
 606 }
 607
 608 static gboolean
 609 gtk_css_selector_id_match (const GtkCssSelector *selector,
 610                            const GtkCssMatcher  *matcher)
 611 {
 612   if (!_gtk_css_matcher_has_id (matcher, selector->data))
 613     return FALSE;
 614
 615   return gtk_css_selector_match (gtk_css_selector_previous (selector), matcher);
 616 }
 617
 618 static void
 619 gtk_css_selector_id_tree_match (const GtkCssSelectorTree *tree,
 620                                 const GtkCssMatcher  *matcher,
 621                                 GHashTable *res)
 622 {
 623   const GtkCssSelectorTree *prev;
 624
 625   if (!_gtk_css_matcher_has_id (matcher, tree->selector.data))
 626     return;
 627
 628   gtk_css_selector_tree_found_match (tree, res);
 629
 630   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 631     gtk_css_selector_tree_match (prev, matcher, res);
 632 }
 633
 634 static GtkCssChange
 635 gtk_css_selector_id_get_change (const GtkCssSelector *selector)
 636 {
 637   return gtk_css_selector_get_change (gtk_css_selector_previous (selector)) | GTK_CSS_CHANGE_ID;
 638 }
 639
 640 static const GtkCssSelectorClass GTK_CSS_SELECTOR_ID = {
 641   "id",
 642   gtk_css_selector_id_print,
 643   gtk_css_selector_id_match,
 644   gtk_css_selector_id_tree_match,
 645   gtk_css_selector_id_get_change,
 646   TRUE, FALSE, FALSE, TRUE, FALSE
 647 };
 648
 649 /* PSEUDOCLASS FOR STATE */
 650
 651 static void
 652 gtk_css_selector_pseudoclass_state_print (const GtkCssSelector *selector,
 653                                           GString              *string)
 654 {
 655   static const char * state_names[] = {
 656     "active",
 657     "hover",
 658     "selected",
 659     "insensitive",
 660     "inconsistent",
 661     "focus",
 662     "backdrop"
 663   };
 664   guint i, state;
 665
 666   state = GPOINTER_TO_UINT (selector->data);
 667   g_string_append_c (string, ':');
 668
 669   for (i = 0; i < G_N_ELEMENTS (state_names); i++)
 670     {
 671       if (state == (1 << i))
 672         {
 673           g_string_append (string, state_names[i]);
 674           return;
 675         }
 676     }
 677
 678   g_assert_not_reached ();
 679 }
 680
 681 static gboolean
 682 gtk_css_selector_pseudoclass_state_match (const GtkCssSelector *selector,
 683                                           const GtkCssMatcher  *matcher)
 684 {
 685   GtkStateFlags state = GPOINTER_TO_UINT (selector->data);
 686
 687   if ((_gtk_css_matcher_get_state (matcher) & state) != state)
 688     return FALSE;
 689
 690   return gtk_css_selector_match (gtk_css_selector_previous (selector), matcher);
 691 }
 692
 693 static void
 694 gtk_css_selector_pseudoclass_state_tree_match (const GtkCssSelectorTree *tree,
 695                                                const GtkCssMatcher  *matcher,
 696                                                GHashTable *res)
 697 {
 698   GtkStateFlags state = GPOINTER_TO_UINT (tree->selector.data);
 699   const GtkCssSelectorTree *prev;
 700
 701   if ((_gtk_css_matcher_get_state (matcher) & state) != state)
 702     return;
 703
 704   gtk_css_selector_tree_found_match (tree, res);
 705
 706   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
 707     gtk_css_selector_tree_match (prev, matcher, res);
 708 }
 709
 710
 711 static GtkCssChange
 712 gtk_css_selector_pseudoclass_state_get_change (const GtkCssSelector *selector)
 713 {
 714   return gtk_css_selector_get_change (gtk_css_selector_previous (selector)) | GTK_CSS_CHANGE_STATE;
 715 }
 716
 717 static const GtkCssSelectorClass GTK_CSS_SELECTOR_PSEUDOCLASS_STATE = {
 718   "pseudoclass-state",
 719   gtk_css_selector_pseudoclass_state_print,
 720   gtk_css_selector_pseudoclass_state_match,
 721   gtk_css_selector_pseudoclass_state_tree_match,
 722   gtk_css_selector_pseudoclass_state_get_change,
 723   FALSE, TRUE, FALSE, TRUE, FALSE
 724 };
 725
 726 /* PSEUDOCLASS FOR POSITION */
 727
 728 typedef enum {
 729   POSITION_FORWARD,
 730   POSITION_BACKWARD,
 731   POSITION_ONLY,
 732   POSITION_SORTED
 733 } PositionType;
 734 #define POSITION_TYPE_BITS 2
 735 #define POSITION_NUMBER_BITS ((sizeof (gpointer) * 8 - POSITION_TYPE_BITS) / 2)
 736
 737 static gconstpointer
 738 encode_position (PositionType type,
 739                  int          a,
 740                  int          b)
 741 {
 742   union {
 743     gconstpointer p;
 744     struct {
 745       gssize type :POSITION_TYPE_BITS;
 746       gssize a :POSITION_NUMBER_BITS;
 747       gssize b :POSITION_NUMBER_BITS;
 748     } data;
 749   } result;
 750   G_STATIC_ASSERT (sizeof (gconstpointer) == sizeof (result));
 751
 752   g_assert (type < (1 << POSITION_TYPE_BITS));
 753
 754   result.data.type = type;
 755   result.data.a = a;
 756   result.data.b = b;
 757
 758   return result.p;
 759 }
 760
 761 static void
 762 decode_position (const GtkCssSelector *selector,
 763                  PositionType         *type,
 764                  int                  *a,
 765                  int                  *b)
 766 {
 767   union {
 768     gconstpointer p;
 769     struct {
 770       gssize type :POSITION_TYPE_BITS;
 771       gssize a :POSITION_NUMBER_BITS;
 772       gssize b :POSITION_NUMBER_BITS;
 773     } data;
 774   } result;
 775   G_STATIC_ASSERT (sizeof (gconstpointer) == sizeof (result));
 776
 777   result.p = selector->data;
 778
 779   *type = result.data.type & ((1 << POSITION_TYPE_BITS) - 1);
 780   *a = result.data.a;
 781   *b = result.data.b;
 782 }
 783
 784 static void
 785 gtk_css_selector_pseudoclass_position_print (const GtkCssSelector *selector,
 786                                              GString              *string)
 787 {
 788   PositionType type;
 789   int a, b;
 790
 791   decode_position (selector, &type, &a, &b);
 792   switch (type)
 793     {
 794     case POSITION_FORWARD:
 795       if (a == 0)
 796         {
 797           if (b == 1)
 798             g_string_append (string, ":first-child");
 799           else
 800             g_string_append_printf (string, ":nth-child(%d)", b);
 801         }
 802       else if (a == 2 && b == 0)
 803         g_string_append (string, ":nth-child(even)");
 804       else if (a == 2 && b == 1)
 805         g_string_append (string, ":nth-child(odd)");
 806       else
 807         {
 808           g_string_append (string, ":nth-child(");
 809           if (a == 1)
 810             g_string_append (string, "n");
 811           else if (a == -1)
 812             g_string_append (string, "-n");
 813           else
 814             g_string_append_printf (string, "%dn", a);
 815           if (b > 0)
 816             g_string_append_printf (string, "+%d)", b);
 817           else if (b < 0)
 818             g_string_append_printf (string, "%d)", b);
 819           else
 820             g_string_append (string, ")");
 821         }
 822       break;
 823     case POSITION_BACKWARD:
 824       if (a == 0)
 825         {
 826           if (b == 1)
 827             g_string_append (string, ":last-child");
 828           else
 829             g_string_append_printf (string, ":nth-last-child(%d)", b);
 830         }
 831       else if (a == 2 && b == 0)
 832         g_string_append (string, ":nth-last-child(even)");
 833       else if (a == 2 && b == 1)
 834         g_string_append (string, ":nth-last-child(odd)");
 835       else
 836         {
 837           g_string_append (string, ":nth-last-child(");
 838           if (a == 1)
 839             g_string_append (string, "n");
 840           else if (a == -1)
 841             g_string_append (string, "-n");
 842           else
 843             g_string_append_printf (string, "%dn", a);
 844           if (b > 0)
 845             g_string_append_printf (string, "+%d)", b);
 846           else if (b < 0)
 847             g_string_append_printf (string, "%d)", b);
 848           else
 849             g_string_append (string, ")");
 850         }
 851       break;
 852     case POSITION_ONLY:
 853       g_string_append (string, ":only-child");
 854       break;
 855     case POSITION_SORTED:
 856       g_string_append (string, ":sorted");
 857       break;
 858     default:
 859       g_assert_not_reached ();
 860       break;
 861     }
 862 }
 863
 864 static gboolean
 865 gtk_css_selector_pseudoclass_position_match_for_region (const GtkCssSelector *selector,
 866                                                         const GtkCssMatcher  *matcher)
 867 {
 868   GtkRegionFlags selector_flags;
 869   const GtkCssSelector *previous;
 870   PositionType type;
 871   int a, b;
 872
 873   decode_position (selector, &type, &a, &b);
 874   switch (type)
 875     {
 876     case POSITION_FORWARD:
 877       if (a == 0 && b == 1)
 878         selector_flags = GTK_REGION_FIRST;
 879       else if (a == 2 && b == 0)
 880         selector_flags = GTK_REGION_EVEN;
 881       else if (a == 2 && b == 1)
 882         selector_flags = GTK_REGION_ODD;
 883       else
 884         return FALSE;
 885       break;
 886     case POSITION_BACKWARD:
 887       if (a == 0 && b == 1)
 888         selector_flags = GTK_REGION_LAST;
 889       else
 890         return FALSE;
 891       break;
 892     case POSITION_ONLY:
 893       selector_flags = GTK_REGION_ONLY;
 894       break;
 895     case POSITION_SORTED:
 896       selector_flags = GTK_REGION_SORTED;
 897       break;
 898     default:
 899       g_assert_not_reached ();
 900       break;
 901     }
 902   selector = gtk_css_selector_previous (selector);
 903
 904   if (!_gtk_css_matcher_has_region (matcher, selector->data, selector_flags))
 905     return FALSE;
 906
 907   previous = gtk_css_selector_previous (selector);
 908   if (previous && previous->class == &GTK_CSS_SELECTOR_DESCENDANT &&
 909       gtk_css_selector_match (gtk_css_selector_previous (previous), matcher))
 910     return TRUE;
 911
 912   return gtk_css_selector_match (previous, matcher);
 913 }
 914
 915 static gboolean
 916 gtk_css_selector_pseudoclass_position_match (const GtkCssSelector *selector,
 917                                              const GtkCssMatcher  *matcher)
 918 {
 919   const GtkCssSelector *previous;
 920   PositionType type;
 921   int a, b;
 922
 923   previous = gtk_css_selector_previous (selector);
 924   if (previous && previous->class == &GTK_CSS_SELECTOR_REGION)
 925     return gtk_css_selector_pseudoclass_position_match_for_region (selector, matcher);
 926
 927   decode_position (selector, &type, &a, &b);
 928   switch (type)
 929     {
 930     case POSITION_FORWARD:
 931       if (!_gtk_css_matcher_has_position (matcher, TRUE, a, b))
 932         return FALSE;
 933       break;
 934     case POSITION_BACKWARD:
 935       if (!_gtk_css_matcher_has_position (matcher, FALSE, a, b))
 936         return FALSE;
 937       break;
 938     case POSITION_ONLY:
 939       if (!_gtk_css_matcher_has_position (matcher, TRUE, 0, 1) ||
 940           !_gtk_css_matcher_has_position (matcher, FALSE, 0, 1))
 941         return FALSE;
 942       break;
 943     case POSITION_SORTED:
 944       return FALSE;
 945     default:
 946       g_assert_not_reached ();
 947       return FALSE;
 948     }
 949
 950   return gtk_css_selector_match (previous, matcher);
 951 }
 952
 953 static void
 954 gtk_css_selector_pseudoclass_position_tree_match_for_region (const GtkCssSelectorTree *tree,
 955                                                              const GtkCssSelectorTree *prev,
 956                                                              const GtkCssMatcher  *matcher,
 957                                                              GHashTable *res)
 958 {
 959   const GtkCssSelectorTree *prev2;
 960   GtkRegionFlags selector_flags;
 961   PositionType type;
 962   int a, b;
 963
 964   decode_position (&tree->selector, &type, &a, &b);
 965   switch (type)
 966     {
 967     case POSITION_FORWARD:
 968       if (a == 0 && b == 1)
 969         selector_flags = GTK_REGION_FIRST;
 970       else if (a == 2 && b == 0)
 971         selector_flags = GTK_REGION_EVEN;
 972       else if (a == 2 && b == 1)
 973         selector_flags = GTK_REGION_ODD;
 974       else
 975         return;
 976       break;
 977     case POSITION_BACKWARD:
 978       if (a == 0 && b == 1)
 979         selector_flags = GTK_REGION_LAST;
 980       else
 981         return;
 982       break;
 983     case POSITION_ONLY:
 984       selector_flags = GTK_REGION_ONLY;
 985       break;
 986     case POSITION_SORTED:
 987       selector_flags = GTK_REGION_SORTED;
 988       break;
 989     default:
 990       g_assert_not_reached ();
 991       break;
 992     }
 993
 994   if (!_gtk_css_matcher_has_region (matcher, prev->selector.data, selector_flags))
 995     return;
 996
 997   gtk_css_selector_tree_found_match (prev, res);
 998
 999   for (prev2 = prev->previous; prev2 != NULL; prev2 = prev2->siblings)
1000     {
1001       if (prev2->selector.class == &GTK_CSS_SELECTOR_DESCENDANT)
1002         gtk_css_selector_tree_match (prev2->previous, matcher, res);
1003       gtk_css_selector_tree_match (prev2, matcher, res);
1004     }
1005 }
1006
1007 static void
1008 gtk_css_selector_pseudoclass_position_tree_match (const GtkCssSelectorTree *tree,
1009                                                   const GtkCssMatcher  *matcher,
1010                                                   GHashTable *res)
1011 {
1012   const GtkCssSelectorTree *prev;
1013   PositionType type;
1014   int a, b;
1015
1016   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
1017     {
1018       if (prev->selector.class == &GTK_CSS_SELECTOR_REGION)
1019         gtk_css_selector_pseudoclass_position_tree_match_for_region (tree, prev, matcher, res);
1020     }
1021
1022   decode_position (&tree->selector, &type, &a, &b);
1023   switch (type)
1024     {
1025     case POSITION_FORWARD:
1026       if (!_gtk_css_matcher_has_position (matcher, TRUE, a, b))
1027         return;
1028       break;
1029     case POSITION_BACKWARD:
1030       if (!_gtk_css_matcher_has_position (matcher, FALSE, a, b))
1031         return;
1032       break;
1033     case POSITION_ONLY:
1034       if (!_gtk_css_matcher_has_position (matcher, TRUE, 0, 1) ||
1035           !_gtk_css_matcher_has_position (matcher, FALSE, 0, 1))
1036         return;
1037       break;
1038     case POSITION_SORTED:
1039       return;
1040     default:
1041       g_assert_not_reached ();
1042       return;
1043     }
1044
1045   gtk_css_selector_tree_found_match (tree, res);
1046
1047   for (prev = tree->previous; prev != NULL; prev = prev->siblings)
1048     {
1049       if (prev->selector.class != &GTK_CSS_SELECTOR_REGION)
1050         gtk_css_selector_tree_match (prev, matcher, res);
1051     }
1052 }
1053
1054 static GtkCssChange
1055 gtk_css_selector_pseudoclass_position_get_change (const GtkCssSelector *selector)
1056 {
1057   return gtk_css_selector_get_change (gtk_css_selector_previous (selector)) | GTK_CSS_CHANGE_POSITION;
1058 }
1059
1060 static const GtkCssSelectorClass GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION = {
1061   "pseudoclass-position",
1062   gtk_css_selector_pseudoclass_position_print,
1063   gtk_css_selector_pseudoclass_position_match,
1064   gtk_css_selector_pseudoclass_position_tree_match,
1065   gtk_css_selector_pseudoclass_position_get_change,
1066   FALSE, TRUE, FALSE, TRUE, TRUE
1067 };
1068
1069 /* API */
1070
1071 static guint
1072 gtk_css_selector_size (const GtkCssSelector *selector)
1073 {
1074   guint size = 0;
1075
1076   while (selector)
1077     {
1078       selector = gtk_css_selector_previous (selector);
1079       size++;
1080     }
1081
1082   return size;
1083 }
1084
1085 static GtkCssSelector *
1086 gtk_css_selector_new (const GtkCssSelectorClass *class,
1087                       GtkCssSelector            *selector,
1088                       gconstpointer              data)
1089 {
1090   guint size;
1091
1092   size = gtk_css_selector_size (selector);
1093   selector = g_realloc (selector, sizeof (GtkCssSelector) * (size + 1) + sizeof (gpointer));
1094   if (size == 0)
1095     selector[1].class = NULL;
1096   else
1097     memmove (selector + 1, selector, sizeof (GtkCssSelector) * size + sizeof (gpointer));
1098
1099   selector->class = class;
1100   selector->data = data;
1101
1102   return selector;
1103 }
1104
1105 static GtkCssSelector *
1106 parse_selector_class (GtkCssParser *parser, GtkCssSelector *selector)
1107 {
1108   char *name;
1109
1110   name = _gtk_css_parser_try_name (parser, FALSE);
1111
1112   if (name == NULL)
1113     {
1114       _gtk_css_parser_error (parser, "Expected a valid name for class");
1115       if (selector)
1116         _gtk_css_selector_free (selector);
1117       return NULL;
1118     }
1119
1120   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_CLASS,
1121                                    selector,
1122                                    GUINT_TO_POINTER (g_quark_from_string (name)));
1123
1124   g_free (name);
1125
1126   return selector;
1127 }
1128
1129 static GtkCssSelector *
1130 parse_selector_id (GtkCssParser *parser, GtkCssSelector *selector)
1131 {
1132   char *name;
1133
1134   name = _gtk_css_parser_try_name (parser, FALSE);
1135
1136   if (name == NULL)
1137     {
1138       _gtk_css_parser_error (parser, "Expected a valid name for id");
1139       if (selector)
1140         _gtk_css_selector_free (selector);
1141       return NULL;
1142     }
1143
1144   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ID,
1145                                    selector,
1146                                    g_intern_string (name));
1147
1148   g_free (name);
1149
1150   return selector;
1151 }
1152
1153 static GtkCssSelector *
1154 parse_selector_pseudo_class_nth_child (GtkCssParser   *parser,
1155                                        GtkCssSelector *selector,
1156                                        PositionType    type)
1157 {
1158   int a, b;
1159
1160   if (!_gtk_css_parser_try (parser, "(", TRUE))
1161     {
1162       _gtk_css_parser_error (parser, "Missing opening bracket for pseudo-class");
1163       if (selector)
1164         _gtk_css_selector_free (selector);
1165       return NULL;
1166     }
1167
1168   if (_gtk_css_parser_try (parser, "even", TRUE))
1169     {
1170       a = 2;
1171       b = 0;
1172     }
1173   else if (_gtk_css_parser_try (parser, "odd", TRUE))
1174     {
1175       a = 2;
1176       b = 1;
1177     }
1178   else if (type == POSITION_FORWARD &&
1179            _gtk_css_parser_try (parser, "first", TRUE))
1180     {
1181       a = 0;
1182       b = 1;
1183     }
1184   else if (type == POSITION_FORWARD &&
1185            _gtk_css_parser_try (parser, "last", TRUE))
1186     {
1187       a = 0;
1188       b = 1;
1189       type = POSITION_BACKWARD;
1190     }
1191   else
1192     {
1193       int multiplier;
1194
1195       if (_gtk_css_parser_try (parser, "+", TRUE))
1196         multiplier = 1;
1197       else if (_gtk_css_parser_try (parser, "-", TRUE))
1198         multiplier = -1;
1199       else
1200         multiplier = 1;
1201
1202       if (_gtk_css_parser_try_int (parser, &a))
1203         {
1204           if (a < 0)
1205             {
1206               _gtk_css_parser_error (parser, "Expected an integer");
1207               if (selector)
1208                 _gtk_css_selector_free (selector);
1209               return NULL;
1210             }
1211           a *= multiplier;
1212         }
1213       else if (_gtk_css_parser_has_prefix (parser, "n"))
1214         {
1215           a = multiplier;
1216         }
1217       else
1218         {
1219           _gtk_css_parser_error (parser, "Expected an integer");
1220           if (selector)
1221             _gtk_css_selector_free (selector);
1222           return NULL;
1223         }
1224
1225       if (_gtk_css_parser_try (parser, "n", TRUE))
1226         {
1227           if (_gtk_css_parser_try (parser, "+", TRUE))
1228             multiplier = 1;
1229           else if (_gtk_css_parser_try (parser, "-", TRUE))
1230             multiplier = -1;
1231           else
1232             multiplier = 1;
1233
1234           if (_gtk_css_parser_try_int (parser, &b))
1235             {
1236               if (b < 0)
1237                 {
1238                   _gtk_css_parser_error (parser, "Expected an integer");
1239                   if (selector)
1240                     _gtk_css_selector_free (selector);
1241                   return NULL;
1242                 }
1243             }
1244           else
1245             b = 0;
1246
1247           b *= multiplier;
1248         }
1249       else
1250         {
1251           b = a;
1252           a = 0;
1253         }
1254     }
1255
1256   if (!_gtk_css_parser_try (parser, ")", FALSE))
1257     {
1258       _gtk_css_parser_error (parser, "Missing closing bracket for pseudo-class");
1259       if (selector)
1260         _gtk_css_selector_free (selector);
1261       return NULL;
1262     }
1263
1264   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION,
1265                                    selector,
1266                                    encode_position (type, a, b));
1267
1268   return selector;
1269 }
1270
1271 static GtkCssSelector *
1272 parse_selector_pseudo_class (GtkCssParser   *parser,
1273                              GtkCssSelector *selector)
1274 {
1275   static const struct {
1276     const char    *name;
1277     GtkStateFlags  state_flag;
1278     PositionType   position_type;
1279     int            position_a;
1280     int            position_b;
1281   } pseudo_classes[] = {
1282     { "first-child",  0,                           POSITION_FORWARD,  0, 1 },
1283     { "last-child",   0,                           POSITION_BACKWARD, 0, 1 },
1284     { "only-child",   0,                           POSITION_ONLY,     0, 0 },
1285     { "sorted",       0,                           POSITION_SORTED,   0, 0 },
1286     { "active",       GTK_STATE_FLAG_ACTIVE, },
1287     { "prelight",     GTK_STATE_FLAG_PRELIGHT, },
1288     { "hover",        GTK_STATE_FLAG_PRELIGHT, },
1289     { "selected",     GTK_STATE_FLAG_SELECTED, },
1290     { "insensitive",  GTK_STATE_FLAG_INSENSITIVE, },
1291     { "inconsistent", GTK_STATE_FLAG_INCONSISTENT, },
1292     { "focused",      GTK_STATE_FLAG_FOCUSED, },
1293     { "focus",        GTK_STATE_FLAG_FOCUSED, },
1294     { "backdrop",     GTK_STATE_FLAG_BACKDROP, }
1295   };
1296   guint i;
1297
1298   if (_gtk_css_parser_try (parser, "nth-child", FALSE))
1299     return parse_selector_pseudo_class_nth_child (parser, selector, POSITION_FORWARD);
1300   else if (_gtk_css_parser_try (parser, "nth-last-child", FALSE))
1301     return parse_selector_pseudo_class_nth_child (parser, selector, POSITION_BACKWARD);
1302
1303   for (i = 0; i < G_N_ELEMENTS (pseudo_classes); i++)
1304     {
1305       if (_gtk_css_parser_try (parser, pseudo_classes[i].name, FALSE))
1306         {
1307           if (pseudo_classes[i].state_flag)
1308             selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_STATE,
1309                                              selector,
1310                                              GUINT_TO_POINTER (pseudo_classes[i].state_flag));
1311           else
1312             selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION,
1313                                              selector,
1314                                              encode_position (pseudo_classes[i].position_type,
1315                                                               pseudo_classes[i].position_a,
1316                                                               pseudo_classes[i].position_b));
1317           return selector;
1318         }
1319     }
1320
1321   _gtk_css_parser_error (parser, "Missing name of pseudo-class");
1322   if (selector)
1323     _gtk_css_selector_free (selector);
1324   return NULL;
1325 }
1326
1327 static GtkCssSelector *
1328 try_parse_name (GtkCssParser   *parser,
1329                 GtkCssSelector *selector)
1330 {
1331   char *name;
1332
1333   name = _gtk_css_parser_try_ident (parser, FALSE);
1334   if (name)
1335     {
1336       selector = gtk_css_selector_new (_gtk_style_context_check_region_name (name)
1337                                        ? &GTK_CSS_SELECTOR_REGION
1338                                        : &GTK_CSS_SELECTOR_NAME,
1339                                        selector,
1340                                        g_intern_string (name));
1341       g_free (name);
1342     }
1343   else if (_gtk_css_parser_try (parser, "*", FALSE))
1344     selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ANY, selector, NULL);
1345
1346   return selector;
1347 }
1348
1349 static GtkCssSelector *
1350 parse_simple_selector (GtkCssParser   *parser,
1351                        GtkCssSelector *selector)
1352 {
1353   guint size = gtk_css_selector_size (selector);
1354
1355   selector = try_parse_name (parser, selector);
1356
1357   do {
1358       if (_gtk_css_parser_try (parser, "#", FALSE))
1359         selector = parse_selector_id (parser, selector);
1360       else if (_gtk_css_parser_try (parser, ".", FALSE))
1361         selector = parse_selector_class (parser, selector);
1362       else if (_gtk_css_parser_try (parser, ":", FALSE))
1363         selector = parse_selector_pseudo_class (parser, selector);
1364       else if (gtk_css_selector_size (selector) == size)
1365         {
1366           _gtk_css_parser_error (parser, "Expected a valid selector");
1367           if (selector)
1368             _gtk_css_selector_free (selector);
1369           return NULL;
1370         }
1371       else
1372         break;
1373     }
1374   while (selector && !_gtk_css_parser_is_eof (parser));
1375
1376   _gtk_css_parser_skip_whitespace (parser);
1377
1378   return selector;
1379 }
1380
1381 GtkCssSelector *
1382 _gtk_css_selector_parse (GtkCssParser *parser)
1383 {
1384   GtkCssSelector *selector = NULL;
1385
1386   while ((selector = parse_simple_selector (parser, selector)) &&
1387          !_gtk_css_parser_is_eof (parser) &&
1388          !_gtk_css_parser_begins_with (parser, ',') &&
1389          !_gtk_css_parser_begins_with (parser, '{'))
1390     {
1391       if (_gtk_css_parser_try (parser, "+", TRUE))
1392         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ADJACENT, selector, NULL);
1393       else if (_gtk_css_parser_try (parser, "~", TRUE))
1394         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_SIBLING, selector, NULL);
1395       else if (_gtk_css_parser_try (parser, ">", TRUE))
1396         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_CHILD, selector, NULL);
1397       else
1398         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_DESCENDANT, selector, NULL);
1399     }
1400
1401   return selector;
1402 }
1403
1404 void
1405 _gtk_css_selector_free (GtkCssSelector *selector)
1406 {
1407   g_return_if_fail (selector != NULL);
1408
1409   g_free (selector);
1410 }
1411
1412 void
1413 _gtk_css_selector_print (const GtkCssSelector *selector,
1414                          GString *             str)
1415 {
1416   const GtkCssSelector *previous;
1417
1418   g_return_if_fail (selector != NULL);
1419
1420   previous = gtk_css_selector_previous (selector);
1421   if (previous)
1422     _gtk_css_selector_print (previous, str);
1423
1424   selector->class->print (selector, str);
1425 }
1426
1427 char *
1428 _gtk_css_selector_to_string (const GtkCssSelector *selector)
1429 {
1430   GString *string;
1431
1432   g_return_val_if_fail (selector != NULL, NULL);
1433
1434   string = g_string_new (NULL);
1435
1436   _gtk_css_selector_print (selector, string);
1437
1438   return g_string_free (string, FALSE);
1439 }
1440
1441 GtkCssChange
1442 _gtk_css_selector_get_change (const GtkCssSelector *selector)
1443 {
1444   g_return_val_if_fail (selector != NULL, 0);
1445
1446   return gtk_css_selector_get_change (selector);
1447 }
1448
1449 /**
1450  * _gtk_css_selector_matches:
1451  * @selector: the selector
1452  * @path: the path to check
1453  * @state: The state to match
1454  *
1455  * Checks if the @selector matches the given @path. If @length is
1456  * smaller than the number of elements in @path, it is assumed that
1457  * only the first @length element of @path are valid and the rest
1458  * does not exist. This is useful for doing parent matches for the
1459  * 'inherit' keyword.
1460  *
1461  * Returns: %TRUE if the selector matches @path
1462  **/
1463 gboolean
1464 _gtk_css_selector_matches (const GtkCssSelector *selector,
1465                            const GtkCssMatcher  *matcher)
1466 {
1467
1468   g_return_val_if_fail (selector != NULL, FALSE);
1469   g_return_val_if_fail (matcher != NULL, FALSE);
1470
1471   return gtk_css_selector_match (selector, matcher);
1472 }
1473
1474 /* Computes specificity according to CSS 2.1.
1475  * The arguments must be initialized to 0 */
1476 static void
1477 _gtk_css_selector_get_specificity (const GtkCssSelector *selector,
1478                                    guint                *ids,
1479                                    guint                *classes,
1480                                    guint                *elements)
1481 {
1482   for (; selector; selector = gtk_css_selector_previous (selector))
1483     {
1484       const GtkCssSelectorClass *klass = selector->class;
1485
1486       if (klass->increase_id_specificity)
1487         (*ids)++;
1488       if (klass->increase_class_specificity)
1489         (*classes)++;
1490       if (klass->increase_element_specificity)
1491         (*elements)++;
1492     }
1493 }
1494
1495 int
1496 _gtk_css_selector_compare (const GtkCssSelector *a,
1497                            const GtkCssSelector *b)
1498 {
1499   guint a_ids = 0, a_classes = 0, a_elements = 0;
1500   guint b_ids = 0, b_classes = 0, b_elements = 0;
1501   int compare;
1502
1503   _gtk_css_selector_get_specificity (a, &a_ids, &a_classes, &a_elements);
1504   _gtk_css_selector_get_specificity (b, &b_ids, &b_classes, &b_elements);
1505
1506   compare = a_ids - b_ids;
1507   if (compare)
1508     return compare;
1509
1510   compare = a_classes - b_classes;
1511   if (compare)
1512     return compare;
1513
1514   return a_elements - b_elements;
1515 }
1516
1517
1518 /******************** SelectorTree handling *****************/
1519
1520 static GHashTable *
1521 gtk_css_selectors_count_initial_init (void)
1522 {
1523   return g_hash_table_new ((GHashFunc)gtk_css_selector_hash, (GEqualFunc)gtk_css_selector_equal);
1524 }
1525
1526 static void
1527 gtk_css_selectors_count_initial (const GtkCssSelector *selector, GHashTable *hash)
1528 {
1529   if (!selector->class->is_simple || selector->class->must_keep_order)
1530     {
1531       guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
1532       g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
1533       return;
1534     }
1535
1536   for (;
1537        selector && selector->class->is_simple && !selector->class->must_keep_order;
1538        selector = gtk_css_selector_previous (selector))
1539     {
1540       guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
1541       g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
1542     }
1543 }
1544
1545 static gboolean
1546 gtk_css_selectors_has_initial_selector (const GtkCssSelector *selector, const GtkCssSelector *initial)
1547 {
1548   if (!selector->class->is_simple || selector->class->must_keep_order)
1549     return gtk_css_selector_equal (selector, initial);
1550
1551   for (;
1552        selector && selector->class->is_simple && !selector->class->must_keep_order;
1553        selector = gtk_css_selector_previous (selector))
1554     {
1555       if (gtk_css_selector_equal (selector, initial))
1556         return TRUE;
1557     }
1558
1559   return FALSE;
1560 }
1561
1562 static GtkCssSelector *
1563 gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssSelector *initial)
1564 {
1565   GtkCssSelector *found;
1566   GtkCssSelector tmp;
1567
1568   /* If the initial simple selector is not first, move it there so we can skip it
1569      without losing any other selectors */
1570   if (!gtk_css_selector_equal (selector, initial))
1571     {
1572       for (found = selector; found && found->class->is_simple; found = (GtkCssSelector *)gtk_css_selector_previous (found))
1573         {
1574           if (gtk_css_selector_equal (found, initial))
1575             break;
1576         }
1577
1578       g_assert (found != NULL && found->class->is_simple);
1579
1580       tmp = *found;
1581       *found = *selector;
1582       *selector = tmp;
1583     }
1584
1585   return (GtkCssSelector *)gtk_css_selector_previous (selector);
1586 }
1587
1588 static int
1589 direct_ptr_compare (const void *_a, const void *_b)
1590 {
1591   gpointer *a = (gpointer *)_a;
1592   gpointer *b = (gpointer *)_b;
1593   if (*a < *b)
1594     return -1;
1595   else if (*a == *b)
1596     return 0;
1597   return 1;
1598 }
1599
1600 GPtrArray *
1601 _gtk_css_selector_tree_match_all (GtkCssSelectorTree *tree,
1602                                   const GtkCssMatcher *matcher)
1603 {
1604   GHashTable *res;
1605   GPtrArray *array;
1606   GHashTableIter iter;
1607   gpointer key;
1608
1609   res = g_hash_table_new (g_direct_hash, g_direct_equal);
1610
1611   for (; tree != NULL; tree = tree->siblings)
1612     gtk_css_selector_tree_match (tree, matcher, res);
1613
1614   array = g_ptr_array_sized_new (g_hash_table_size (res));
1615
1616   g_hash_table_iter_init (&iter, res);
1617   while (g_hash_table_iter_next (&iter, &key, NULL))
1618     g_ptr_array_add (array, key);
1619
1620   g_hash_table_destroy (res);
1621
1622   qsort (array->pdata, array->len, sizeof (gpointer), direct_ptr_compare);
1623
1624   return array;
1625 }
1626
1627 #ifdef PRINT_TREE
1628 static void
1629 _gtk_css_selector_tree_print (GtkCssSelectorTree *tree, GString *str, char *prefix)
1630 {
1631   gboolean first = TRUE;
1632   int len, i;
1633
1634   for (; tree != NULL; tree = tree->siblings, first = FALSE)
1635     {
1636       if (!first)
1637         g_string_append (str, prefix);
1638
1639       if (first)
1640         {
1641           if (tree->siblings)
1642             g_string_append (str, "─┬─");
1643           else
1644             g_string_append (str, "───");
1645         }
1646       else
1647         {
1648           if (tree->siblings)
1649             g_string_append (str, " ├─");
1650           else
1651             g_string_append (str, " └─");
1652         }
1653
1654       len = str->len;
1655       tree->selector.class->print (&tree->selector, str);
1656       len = str->len - len;
1657
1658       if (tree->previous)
1659         {
1660           GString *prefix2 = g_string_new (prefix);
1661
1662           if (tree->siblings)
1663             g_string_append (prefix2, " │ ");
1664           else
1665             g_string_append (prefix2, "   ");
1666           for (i = 0; i < len; i++)
1667             g_string_append_c (prefix2, ' ');
1668
1669           _gtk_css_selector_tree_print (tree->previous, str, prefix2->str);
1670           g_string_free (prefix2, TRUE);
1671         }
1672       else
1673         g_string_append (str, "\n");
1674     }
1675 }
1676 #endif
1677
1678 void
1679 _gtk_css_selector_tree_free (GtkCssSelectorTree *tree)
1680 {
1681   if (tree == NULL)
1682     return;
1683
1684   _gtk_css_selector_tree_free (tree->siblings);
1685   _gtk_css_selector_tree_free (tree->previous);
1686
1687   g_free (tree);
1688 }
1689
1690
1691 typedef struct {
1692   gpointer match;
1693   GtkCssSelector *current_selector;
1694 } GtkCssSelectorRuleSetInfo;
1695
1696
1697 static GtkCssSelectorTree *
1698 subdivide_infos (GList *infos, GtkCssSelectorTree *parent)
1699 {
1700   GHashTable *ht = gtk_css_selectors_count_initial_init ();
1701   GList *l;
1702   GList *matched;
1703   GList *remaining;
1704   GtkCssSelectorTree *tree;
1705   GtkCssSelectorRuleSetInfo *info;
1706   GtkCssSelector *max_selector;
1707   GHashTableIter iter;
1708   guint max_count;
1709   gpointer key, value;
1710   GPtrArray *exact_matches;
1711
1712   if (infos == NULL)
1713     return NULL;
1714
1715   for (l = infos; l != NULL; l = l->next)
1716     {
1717       info = l->data;
1718       gtk_css_selectors_count_initial (info->current_selector, ht);
1719     }
1720
1721   /* Pick the selector with highest count, and use as decision on this level
1722      as that makes it possible to skip the largest amount of checks later */
1723
1724   max_count = 0;
1725   max_selector = NULL;
1726
1727   g_hash_table_iter_init (&iter, ht);
1728   while (g_hash_table_iter_next (&iter, &key, &value))
1729     {
1730       if (GPOINTER_TO_UINT (value) > max_count)
1731         {
1732           max_count = GPOINTER_TO_UINT (value);
1733           max_selector = key;
1734         }
1735     }
1736
1737   matched = NULL;
1738   remaining = NULL;
1739
1740   tree = g_new0 (GtkCssSelectorTree, 1);
1741   tree->parent = parent;
1742   tree->selector = *max_selector;
1743
1744   exact_matches = NULL;
1745   for (l = infos; l != NULL; l = l->next)
1746     {
1747       info = l->data;
1748
1749       if (gtk_css_selectors_has_initial_selector (info->current_selector, &tree->selector))
1750         {
1751           info->current_selector = gtk_css_selectors_skip_initial_selector (info->current_selector, &tree->selector);
1752           if (info->current_selector == NULL)
1753             {
1754               /* Matches current node */
1755               if (exact_matches == NULL)
1756                 exact_matches = g_ptr_array_new ();
1757               g_ptr_array_add (exact_matches, info->match);
1758             }
1759           else
1760             matched = g_list_prepend (matched, info);
1761         }
1762       else
1763         {
1764           remaining = g_list_prepend (remaining, info);
1765         }
1766     }
1767
1768   if (exact_matches)
1769     {
1770       g_ptr_array_add (exact_matches, NULL); /* Null terminate */
1771       tree->matches = g_ptr_array_free (exact_matches, FALSE);
1772     }
1773
1774   if (matched)
1775     tree->previous = subdivide_infos (matched, tree);
1776
1777   if (remaining)
1778     tree->siblings = subdivide_infos (remaining, parent);
1779
1780   return tree;
1781 }
1782
1783 struct _GtkCssSelectorTreeBuilder {
1784   GList  *infos;
1785 };
1786
1787 GtkCssSelectorTreeBuilder *
1788 _gtk_css_selector_tree_builder_new (void)
1789 {
1790   return g_new0 (GtkCssSelectorTreeBuilder, 1);
1791 }
1792
1793 void
1794 _gtk_css_selector_tree_builder_free  (GtkCssSelectorTreeBuilder *builder)
1795 {
1796   g_list_free_full (builder->infos, g_free);
1797   g_free (builder);
1798 }
1799
1800 void
1801 _gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder,
1802                                     GtkCssSelector            *selectors,
1803                                     gpointer                   match)
1804 {
1805   GtkCssSelectorRuleSetInfo *info = g_new0 (GtkCssSelectorRuleSetInfo, 1);
1806
1807   info->match = match;
1808   info->current_selector = selectors;
1809   builder->infos = g_list_prepend (builder->infos, info);
1810 }
1811
1812 GtkCssSelectorTree *
1813 _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder)
1814 {
1815   GtkCssSelectorTree *tree;
1816
1817   tree = subdivide_infos (builder->infos, NULL);
1818
1819 #ifdef PRINT_TREE
1820   {
1821     GString *s = g_string_new ("");
1822     _gtk_css_selector_tree_print (tree, s, "");
1823     g_print ("%s", s->str);
1824     g_string_free (s, TRUE);
1825   }
1826 #endif
1827
1828   return tree;
1829 }