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