1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

//! A centralized set of stylesheets for a document.

use crate::dom::TElement;
use crate::invalidation::stylesheets::{RuleChangeKind, StylesheetInvalidationSet};
use crate::media_queries::Device;
use crate::selector_parser::SnapshotMap;
use crate::shared_lock::SharedRwLockReadGuard;
use crate::stylesheets::{
    CssRule, Origin, OriginSet, OriginSetIterator, PerOrigin, StylesheetInDocument,
};
use std::{mem, slice};

/// Entry for a StylesheetSet.
#[derive(MallocSizeOf)]
struct StylesheetSetEntry<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// The sheet.
    sheet: S,

    /// Whether this sheet has been part of at least one flush.
    committed: bool,
}

impl<S> StylesheetSetEntry<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    fn new(sheet: S) -> Self {
        Self {
            sheet,
            committed: false,
        }
    }
}

/// A iterator over the stylesheets of a list of entries in the StylesheetSet.
pub struct StylesheetCollectionIterator<'a, S>(slice::Iter<'a, StylesheetSetEntry<S>>)
where
    S: StylesheetInDocument + PartialEq + 'static;

impl<'a, S> Clone for StylesheetCollectionIterator<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    fn clone(&self) -> Self {
        StylesheetCollectionIterator(self.0.clone())
    }
}

impl<'a, S> Iterator for StylesheetCollectionIterator<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    type Item = &'a S;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|entry| &entry.sheet)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

/// An iterator over the flattened view of the stylesheet collections.
#[derive(Clone)]
pub struct StylesheetIterator<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    origins: OriginSetIterator,
    collections: &'a PerOrigin<SheetCollection<S>>,
    current: Option<(Origin, StylesheetCollectionIterator<'a, S>)>,
}

impl<'a, S> Iterator for StylesheetIterator<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    type Item = (&'a S, Origin);

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if self.current.is_none() {
                let next_origin = self.origins.next()?;

                self.current = Some((
                    next_origin,
                    self.collections.borrow_for_origin(&next_origin).iter(),
                ));
            }

            {
                let (origin, ref mut iter) = *self.current.as_mut().unwrap();
                if let Some(s) = iter.next() {
                    return Some((s, origin));
                }
            }

            self.current = None;
        }
    }
}

/// The validity of the data in a given cascade origin.
#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, Ord, PartialEq, PartialOrd)]
pub enum DataValidity {
    /// The origin is clean, all the data already there is valid, though we may
    /// have new sheets at the end.
    Valid = 0,

    /// The cascade data is invalid, but not the invalidation data (which is
    /// order-independent), and thus only the cascade data should be inserted.
    CascadeInvalid = 1,

    /// Everything needs to be rebuilt.
    FullyInvalid = 2,
}

impl Default for DataValidity {
    fn default() -> Self {
        DataValidity::Valid
    }
}

/// A struct to iterate over the different stylesheets to be flushed.
pub struct DocumentStylesheetFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    collections: &'a mut PerOrigin<SheetCollection<S>>,
    had_invalidations: bool,
}

/// The type of rebuild that we need to do for a given stylesheet.
#[derive(Clone, Copy, Debug)]
pub enum SheetRebuildKind {
    /// A full rebuild, of both cascade data and invalidation data.
    Full,
    /// A partial rebuild, of only the cascade data.
    CascadeOnly,
}

impl SheetRebuildKind {
    /// Whether the stylesheet invalidation data should be rebuilt.
    pub fn should_rebuild_invalidation(&self) -> bool {
        matches!(*self, SheetRebuildKind::Full)
    }
}

impl<'a, S> DocumentStylesheetFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Returns a flusher for `origin`.
    pub fn flush_origin(&mut self, origin: Origin) -> SheetCollectionFlusher<S> {
        self.collections.borrow_mut_for_origin(&origin).flush()
    }

    /// Returns the list of stylesheets for `origin`.
    ///
    /// Only used for UA sheets.
    pub fn origin_sheets(&mut self, origin: Origin) -> StylesheetCollectionIterator<S> {
        self.collections.borrow_mut_for_origin(&origin).iter()
    }

    /// Returns whether any DOM invalidations were processed as a result of the
    /// stylesheet flush.
    #[inline]
    pub fn had_invalidations(&self) -> bool {
        self.had_invalidations
    }
}

