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