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