/// A flusher struct for a given collection, that takes care of returning the
/// appropriate stylesheets that need work.
pub struct SheetCollectionFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    // TODO: This can be made an iterator again once
    // https://github.com/rust-lang/rust/pull/82771 lands on stable.
    entries: &'a mut [StylesheetSetEntry<S>],
    validity: DataValidity,
    dirty: bool,
}

impl<'a, S> SheetCollectionFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Whether the collection was originally dirty.
    #[inline]
    pub fn dirty(&self) -> bool {
        self.dirty
    }

    /// What the state of the sheet data is.
    #[inline]
    pub fn data_validity(&self) -> DataValidity {
        self.validity
    }

    /// Returns an iterator over the remaining list of sheets to consume.
    pub fn sheets<'b>(&'b self) -> impl Iterator<Item = &'b S> {
        self.entries.iter().map(|entry| &entry.sheet)
    }
}

impl<'a, S> SheetCollectionFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Iterates over all sheets and values that we have to invalidate.
    ///
    /// TODO(emilio): This would be nicer as an iterator but we can't do that
    /// until https://github.com/rust-lang/rust/pull/82771 stabilizes.
    ///
    /// Since we don't have a good use-case for partial iteration, this does the
    /// trick for now.
    pub fn each(self, mut callback: impl FnMut(usize, &S, SheetRebuildKind) -> bool) {
        for (index, potential_sheet) in self.entries.iter_mut().enumerate() {
            let committed = mem::replace(&mut potential_sheet.committed, true);
            let rebuild_kind = if !committed {
                // If the sheet was uncommitted, we need to do a full rebuild
                // anyway.
                SheetRebuildKind::Full
            } else {
                match self.validity {
                    DataValidity::Valid => continue,
                    DataValidity::CascadeInvalid => SheetRebuildKind::CascadeOnly,
                    DataValidity::FullyInvalid => SheetRebuildKind::Full,
                }
            };

            if !callback(index, &potential_sheet.sheet, rebuild_kind) {
                return;
            }
        }
    }
}

#[derive(MallocSizeOf)]
struct SheetCollection<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// The actual list of stylesheets.
    ///
    /// This is only a list of top-level stylesheets, and as such it doesn't
    /// include recursive `@import` rules.
    entries: Vec<StylesheetSetEntry<S>>,

    /// The validity of the data that was already there for a given origin.
    ///
    /// Note that an origin may appear on `origins_dirty`, but still have
    /// `DataValidity::Valid`, if only sheets have been appended into it (in
    /// which case the existing data is valid, but the origin needs to be
    /// rebuilt).
    data_validity: DataValidity,

    /// Whether anything in the collection has changed. Note that this is
    /// different from `data_validity`, in the sense that after a sheet append,
    /// the data validity is still `Valid`, but we need to be marked as dirty.
    dirty: bool,
}

impl<S> Default for SheetCollection<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    fn default() -> Self {
        Self {
            entries: vec![],
            data_validity: DataValidity::Valid,
            dirty: false,
        }
    }
}

