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   };
1112   guint i, state;
1113
1114   state = GPOINTER_TO_UINT (selector->data);
1115   g_string_append_c (string, ':');
1116
1117   for (i = 0; i < G_N_ELEMENTS (state_names); i++)
1118     {
1119       if (state == (1 << i))
1120         {
1121           g_string_append (string, state_names[i]);
1122           return;
1123         }
1124     }
1125
1126   g_assert_not_reached ();
1127 }
1128
1129 static gboolean
1130 gtk_css_selector_pseudoclass_state_match (const GtkCssSelector *selector,
1131                                           const GtkCssMatcher  *matcher)
1132 {
1133   GtkStateFlags state = GPOINTER_TO_UINT (selector->data);
1134
1135   if ((_gtk_css_matcher_get_state (matcher) & state) != state)
1136     return FALSE;
1137
1138   return gtk_css_selector_match (gtk_css_selector_previous (selector), matcher);
1139 }
1140
1141 static void
1142 gtk_css_selector_pseudoclass_state_tree_match (const GtkCssSelectorTree *tree,
1143                                                const GtkCssMatcher  *matcher,
1144                                                GHashTable *res)
1145 {
1146   GtkStateFlags state = GPOINTER_TO_UINT (tree->selector.data);
1147
1148   if ((_gtk_css_matcher_get_state (matcher) & state) != state)
1149     return;
1150
1151   gtk_css_selector_tree_found_match (tree, res);
1152
1153   gtk_css_selector_tree_match_previous (tree, matcher, res);
1154 }
1155
1156 static GtkCssChange
1157 gtk_css_selector_pseudoclass_state_tree_get_change (const GtkCssSelectorTree *tree,
1158                                                     const GtkCssMatcher  *matcher)
1159 {
1160   GtkStateFlags state = GPOINTER_TO_UINT (tree->selector.data);
1161   GtkCssChange change, previous_change;
1162
1163   if ((_gtk_css_matcher_get_state (matcher) & state) != state)
1164     return 0;
1165
1166   change = 0;
1167
1168   if (tree->matches_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
1169     change |= GTK_CSS_CHANGE_STATE | GTK_CSS_CHANGE_GOT_MATCH;
1170
1171   previous_change = gtk_css_selector_tree_get_previous_change (tree, matcher);
1172
1173   if (previous_change != 0)
1174     change |= previous_change | GTK_CSS_CHANGE_STATE | GTK_CSS_CHANGE_GOT_MATCH;
1175
1176   return change;
1177 }
1178
1179 static GtkCssChange
1180 gtk_css_selector_pseudoclass_state_get_change (const GtkCssSelector *selector, GtkCssChange previous_change)
1181 {
1182   return previous_change | GTK_CSS_CHANGE_STATE;
1183 }
1184
1185 static int
1186 gtk_css_selector_pseudoclass_state_compare_one (const GtkCssSelector *a,
1187                                                 const GtkCssSelector *b)
1188 {
1189   return GPOINTER_TO_UINT (a->data) - GPOINTER_TO_UINT (b->data);
1190 }
1191
1192 static const GtkCssSelectorClass GTK_CSS_SELECTOR_PSEUDOCLASS_STATE = {
1193   "pseudoclass-state",
1194   gtk_css_selector_pseudoclass_state_print,
1195   gtk_css_selector_pseudoclass_state_match,
1196   gtk_css_selector_pseudoclass_state_tree_match,
1197   gtk_css_selector_pseudoclass_state_get_change,
1198   gtk_css_selector_pseudoclass_state_tree_get_change,
1199   gtk_css_selector_pseudoclass_state_compare_one,
1200   FALSE, TRUE, FALSE, TRUE, FALSE
1201 };
1202
1203 /* PSEUDOCLASS FOR POSITION */
1204
1205 typedef enum {
1206   POSITION_FORWARD,
1207   POSITION_BACKWARD,
1208   POSITION_ONLY,
1209   POSITION_SORTED
1210 } PositionType;
1211 #define POSITION_TYPE_BITS 2
1212 #define POSITION_NUMBER_BITS ((sizeof (gpointer) * 8 - POSITION_TYPE_BITS) / 2)
1213
1214 static gconstpointer
1215 encode_position (PositionType type,
1216                  int          a,
1217                  int          b)
1218 {
1219   union {
1220     gconstpointer p;
1221     struct {
1222       gssize type :POSITION_TYPE_BITS;
1223       gssize a :POSITION_NUMBER_BITS;
1224       gssize b :POSITION_NUMBER_BITS;
1225     } data;
1226   } result;
1227   G_STATIC_ASSERT (sizeof (gconstpointer) == sizeof (result));
1228
1229   g_assert (type < (1 << POSITION_TYPE_BITS));
1230
1231   result.data.type = type;
1232   result.data.a = a;
1233   result.data.b = b;
1234
1235   return result.p;
1236 }
1237
1238 static void
1239 decode_position (const GtkCssSelector *selector,
1240                  PositionType         *type,
1241                  int                  *a,
1242                  int                  *b)
1243 {
1244   union {
1245     gconstpointer p;
1246     struct {
1247       gssize type :POSITION_TYPE_BITS;
1248       gssize a :POSITION_NUMBER_BITS;
1249       gssize b :POSITION_NUMBER_BITS;
1250     } data;
1251   } result;
1252   G_STATIC_ASSERT (sizeof (gconstpointer) == sizeof (result));
1253
1254   result.p = selector->data;
1255
1256   *type = result.data.type & ((1 << POSITION_TYPE_BITS) - 1);
1257   *a = result.data.a;
1258   *b = result.data.b;
1259 }
1260
1261 static void
1262 gtk_css_selector_pseudoclass_position_print (const GtkCssSelector *selector,
1263                                              GString              *string)
1264 {
1265   PositionType type;
1266   int a, b;
1267
1268   decode_position (selector, &type, &a, &b);
1269   switch (type)
1270     {
1271     case POSITION_FORWARD:
1272       if (a == 0)
1273         {
1274           if (b == 1)
1275             g_string_append (string, ":first-child");
1276           else
1277             g_string_append_printf (string, ":nth-child(%d)", b);
1278         }
1279       else if (a == 2 && b == 0)
1280         g_string_append (string, ":nth-child(even)");
1281       else if (a == 2 && b == 1)
1282         g_string_append (string, ":nth-child(odd)");
1283       else
1284         {
1285           g_string_append (string, ":nth-child(");
1286           if (a == 1)
1287             g_string_append (string, "n");
1288           else if (a == -1)
1289             g_string_append (string, "-n");
1290           else
1291             g_string_append_printf (string, "%dn", a);
1292           if (b > 0)
1293             g_string_append_printf (string, "+%d)", b);
1294           else if (b < 0)
1295             g_string_append_printf (string, "%d)", b);
1296           else
1297             g_string_append (string, ")");
1298         }
1299       break;
1300     case POSITION_BACKWARD:
1301       if (a == 0)
1302         {
1303           if (b == 1)
1304             g_string_append (string, ":last-child");
1305           else
1306             g_string_append_printf (string, ":nth-last-child(%d)", b);
1307         }
1308       else if (a == 2 && b == 0)
1309         g_string_append (string, ":nth-last-child(even)");
1310       else if (a == 2 && b == 1)
1311         g_string_append (string, ":nth-last-child(odd)");
1312       else
1313         {
1314           g_string_append (string, ":nth-last-child(");
1315           if (a == 1)
1316             g_string_append (string, "n");
1317           else if (a == -1)
1318             g_string_append (string, "-n");
1319           else
1320             g_string_append_printf (string, "%dn", a);
1321           if (b > 0)
1322             g_string_append_printf (string, "+%d)", b);
1323           else if (b < 0)
1324             g_string_append_printf (string, "%d)", b);
1325           else
1326             g_string_append (string, ")");
1327         }
1328       break;
1329     case POSITION_ONLY:
1330       g_string_append (string, ":only-child");
1331       break;
1332     case POSITION_SORTED:
1333       g_string_append (string, ":sorted");
1334       break;
1335     default:
1336       g_assert_not_reached ();
1337       break;
1338     }
1339 }
1340
1341 static gboolean
1342 get_selector_flags_for_position_region_match (const GtkCssSelector *selector, GtkRegionFlags *selector_flags)
1343 {
1344   PositionType type;
1345   int a, b;
1346
1347   decode_position (selector, &type, &a, &b);
1348   switch (type)
1349     {
1350     case POSITION_FORWARD:
1351       if (a == 0 && b == 1)
1352         *selector_flags = GTK_REGION_FIRST;
1353       else if (a == 2 && b == 0)
1354         *selector_flags = GTK_REGION_EVEN;
1355       else if (a == 2 && b == 1)
1356         *selector_flags = GTK_REGION_ODD;
1357       else
1358         return FALSE;
1359       break;
1360     case POSITION_BACKWARD:
1361       if (a == 0 && b == 1)
1362         *selector_flags = GTK_REGION_LAST;
1363       else
1364         return FALSE;
1365       break;
1366     case POSITION_ONLY:
1367       *selector_flags = GTK_REGION_ONLY;
1368       break;
1369     case POSITION_SORTED:
1370       *selector_flags = GTK_REGION_SORTED;
1371       break;
1372     default:
1373       g_assert_not_reached ();
1374       break;
1375     }
1376
1377   return TRUE;
1378 }
1379
1380 static gboolean
1381 gtk_css_selector_pseudoclass_position_match_for_region (const GtkCssSelector *selector,
1382                                                         const GtkCssMatcher  *matcher)
1383 {
1384   GtkRegionFlags selector_flags;
1385   const GtkCssSelector *previous;
1386
1387   if (!get_selector_flags_for_position_region_match (selector, &selector_flags))
1388       return FALSE;
1389
1390   selector = gtk_css_selector_previous (selector);
1391
1392   if (!_gtk_css_matcher_has_region (matcher, selector->data, selector_flags))
1393     return FALSE;
1394
1395   previous = gtk_css_selector_previous (selector);
1396   if (previous && previous->class == &GTK_CSS_SELECTOR_DESCENDANT &&
1397       gtk_css_selector_match (gtk_css_selector_previous (previous), matcher))
1398     return TRUE;
1399
1400   return gtk_css_selector_match (previous, matcher);
1401 }
1402
1403 static gboolean
1404 get_position_match (const GtkCssSelector *selector,
1405                     const GtkCssMatcher  *matcher)
1406 {
1407   PositionType type;
1408   int a, b;
1409
1410   decode_position (selector, &type, &a, &b);
1411   switch (type)
1412     {
1413     case POSITION_FORWARD:
1414       if (!_gtk_css_matcher_has_position (matcher, TRUE, a, b))
1415         return FALSE;
1416       break;
1417     case POSITION_BACKWARD:
1418       if (!_gtk_css_matcher_has_position (matcher, FALSE, a, b))
1419         return FALSE;
1420       break;
1421     case POSITION_ONLY:
1422       if (!_gtk_css_matcher_has_position (matcher, TRUE, 0, 1) ||
1423           !_gtk_css_matcher_has_position (matcher, FALSE, 0, 1))
1424         return FALSE;
1425       break;
1426     case POSITION_SORTED:
1427       return FALSE;
1428     default:
1429       g_assert_not_reached ();
1430       return FALSE;
1431     }
1432
1433   return TRUE;
1434 }
1435
1436 static gboolean
1437 gtk_css_selector_pseudoclass_position_match (const GtkCssSelector *selector,
1438                                              const GtkCssMatcher  *matcher)
1439 {
1440   const GtkCssSelector *previous;
1441
1442   previous = gtk_css_selector_previous (selector);
1443   if (previous && previous->class == &GTK_CSS_SELECTOR_REGION)
1444     return gtk_css_selector_pseudoclass_position_match_for_region (selector, matcher);
1445
1446   if (!get_position_match (selector, matcher))
1447     return FALSE;
1448
1449   return gtk_css_selector_match (previous, matcher);
1450 }
1451
1452 static void
1453 gtk_css_selector_pseudoclass_position_tree_match_for_region (const GtkCssSelectorTree *tree,
1454                                                              const GtkCssSelectorTree *prev,
1455                                                              const GtkCssMatcher  *matcher,
1456                                                              GHashTable *res)
1457 {
1458   const GtkCssSelectorTree *prev2;
1459   GtkRegionFlags selector_flags;
1460
1461   if (!get_selector_flags_for_position_region_match (&tree->selector, &selector_flags))
1462       return;
1463
1464   if (!_gtk_css_matcher_has_region (matcher, prev->selector.data, selector_flags))
1465     return;
1466
1467   gtk_css_selector_tree_found_match (prev, res);
1468
1469   for (prev2 = gtk_css_selector_tree_get_previous (prev);
1470        prev2 != NULL;
1471        prev2 = gtk_css_selector_tree_get_sibling (prev2))
1472     {
1473       if (prev2->selector.class == &GTK_CSS_SELECTOR_DESCENDANT)
1474         gtk_css_selector_tree_match (gtk_css_selector_tree_get_previous (prev2), matcher, res);
1475       gtk_css_selector_tree_match (prev2, matcher, res);
1476     }
1477 }
1478
1479 static void
1480 gtk_css_selector_pseudoclass_position_tree_match (const GtkCssSelectorTree *tree,
1481                                                   const GtkCssMatcher  *matcher,
1482                                                   GHashTable *res)
1483 {
1484   const GtkCssSelectorTree *prev;
1485
1486   for (prev = gtk_css_selector_tree_get_previous (tree);
1487        prev != NULL;
1488        prev = gtk_css_selector_tree_get_sibling (prev))
1489     {
1490       if (prev->selector.class == &GTK_CSS_SELECTOR_REGION)
1491         gtk_css_selector_pseudoclass_position_tree_match_for_region (tree, prev, matcher, res);
1492     }
1493
1494   if (!get_position_match (&tree->selector, matcher))
1495     return;
1496
1497   gtk_css_selector_tree_found_match (tree, res);
1498
1499   for (prev = gtk_css_selector_tree_get_previous (tree); prev != NULL; prev = gtk_css_selector_tree_get_sibling (prev))
1500     {
1501       if (prev->selector.class != &GTK_CSS_SELECTOR_REGION)
1502         gtk_css_selector_tree_match (prev, matcher, res);
1503     }
1504 }
1505
1506 static GtkCssChange
1507 gtk_css_selector_pseudoclass_position_tree_get_change_for_region (const GtkCssSelectorTree *tree,
1508                                                                   const GtkCssSelectorTree *prev,
1509                                                                   const GtkCssMatcher  *matcher)
1510 {
1511   const GtkCssSelectorTree *prev2;
1512   GtkRegionFlags selector_flags;
1513   GtkCssChange change, previous_change;
1514
1515   if (!get_selector_flags_for_position_region_match (&tree->selector, &selector_flags))
1516       return 0;
1517
1518   if (!_gtk_css_matcher_has_region (matcher, prev->selector.data, selector_flags))
1519     return 0;
1520
1521   change = 0;
1522   if (tree->matches_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
1523     change |= GTK_CSS_CHANGE_POSITION | GTK_CSS_CHANGE_GOT_MATCH;
1524
1525   previous_change = 0;
1526   for (prev2 = gtk_css_selector_tree_get_previous (prev);
1527        prev2 != NULL;
1528        prev2 = gtk_css_selector_tree_get_sibling (prev2))
1529     {
1530       if (prev2->selector.class == &GTK_CSS_SELECTOR_DESCENDANT)
1531         previous_change |= gtk_css_selector_tree_get_change (gtk_css_selector_tree_get_previous (prev2), matcher);
1532       previous_change |= gtk_css_selector_tree_get_change (prev2, matcher);
1533     }
1534
1535   if (previous_change != 0)
1536     change |= previous_change | GTK_CSS_CHANGE_POSITION | GTK_CSS_CHANGE_GOT_MATCH;
1537
1538   return change;
1539 }
1540
1541 static GtkCssChange
1542 gtk_css_selector_pseudoclass_position_tree_get_change (const GtkCssSelectorTree *tree,
1543                                                        const GtkCssMatcher  *matcher)
1544 {
1545   const GtkCssSelectorTree *prev;
1546   GtkCssChange change, previous_change;
1547
1548   change = 0;
1549
1550   for (prev = gtk_css_selector_tree_get_previous (tree);
1551        prev != NULL;
1552        prev = gtk_css_selector_tree_get_sibling (prev))
1553     {
1554       if (prev->selector.class == &GTK_CSS_SELECTOR_REGION)
1555         change |= gtk_css_selector_pseudoclass_position_tree_get_change_for_region (tree, prev, matcher);
1556     }
1557
1558   if (!get_position_match (&tree->selector, matcher))
1559     return change;
1560
1561   if (tree->matches_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
1562     change |= GTK_CSS_CHANGE_POSITION | GTK_CSS_CHANGE_GOT_MATCH;
1563
1564   previous_change = 0;
1565   for (prev = gtk_css_selector_tree_get_previous (tree); prev != NULL; prev = gtk_css_selector_tree_get_sibling (prev))
1566     {
1567       if (prev->selector.class != &GTK_CSS_SELECTOR_REGION)
1568         previous_change |= gtk_css_selector_tree_get_change (prev, matcher);
1569     }
1570
1571   if (previous_change != 0)
1572     change |= previous_change | GTK_CSS_CHANGE_POSITION | GTK_CSS_CHANGE_GOT_MATCH;
1573
1574   return change;
1575 }
1576
1577 static GtkCssChange
1578 gtk_css_selector_pseudoclass_position_get_change (const GtkCssSelector *selector, GtkCssChange previous_change)
1579 {
1580   return previous_change | GTK_CSS_CHANGE_POSITION;
1581 }
1582
1583 static int
1584 gtk_css_selector_pseudoclass_position_compare_one (const GtkCssSelector *a,
1585                                                    const GtkCssSelector *b)
1586 {
1587   return GPOINTER_TO_UINT (a->data) - GPOINTER_TO_UINT (b->data);
1588 }
1589
1590 static const GtkCssSelectorClass GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION = {
1591   "pseudoclass-position",
1592   gtk_css_selector_pseudoclass_position_print,
1593   gtk_css_selector_pseudoclass_position_match,
1594   gtk_css_selector_pseudoclass_position_tree_match,
1595   gtk_css_selector_pseudoclass_position_get_change,
1596   gtk_css_selector_pseudoclass_position_tree_get_change,
1597   gtk_css_selector_pseudoclass_position_compare_one,
1598   FALSE, TRUE, FALSE, TRUE, TRUE
1599 };
1600
1601 /* API */
1602
1603 static guint
1604 gtk_css_selector_size (const GtkCssSelector *selector)
1605 {
1606   guint size = 0;
1607
1608   while (selector)
1609     {
1610       selector = gtk_css_selector_previous (selector);
1611       size++;
1612     }
1613
1614   return size;
1615 }
1616
1617 static GtkCssSelector *
1618 gtk_css_selector_new (const GtkCssSelectorClass *class,
1619                       GtkCssSelector            *selector,
1620                       gconstpointer              data)
1621 {
1622   guint size;
1623
1624   size = gtk_css_selector_size (selector);
1625   selector = g_realloc (selector, sizeof (GtkCssSelector) * (size + 1) + sizeof (gpointer));
1626   if (size == 0)
1627     selector[1].class = NULL;
1628   else
1629     memmove (selector + 1, selector, sizeof (GtkCssSelector) * size + sizeof (gpointer));
1630
1631   selector->class = class;
1632   selector->data = data;
1633
1634   return selector;
1635 }
1636
1637 static GtkCssSelector *
1638 parse_selector_class (GtkCssParser *parser, GtkCssSelector *selector)
1639 {
1640   char *name;
1641
1642   name = _gtk_css_parser_try_name (parser, FALSE);
1643
1644   if (name == NULL)
1645     {
1646       _gtk_css_parser_error (parser, "Expected a valid name for class");
1647       if (selector)
1648         _gtk_css_selector_free (selector);
1649       return NULL;
1650     }
1651
1652   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_CLASS,
1653                                    selector,
1654                                    GUINT_TO_POINTER (g_quark_from_string (name)));
1655
1656   g_free (name);
1657
1658   return selector;
1659 }
1660
1661 static GtkCssSelector *
1662 parse_selector_id (GtkCssParser *parser, GtkCssSelector *selector)
1663 {
1664   char *name;
1665
1666   name = _gtk_css_parser_try_name (parser, FALSE);
1667
1668   if (name == NULL)
1669     {
1670       _gtk_css_parser_error (parser, "Expected a valid name for id");
1671       if (selector)
1672         _gtk_css_selector_free (selector);
1673       return NULL;
1674     }
1675
1676   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ID,
1677                                    selector,
1678                                    g_intern_string (name));
1679
1680   g_free (name);
1681
1682   return selector;
1683 }
1684
1685 static GtkCssSelector *
1686 parse_selector_pseudo_class_nth_child (GtkCssParser   *parser,
1687                                        GtkCssSelector *selector,
1688                                        PositionType    type)
1689 {
1690   int a, b;
1691
1692   if (!_gtk_css_parser_try (parser, "(", TRUE))
1693     {
1694       _gtk_css_parser_error (parser, "Missing opening bracket for pseudo-class");
1695       if (selector)
1696         _gtk_css_selector_free (selector);
1697       return NULL;
1698     }
1699
1700   if (_gtk_css_parser_try (parser, "even", TRUE))
1701     {
1702       a = 2;
1703       b = 0;
1704     }
1705   else if (_gtk_css_parser_try (parser, "odd", TRUE))
1706     {
1707       a = 2;
1708       b = 1;
1709     }
1710   else if (type == POSITION_FORWARD &&
1711            _gtk_css_parser_try (parser, "first", TRUE))
1712     {
1713       a = 0;
1714       b = 1;
1715     }
1716   else if (type == POSITION_FORWARD &&
1717            _gtk_css_parser_try (parser, "last", TRUE))
1718     {
1719       a = 0;
1720       b = 1;
1721       type = POSITION_BACKWARD;
1722     }
1723   else
1724     {
1725       int multiplier;
1726
1727       if (_gtk_css_parser_try (parser, "+", TRUE))
1728         multiplier = 1;
1729       else if (_gtk_css_parser_try (parser, "-", TRUE))
1730         multiplier = -1;
1731       else
1732         multiplier = 1;
1733
1734       if (_gtk_css_parser_try_int (parser, &a))
1735         {
1736           if (a < 0)
1737             {
1738               _gtk_css_parser_error (parser, "Expected an integer");
1739               if (selector)
1740                 _gtk_css_selector_free (selector);
1741               return NULL;
1742             }
1743           a *= multiplier;
1744         }
1745       else if (_gtk_css_parser_has_prefix (parser, "n"))
1746         {
1747           a = multiplier;
1748         }
1749       else
1750         {
1751           _gtk_css_parser_error (parser, "Expected an integer");
1752           if (selector)
1753             _gtk_css_selector_free (selector);
1754           return NULL;
1755         }
1756
1757       if (_gtk_css_parser_try (parser, "n", TRUE))
1758         {
1759           if (_gtk_css_parser_try (parser, "+", TRUE))
1760             multiplier = 1;
1761           else if (_gtk_css_parser_try (parser, "-", TRUE))
1762             multiplier = -1;
1763           else
1764             multiplier = 1;
1765
1766           if (_gtk_css_parser_try_int (parser, &b))
1767             {
1768               if (b < 0)
1769                 {
1770                   _gtk_css_parser_error (parser, "Expected an integer");
1771                   if (selector)
1772                     _gtk_css_selector_free (selector);
1773                   return NULL;
1774                 }
1775             }
1776           else
1777             b = 0;
1778
1779           b *= multiplier;
1780         }
1781       else
1782         {
1783           b = a;
1784           a = 0;
1785         }
1786     }
1787
1788   if (!_gtk_css_parser_try (parser, ")", FALSE))
1789     {
1790       _gtk_css_parser_error (parser, "Missing closing bracket for pseudo-class");
1791       if (selector)
1792         _gtk_css_selector_free (selector);
1793       return NULL;
1794     }
1795
1796   selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION,
1797                                    selector,
1798                                    encode_position (type, a, b));
1799
1800   return selector;
1801 }
1802
1803 static GtkCssSelector *
1804 parse_selector_pseudo_class (GtkCssParser   *parser,
1805                              GtkCssSelector *selector)
1806 {
1807   static const struct {
1808     const char    *name;
1809     GtkStateFlags  state_flag;
1810     PositionType   position_type;
1811     int            position_a;
1812     int            position_b;
1813   } pseudo_classes[] = {
1814     { "first-child",  0,                           POSITION_FORWARD,  0, 1 },
1815     { "last-child",   0,                           POSITION_BACKWARD, 0, 1 },
1816     { "only-child",   0,                           POSITION_ONLY,     0, 0 },
1817     { "sorted",       0,                           POSITION_SORTED,   0, 0 },
1818     { "active",       GTK_STATE_FLAG_ACTIVE, },
1819     { "prelight",     GTK_STATE_FLAG_PRELIGHT, },
1820     { "hover",        GTK_STATE_FLAG_PRELIGHT, },
1821     { "selected",     GTK_STATE_FLAG_SELECTED, },
1822     { "insensitive",  GTK_STATE_FLAG_INSENSITIVE, },
1823     { "inconsistent", GTK_STATE_FLAG_INCONSISTENT, },
1824     { "focused",      GTK_STATE_FLAG_FOCUSED, },
1825     { "focus",        GTK_STATE_FLAG_FOCUSED, },
1826     { "backdrop",     GTK_STATE_FLAG_BACKDROP, }
1827   };
1828   guint i;
1829
1830   if (_gtk_css_parser_try (parser, "nth-child", FALSE))
1831     return parse_selector_pseudo_class_nth_child (parser, selector, POSITION_FORWARD);
1832   else if (_gtk_css_parser_try (parser, "nth-last-child", FALSE))
1833     return parse_selector_pseudo_class_nth_child (parser, selector, POSITION_BACKWARD);
1834
1835   for (i = 0; i < G_N_ELEMENTS (pseudo_classes); i++)
1836     {
1837       if (_gtk_css_parser_try (parser, pseudo_classes[i].name, FALSE))
1838         {
1839           if (pseudo_classes[i].state_flag)
1840             selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_STATE,
1841                                              selector,
1842                                              GUINT_TO_POINTER (pseudo_classes[i].state_flag));
1843           else
1844             selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_PSEUDOCLASS_POSITION,
1845                                              selector,
1846                                              encode_position (pseudo_classes[i].position_type,
1847                                                               pseudo_classes[i].position_a,
1848                                                               pseudo_classes[i].position_b));
1849           return selector;
1850         }
1851     }
1852
1853   _gtk_css_parser_error (parser, "Missing name of pseudo-class");
1854   if (selector)
1855     _gtk_css_selector_free (selector);
1856   return NULL;
1857 }
1858
1859 static GtkCssSelector *
1860 try_parse_name (GtkCssParser   *parser,
1861                 GtkCssSelector *selector)
1862 {
1863   char *name;
1864
1865   name = _gtk_css_parser_try_ident (parser, FALSE);
1866   if (name)
1867     {
1868       if (_gtk_style_context_check_region_name (name))
1869         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_REGION,
1870                                          selector,
1871                                          g_intern_string (name));
1872       else
1873         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_NAME,
1874                                          selector,
1875                                          get_type_reference (name));
1876       g_free (name);
1877     }
1878   else if (_gtk_css_parser_try (parser, "*", FALSE))
1879     selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ANY, selector, NULL);
1880
1881   return selector;
1882 }
1883
1884 static GtkCssSelector *
1885 parse_simple_selector (GtkCssParser   *parser,
1886                        GtkCssSelector *selector)
1887 {
1888   guint size = gtk_css_selector_size (selector);
1889
1890   selector = try_parse_name (parser, selector);
1891
1892   do {
1893       if (_gtk_css_parser_try (parser, "#", FALSE))
1894         selector = parse_selector_id (parser, selector);
1895       else if (_gtk_css_parser_try (parser, ".", FALSE))
1896         selector = parse_selector_class (parser, selector);
1897       else if (_gtk_css_parser_try (parser, ":", FALSE))
1898         selector = parse_selector_pseudo_class (parser, selector);
1899       else if (gtk_css_selector_size (selector) == size)
1900         {
1901           _gtk_css_parser_error (parser, "Expected a valid selector");
1902           if (selector)
1903             _gtk_css_selector_free (selector);
1904           return NULL;
1905         }
1906       else
1907         break;
1908     }
1909   while (selector && !_gtk_css_parser_is_eof (parser));
1910
1911   _gtk_css_parser_skip_whitespace (parser);
1912
1913   return selector;
1914 }
1915
1916 GtkCssSelector *
1917 _gtk_css_selector_parse (GtkCssParser *parser)
1918 {
1919   GtkCssSelector *selector = NULL;
1920
1921   while ((selector = parse_simple_selector (parser, selector)) &&
1922          !_gtk_css_parser_is_eof (parser) &&
1923          !_gtk_css_parser_begins_with (parser, ',') &&
1924          !_gtk_css_parser_begins_with (parser, '{'))
1925     {
1926       if (_gtk_css_parser_try (parser, "+", TRUE))
1927         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_ADJACENT, selector, NULL);
1928       else if (_gtk_css_parser_try (parser, "~", TRUE))
1929         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_SIBLING, selector, NULL);
1930       else if (_gtk_css_parser_try (parser, ">", TRUE))
1931         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_CHILD, selector, NULL);
1932       else
1933         selector = gtk_css_selector_new (&GTK_CSS_SELECTOR_DESCENDANT, selector, NULL);
1934     }
1935
1936   return selector;
1937 }
1938
1939 void
1940 _gtk_css_selector_free (GtkCssSelector *selector)
1941 {
1942   g_return_if_fail (selector != NULL);
1943
1944   g_free (selector);
1945 }
1946
1947 void
1948 _gtk_css_selector_print (const GtkCssSelector *selector,
1949                          GString *             str)
1950 {
1951   const GtkCssSelector *previous;
1952
1953   g_return_if_fail (selector != NULL);
1954
1955   previous = gtk_css_selector_previous (selector);
1956   if (previous)
1957     _gtk_css_selector_print (previous, str);
1958
1959   selector->class->print (selector, str);
1960 }
1961
1962 char *
1963 _gtk_css_selector_to_string (const GtkCssSelector *selector)
1964 {
1965   GString *string;
1966
1967   g_return_val_if_fail (selector != NULL, NULL);
1968
1969   string = g_string_new (NULL);
1970
1971   _gtk_css_selector_print (selector, string);
1972
1973   return g_string_free (string, FALSE);
1974 }
1975
1976
1977 GtkCssChange
1978 _gtk_css_selector_tree_match_get_change (const GtkCssSelectorTree *tree)
1979 {
1980   GtkCssChange change = 0;
1981
1982   update_type_references ();
1983
1984   while (tree)
1985     {
1986       change = tree->selector.class->get_change (&tree->selector, change);
1987       tree = gtk_css_selector_tree_get_parent (tree);
1988     }
1989
1990   return change;
1991 }
1992
1993 /**
1994  * _gtk_css_selector_matches:
1995  * @selector: the selector
1996  * @path: the path to check
1997  * @state: The state to match
1998  *
1999  * Checks if the @selector matches the given @path. If @length is
2000  * smaller than the number of elements in @path, it is assumed that
2001  * only the first @length element of @path are valid and the rest
2002  * does not exist. This is useful for doing parent matches for the
2003  * 'inherit' keyword.
2004  *
2005  * Returns: %TRUE if the selector matches @path
2006  **/
2007 gboolean
2008 _gtk_css_selector_matches (const GtkCssSelector *selector,
2009                            const GtkCssMatcher  *matcher)
2010 {
2011
2012   g_return_val_if_fail (selector != NULL, FALSE);
2013   g_return_val_if_fail (matcher != NULL, FALSE);
2014
2015   update_type_references ();
2016
2017   return gtk_css_selector_match (selector, matcher);
2018 }
2019
2020 /* Computes specificity according to CSS 2.1.
2021  * The arguments must be initialized to 0 */
2022 static void
2023 _gtk_css_selector_get_specificity (const GtkCssSelector *selector,
2024                                    guint                *ids,
2025                                    guint                *classes,
2026                                    guint                *elements)
2027 {
2028   for (; selector; selector = gtk_css_selector_previous (selector))
2029     {
2030       const GtkCssSelectorClass *klass = selector->class;
2031
2032       if (klass->increase_id_specificity)
2033         (*ids)++;
2034       if (klass->increase_class_specificity)
2035         (*classes)++;
2036       if (klass->increase_element_specificity)
2037         (*elements)++;
2038     }
2039 }
2040
2041 int
2042 _gtk_css_selector_compare (const GtkCssSelector *a,
2043                            const GtkCssSelector *b)
2044 {
2045   guint a_ids = 0, a_classes = 0, a_elements = 0;
2046   guint b_ids = 0, b_classes = 0, b_elements = 0;
2047   int compare;
2048
2049   _gtk_css_selector_get_specificity (a, &a_ids, &a_classes, &a_elements);
2050   _gtk_css_selector_get_specificity (b, &b_ids, &b_classes, &b_elements);
2051
2052   compare = a_ids - b_ids;
2053   if (compare)
2054     return compare;
2055
2056   compare = a_classes - b_classes;
2057   if (compare)
2058     return compare;
2059
2060   return a_elements - b_elements;
2061 }
2062
2063
2064 /******************** SelectorTree handling *****************/
2065
2066 static GHashTable *
2067 gtk_css_selectors_count_initial_init (void)
2068 {
2069   return g_hash_table_new ((GHashFunc)gtk_css_selector_hash, (GEqualFunc)gtk_css_selector_equal);
2070 }
2071
2072 static void
2073 gtk_css_selectors_count_initial (const GtkCssSelector *selector, GHashTable *hash)
2074 {
2075   if (!selector->class->is_simple || selector->class->must_keep_order)
2076     {
2077       guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
2078       g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
2079       return;
2080     }
2081
2082   for (;
2083        selector && selector->class->is_simple && !selector->class->must_keep_order;
2084        selector = gtk_css_selector_previous (selector))
2085     {
2086       guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
2087       g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
2088     }
2089 }
2090
2091 static gboolean
2092 gtk_css_selectors_has_initial_selector (const GtkCssSelector *selector, const GtkCssSelector *initial)
2093 {
2094   if (!selector->class->is_simple || selector->class->must_keep_order)
2095     return gtk_css_selector_equal (selector, initial);
2096
2097   for (;
2098        selector && selector->class->is_simple && !selector->class->must_keep_order;
2099        selector = gtk_css_selector_previous (selector))
2100     {
2101       if (gtk_css_selector_equal (selector, initial))
2102         return TRUE;
2103     }
2104
2105   return FALSE;
2106 }
2107
2108 static GtkCssSelector *
2109 gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssSelector *initial)
2110 {
2111   GtkCssSelector *found;
2112   GtkCssSelector tmp;
2113
2114   /* If the initial simple selector is not first, move it there so we can skip it
2115      without losing any other selectors */
2116   if (!gtk_css_selector_equal (selector, initial))
2117     {
2118       for (found = selector; found && found->class->is_simple; found = (GtkCssSelector *)gtk_css_selector_previous (found))
2119         {
2120           if (gtk_css_selector_equal (found, initial))
2121             break;
2122         }
2123
2124       g_assert (found != NULL && found->class->is_simple);
2125
2126       tmp = *found;
2127       *found = *selector;
2128       *selector = tmp;
2129     }
2130
2131   return (GtkCssSelector *)gtk_css_selector_previous (selector);
2132 }
2133
2134 static int
2135 direct_ptr_compare (const void *_a, const void *_b)
2136 {
2137   gpointer *a = (gpointer *)_a;
2138   gpointer *b = (gpointer *)_b;
2139   if (*a < *b)
2140     return -1;
2141   else if (*a == *b)
2142     return 0;
2143   return 1;
2144 }
2145
2146 GPtrArray *
2147 _gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree,
2148                                   const GtkCssMatcher *matcher)
2149 {
2150   GHashTable *res;
2151   GPtrArray *array;
2152   GHashTableIter iter;
2153   gpointer key;
2154
2155   update_type_references ();
2156
2157   res = g_hash_table_new (g_direct_hash, g_direct_equal);
2158
2159   for (; tree != NULL;
2160        tree = gtk_css_selector_tree_get_sibling (tree))
2161     gtk_css_selector_tree_match (tree, matcher, res);
2162
2163   array = g_ptr_array_sized_new (g_hash_table_size (res));
2164
2165   g_hash_table_iter_init (&iter, res);
2166   while (g_hash_table_iter_next (&iter, &key, NULL))
2167     g_ptr_array_add (array, key);
2168
2169   g_hash_table_destroy (res);
2170
2171   qsort (array->pdata, array->len, sizeof (gpointer), direct_ptr_compare);
2172
2173   return array;
2174 }
2175
2176 GtkCssChange
2177 _gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree,
2178                                        const GtkCssMatcher *matcher)
2179 {
2180   GtkCssChange change;
2181
2182   change = 0;
2183
2184   for (; tree != NULL;
2185        tree = gtk_css_selector_tree_get_sibling (tree))
2186     change |= gtk_css_selector_tree_get_change (tree, matcher);
2187
2188   /* Never return reserved bit set */
2189   return change & ~GTK_CSS_CHANGE_RESERVED_BIT;
2190 }
2191
2192 #ifdef PRINT_TREE
2193 static void
2194 _gtk_css_selector_tree_print (GtkCssSelectorTree *tree, GString *str, char *prefix)
2195 {
2196   gboolean first = TRUE;
2197   int len, i;
2198
2199   for (; tree != NULL; tree = tree->siblings, first = FALSE)
2200     {
2201       if (!first)
2202         g_string_append (str, prefix);
2203
2204       if (first)
2205         {
2206           if (tree->siblings)
2207             g_string_append (str, "─┬─");
2208           else
2209             g_string_append (str, "───");
2210         }
2211       else
2212         {
2213           if (tree->siblings)
2214             g_string_append (str, " ├─");
2215           else
2216             g_string_append (str, " └─");
2217         }
2218
2219       len = str->len;
2220       tree->selector.class->print (&tree->selector, str);
2221       len = str->len - len;
2222
2223       if (gtk_css_selector_tree_get_previous (tree))
2224         {
2225           GString *prefix2 = g_string_new (prefix);
2226
2227           if (tree->siblings)
2228             g_string_append (prefix2, " │ ");
2229           else
2230             g_string_append (prefix2, "   ");
2231           for (i = 0; i < len; i++)
2232             g_string_append_c (prefix2, ' ');
2233
2234           _gtk_css_selector_tree_print (gtk_css_selector_tree_get_previous (tree), str, prefix2->str);
2235           g_string_free (prefix2, TRUE);
2236         }
2237       else
2238         g_string_append (str, "\n");
2239     }
2240 }
2241 #endif
2242
2243 void
2244 _gtk_css_selector_tree_match_print (const GtkCssSelectorTree *tree,
2245                                     GString *str)
2246 {
2247   const GtkCssSelectorTree *parent;
2248
2249   g_return_if_fail (tree != NULL);
2250
2251   tree->selector.class->print (&tree->selector, str);
2252
2253   parent = gtk_css_selector_tree_get_parent (tree);
2254   if (parent != NULL)
2255     _gtk_css_selector_tree_match_print (parent, str);
2256 }
2257
2258 void
2259 _gtk_css_selector_tree_free (GtkCssSelectorTree *tree)
2260 {
2261   if (tree == NULL)
2262     return;
2263
2264   g_free (tree);
2265 }
2266
2267
2268 typedef struct {
2269   gpointer match;
2270   GtkCssSelector *current_selector;
2271   GtkCssSelectorTree **selector_match;
2272 } GtkCssSelectorRuleSetInfo;
2273
2274 static GtkCssSelectorTree *
2275 get_tree (GByteArray *array, gint32 offset)
2276 {
2277   return (GtkCssSelectorTree *) (array->data + offset);
2278 }
2279
2280 static GtkCssSelectorTree *
2281 alloc_tree (GByteArray *array, gint32 *offset)
2282 {
2283   GtkCssSelectorTree tree = { { NULL} };
2284
2285   *offset = array->len;
2286   g_byte_array_append (array, (guint8 *)&tree, sizeof (GtkCssSelectorTree));
2287   return get_tree (array, *offset);
2288 }
2289
2290 static gint32
2291 subdivide_infos (GByteArray *array, GList *infos, gint32 parent_offset)
2292 {
2293   GHashTable *ht;
2294   GList *l;
2295   GList *matched;
2296   GList *remaining;
2297   gint32 tree_offset;
2298   GtkCssSelectorTree *tree;
2299   GtkCssSelectorRuleSetInfo *info;
2300   GtkCssSelector max_selector;
2301   GHashTableIter iter;
2302   guint max_count;
2303   gpointer key, value;
2304   GPtrArray *exact_matches;
2305   gint32 res;
2306
2307   if (infos == NULL)
2308     return GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
2309
2310   ht = gtk_css_selectors_count_initial_init ();
2311
2312   for (l = infos; l != NULL; l = l->next)
2313     {
2314       info = l->data;
2315       gtk_css_selectors_count_initial (info->current_selector, ht);
2316     }
2317
2318   /* Pick the selector with highest count, and use as decision on this level
2319      as that makes it possible to skip the largest amount of checks later */
2320
2321   max_count = 0;
2322
2323   g_hash_table_iter_init (&iter, ht);
2324   while (g_hash_table_iter_next (&iter, &key, &value))
2325     {
2326       GtkCssSelector *selector = key;
2327       if (GPOINTER_TO_UINT (value) > max_count ||
2328           (GPOINTER_TO_UINT (value) == max_count &&
2329           gtk_css_selector_compare_one (selector, &max_selector) < 0))
2330         {
2331           max_count = GPOINTER_TO_UINT (value);
2332           max_selector = *selector;
2333         }
2334     }
2335
2336   matched = NULL;
2337   remaining = NULL;
2338
2339   tree = alloc_tree (array, &tree_offset);
2340   tree->parent_offset = parent_offset;
2341   tree->selector = max_selector;
2342
2343   exact_matches = NULL;
2344   for (l = infos; l != NULL; l = l->next)
2345     {
2346       info = l->data;
2347
2348       if (gtk_css_selectors_has_initial_selector (info->current_selector, &max_selector))
2349         {
2350           info->current_selector = gtk_css_selectors_skip_initial_selector (info->current_selector, &max_selector);
2351           if (info->current_selector == NULL)
2352             {
2353               /* Matches current node */
2354               if (exact_matches == NULL)
2355                 exact_matches = g_ptr_array_new ();
2356               g_ptr_array_add (exact_matches, info->match);
2357               if (info->selector_match != NULL)
2358                 *info->selector_match = GUINT_TO_POINTER (tree_offset);
2359             }
2360           else
2361             matched = g_list_prepend (matched, info);
2362         }
2363       else
2364         {
2365           remaining = g_list_prepend (remaining, info);
2366         }
2367     }
2368
2369   if (exact_matches)
2370     {
2371       g_ptr_array_add (exact_matches, NULL); /* Null terminate */
2372       res = array->len;
2373       g_byte_array_append (array, (guint8 *)exact_matches->pdata,
2374                            exact_matches->len * sizeof (gpointer));
2375       g_ptr_array_free (exact_matches, TRUE);
2376     }
2377   else
2378     res = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
2379   get_tree (array, tree_offset)->matches_offset = res;
2380
2381   res = subdivide_infos (array, matched, tree_offset);
2382   get_tree (array, tree_offset)->previous_offset = res;
2383
2384   res = subdivide_infos (array, remaining, parent_offset);
2385   get_tree (array, tree_offset)->sibling_offset = res;
2386
2387   g_list_free (matched);
2388   g_list_free (remaining);
2389   g_hash_table_unref (ht);
2390
2391   return tree_offset;
2392 }
2393
2394 struct _GtkCssSelectorTreeBuilder {
2395   GList  *infos;
2396 };
2397
2398 GtkCssSelectorTreeBuilder *
2399 _gtk_css_selector_tree_builder_new (void)
2400 {
2401   return g_new0 (GtkCssSelectorTreeBuilder, 1);
2402 }
2403
2404 void
2405 _gtk_css_selector_tree_builder_free  (GtkCssSelectorTreeBuilder *builder)
2406 {
2407   g_list_free_full (builder->infos, g_free);
2408   g_free (builder);
2409 }
2410
2411 void
2412 _gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder,
2413                                     GtkCssSelector            *selectors,
2414                                     GtkCssSelectorTree       **selector_match,
2415                                     gpointer                   match)
2416 {
2417   GtkCssSelectorRuleSetInfo *info = g_new0 (GtkCssSelectorRuleSetInfo, 1);
2418
2419   info->match = match;
2420   info->current_selector = selectors;
2421   info->selector_match = selector_match;
2422   builder->infos = g_list_prepend (builder->infos, info);
2423 }
2424
2425 /* Convert all offsets to node-relative */
2426 static void
2427 fixup_offsets (GtkCssSelectorTree *tree, guint8 *data)
2428 {
2429   while (tree != NULL)
2430     {
2431       if (tree->parent_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
2432         tree->parent_offset -= ((guint8 *)tree - data);
2433
2434       if (tree->previous_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
2435         tree->previous_offset -= ((guint8 *)tree - data);
2436
2437       if (tree->sibling_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
2438         tree->sibling_offset -= ((guint8 *)tree - data);
2439
2440       if (tree->matches_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
2441         tree->matches_offset -= ((guint8 *)tree - data);
2442
2443       fixup_offsets ((GtkCssSelectorTree *)gtk_css_selector_tree_get_previous (tree), data);
2444
2445       tree = (GtkCssSelectorTree *)gtk_css_selector_tree_get_sibling (tree);
2446     }
2447 }
2448
2449 GtkCssSelectorTree *
2450 _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder)
2451 {
2452   GtkCssSelectorTree *tree;
2453   GByteArray *array;
2454   guint8 *data;
2455   guint len;
2456   GList *l;
2457   GtkCssSelectorRuleSetInfo *info;
2458
2459   array = g_byte_array_new ();
2460   subdivide_infos (array, builder->infos, GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET);
2461
2462   len = array->len;
2463   data = g_byte_array_free (array, FALSE);
2464
2465   /* shrink to final size */
2466   data = g_realloc (data, len);
2467
2468   tree = (GtkCssSelectorTree *)data;
2469
2470   fixup_offsets (tree, data);
2471
2472   /* Convert offsets to final pointers */
2473   for (l = builder->infos; l != NULL; l = l->next)
2474     {
2475       info = l->data;
2476       if (info->selector_match)
2477         *info->selector_match = (GtkCssSelectorTree *)(data + GPOINTER_TO_UINT (*info->selector_match));
2478     }
2479
2480 #ifdef PRINT_TREE
2481   {
2482     GString *s = g_string_new ("");
2483     _gtk_css_selector_tree_print (tree, s, "");
2484     g_print ("%s", s->str);
2485     g_string_free (s, TRUE);
2486   }
2487 #endif
2488
2489   return tree;
2490 }