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