impl<S> SheetCollection<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Returns the number of stylesheets in the set.
    fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns the `index`th stylesheet in the set if present.
    fn get(&self, index: usize) -> Option<&S> {
        self.entries.get(index).map(|e| &e.sheet)
    }

    fn remove(&mut self, sheet: &S) {
        let index = self.entries.iter().position(|entry| entry.sheet == *sheet);
        if cfg!(feature = "gecko") && index.is_none() {
            // FIXME(emilio): Make Gecko's PresShell::AddUserSheet not suck.
            return;
        }
        let sheet = self.entries.remove(index.unwrap());
        // Removing sheets makes us tear down the whole cascade and invalidation
        // data, but only if the sheet has been involved in at least one flush.
        // Checking whether the sheet has been committed allows us to avoid
        // rebuilding the world when sites quickly append and remove a
        // stylesheet.
        //
        // See bug 1434756.
        if sheet.committed {
            self.set_data_validity_at_least(DataValidity::FullyInvalid);
        } else {
            self.dirty = true;
        }
    }

    fn contains(&self, sheet: &S) -> bool {
        self.entries.iter().any(|e| e.sheet == *sheet)
    }

    /// Appends a given sheet into the collection.
    fn append(&mut self, sheet: S) {
        debug_assert!(!self.contains(&sheet));
        self.entries.push(StylesheetSetEntry::new(sheet));
        // Appending sheets doesn't alter the validity of the existing data, so
        // we don't need to change `data_validity` here.
        //
        // But we need to be marked as dirty, otherwise we'll never add the new
        // sheet!
        self.dirty = true;
    }

    fn insert_before(&mut self, sheet: S, before_sheet: &S) {
        debug_assert!(!self.contains(&sheet));

        let index = self
            .entries
            .iter()
            .position(|entry| entry.sheet == *before_sheet)
            .expect("`before_sheet` stylesheet not found");

        // Inserting stylesheets somewhere but at the end changes the validity
        // of the cascade data, but not the invalidation data.
        self.set_data_validity_at_least(DataValidity::CascadeInvalid);
        self.entries.insert(index, StylesheetSetEntry::new(sheet));
    }

    fn set_data_validity_at_least(&mut self, validity: DataValidity) {
        use std::cmp;

        debug_assert_ne!(validity, DataValidity::Valid);

        self.dirty = true;
        self.data_validity = cmp::max(validity, self.data_validity);
    }

    /// Returns an iterator over the current list of stylesheets.
    fn iter(&self) -> StylesheetCollectionIterator<S> {
        StylesheetCollectionIterator(self.entries.iter())
    }

    fn flush(&mut self) -> SheetCollectionFlusher<S> {
        let dirty = mem::replace(&mut self.dirty, false);
        let validity = mem::replace(&mut self.data_validity, DataValidity::Valid);

        SheetCollectionFlusher {
            entries: &mut self.entries,
            dirty,
            validity,
        }
    }
}

/// The set of stylesheets effective for a given document.
#[cfg_attr(feature = "servo", derive(MallocSizeOf))]
pub struct DocumentStylesheetSet<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// The collections of sheets per each origin.
    collections: PerOrigin<SheetCollection<S>>,

    /// The invalidations for stylesheets added or removed from this document.
    invalidations: StylesheetInvalidationSet,
}

