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