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