/// This macro defines methods common to DocumentStylesheetSet and
/// AuthorStylesheetSet.
///
/// We could simplify the setup moving invalidations to SheetCollection, but
/// that would imply not sharing invalidations across origins of the same
/// documents, which is slightly annoying.
macro_rules! sheet_set_methods {
    ($set_name:expr) => {
        fn collect_invalidations_for(
            &mut self,
            device: Option<&Device>,
            sheet: &S,
            guard: &SharedRwLockReadGuard,
        ) {
            if let Some(device) = device {
                self.invalidations
                    .collect_invalidations_for(device, sheet, guard);
            }
        }

        /// Appends a new stylesheet to the current set.
        ///
        /// No device implies not computing invalidations.
        pub fn append_stylesheet(
            &mut self,
            device: Option<&Device>,
            sheet: S,
            guard: &SharedRwLockReadGuard,
        ) {
            debug!(concat!($set_name, "::append_stylesheet"));
            self.collect_invalidations_for(device, &sheet, guard);
            let collection = self.collection_for(&sheet);
            collection.append(sheet);
        }

        /// Insert a given stylesheet before another stylesheet in the document.
        pub fn insert_stylesheet_before(
            &mut self,
            device: Option<&Device>,
            sheet: S,
            before_sheet: S,
            guard: &SharedRwLockReadGuard,
        ) {
            debug!(concat!($set_name, "::insert_stylesheet_before"));
            self.collect_invalidations_for(device, &sheet, guard);

            let collection = self.collection_for(&sheet);
            collection.insert_before(sheet, &before_sheet);
        }

        /// Remove a given stylesheet from the set.
        pub fn remove_stylesheet(
            &mut self,
            device: Option<&Device>,
            sheet: S,
            guard: &SharedRwLockReadGuard,
        ) {
            debug!(concat!($set_name, "::remove_stylesheet"));
            self.collect_invalidations_for(device, &sheet, guard);

            let collection = self.collection_for(&sheet);
            collection.remove(&sheet)
        }

        /// Notify the set that a rule from a given stylesheet has changed
        /// somehow.
        pub fn rule_changed(
            &mut self,
            device: Option<&Device>,
            sheet: &S,
            rule: &CssRule,
            guard: &SharedRwLockReadGuard,
            change_kind: RuleChangeKind,
        ) {
            if let Some(device) = device {
                let quirks_mode = device.quirks_mode();
                self.invalidations.rule_changed(
                    sheet,
                    rule,
                    guard,
                    device,
                    quirks_mode,
                    change_kind,
                );
            }

            let validity = match change_kind {
                // Insertion / Removals need to rebuild both the cascade and
                // invalidation data. For generic changes this is conservative,
                // could be optimized on a per-case basis.
                RuleChangeKind::Generic | RuleChangeKind::Insertion | RuleChangeKind::Removal => {
                    DataValidity::FullyInvalid
                },
                // TODO(emilio): This, in theory, doesn't need to invalidate
                // style data, if the rule we're modifying is actually in the
                // CascadeData already.
                //
                // But this is actually a bit tricky to prove, because when we
                // copy-on-write a stylesheet we don't bother doing a rebuild,
                // so we may still have rules from the original stylesheet
                // instead of the cloned one that we're modifying. So don't
                // bother for now and unconditionally rebuild, it's no worse
                // than what we were already doing anyway.
                //
                // Maybe we could record whether we saw a clone in this flush,
                // and if so do the conservative thing, otherwise just
                // early-return.
                RuleChangeKind::StyleRuleDeclarations => DataValidity::FullyInvalid,
            };

            let collection = self.collection_for(&sheet);
            collection.set_data_validity_at_least(validity);
        }
    };
}

impl<S> DocumentStylesheetSet<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Create a new empty DocumentStylesheetSet.
    pub fn new() -> Self {
        Self {
            collections: Default::default(),
            invalidations: StylesheetInvalidationSet::new(),
        }
    }

    fn collection_for(&mut self, sheet: &S) -> &mut SheetCollection<S> {
        let origin = sheet.contents().origin;
        self.collections.borrow_mut_for_origin(&origin)
    }

    sheet_set_methods!("DocumentStylesheetSet");

    /// Returns the number of stylesheets in the set.
    pub fn len(&self) -> usize {
        self.collections
            .iter_origins()
            .fold(0, |s, (item, _)| s + item.len())
    }

    /// Returns the count of stylesheets for a given origin.
    #[inline]
    pub fn sheet_count(&self, origin: Origin) -> usize {
        self.collections.borrow_for_origin(&origin).len()
    }

    /// Returns the `index`th stylesheet in the set for the given origin.
    #[inline]
    pub fn get(&self, origin: Origin, index: usize) -> Option<&S> {
        self.collections.borrow_for_origin(&origin).get(index)
    }

    /// Returns whether the given set has changed from the last flush.
    pub fn has_changed(&self) -> bool {
        !self.invalidations.is_empty() ||
            self.collections
                .iter_origins()
                .any(|(collection, _)| collection.dirty)
    }

    /// Flush the current set, unmarking it as dirty, and returns a
    /// `DocumentStylesheetFlusher` in order to rebuild the stylist.
    pub fn flush<E>(
        &mut self,
        document_element: Option<E>,
        snapshots: Option<&SnapshotMap>,
    ) -> DocumentStylesheetFlusher<S>
    where
        E: TElement,
    {
        debug!("DocumentStylesheetSet::flush");

        let had_invalidations = self.invalidations.flush(document_element, snapshots);

        DocumentStylesheetFlusher {
            collections: &mut self.collections,
            had_invalidations,
        }
    }

    /// Flush stylesheets, but without running any of the invalidation passes.
    #[cfg(feature = "servo")]
    pub fn flush_without_invalidation(&mut self) -> OriginSet {
        debug!("DocumentStylesheetSet::flush_without_invalidation");

        let mut origins = OriginSet::empty();
        self.invalidations.clear();

        for (collection, origin) in self.collections.iter_mut_origins() {
            if collection.flush().dirty() {
                origins |= origin;
            }
        }

        origins
    }

    /// Return an iterator over the flattened view of all the stylesheets.
    pub fn iter(&self) -> StylesheetIterator<S> {
        StylesheetIterator {
            origins: OriginSet::all().iter_origins(),
            collections: &self.collections,
            current: None,
        }
    }

    /// Mark the stylesheets for the specified origin as dirty, because
    /// something external may have invalidated it.
    pub fn force_dirty(&mut self, origins: OriginSet) {
        self.invalidations.invalidate_fully();
        for origin in origins.iter_origins() {
            // We don't know what happened, assume the worse.
            self.collections
                .borrow_mut_for_origin(&origin)
                .set_data_validity_at_least(DataValidity::FullyInvalid);
        }
    }
}

