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