/// The set of stylesheets effective for a given Shadow Root.
#[derive(MallocSizeOf)]
pub struct AuthorStylesheetSet<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// The actual style sheets.
    collection: SheetCollection<S>,
    /// The set of invalidations scheduled for this collection.
    invalidations: StylesheetInvalidationSet,
}

/// A struct to flush an author style sheet collection.
pub struct AuthorStylesheetFlusher<'a, S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// The actual flusher for the collection.
    pub sheets: SheetCollectionFlusher<'a, S>,
    /// Whether any sheet invalidation matched.
    pub had_invalidations: bool,
}

impl<S> AuthorStylesheetSet<S>
where
    S: StylesheetInDocument + PartialEq + 'static,
{
    /// Create a new empty AuthorStylesheetSet.
    #[inline]
    pub fn new() -> Self {
        Self {
            collection: Default::default(),
            invalidations: StylesheetInvalidationSet::new(),
        }
    }

    /// Whether anything has changed since the last time this was flushed.
    pub fn dirty(&self) -> bool {
        self.collection.dirty
    }

    /// Whether the collection is empty.
    pub fn is_empty(&self) -> bool {
        self.collection.len() == 0
    }

    /// Returns the `index`th stylesheet in the collection of author styles if present.
    pub fn get(&self, index: usize) -> Option<&S> {
        self.collection.get(index)
    }

    /// Returns the number of author stylesheets.
    pub fn len(&self) -> usize {
        self.collection.len()
    }

    fn collection_for(&mut self, _sheet: &S) -> &mut SheetCollection<S> {
        &mut self.collection
    }

    sheet_set_methods!("AuthorStylesheetSet");

    /// Iterate over the list of stylesheets.
    pub fn iter(&self) -> StylesheetCollectionIterator<S> {
        self.collection.iter()
    }

    /// Mark the sheet set dirty, as appropriate.
    pub fn force_dirty(&mut self) {
        self.invalidations.invalidate_fully();
        self.collection
            .set_data_validity_at_least(DataValidity::FullyInvalid);
    }

    /// Flush the stylesheets for this author set.
    ///
    /// `host` is the root of the affected subtree, like the shadow host, for
    /// example.
    pub fn flush<E>(
        &mut self,
        host: Option<E>,
        snapshots: Option<&SnapshotMap>,
    ) -> AuthorStylesheetFlusher<S>
    where
        E: TElement,
    {
        let had_invalidations = self.invalidations.flush(host, snapshots);
        AuthorStylesheetFlusher {
            sheets: self.collection.flush(),
            had_invalidations,
        }
    }
}