1403839 - stylo: custom-properties dependency cycle resolving algorithm is unreliable

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect, P3)

Description

[Xidorn Quan [:xidorn] UTC+10]

See bug 1402217 comment 2. That algorithm doesn't guarantee to eliminate all cycle dependencies.

Comment 1

[Emilio Cobos Álvarez (:emilio)]

You should probably check with Simon, he may be interested in looking into these.

Comment 2

[Xidorn Quan [:xidorn] UTC+10]

Attachment: Rewrite cycle removal algorithm of custom properties.

Review commit: https://reviewboard.mozilla.org/r/185014/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/185014/

Comment 3

[Xidorn Quan [:xidorn] UTC+10]

Attachment: Bug 1403839 - Add a more complicated test for custom properties loop eliminiation.

Review commit: https://reviewboard.mozilla.org/r/185016/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/185016/

Comment 4

[Xidorn Quan [:xidorn] UTC+10]

The main problem of the old algorithm is that, it skips any node that has been visited, and don't take the node into account for cycle. However, a node visited can really be part of a loop for another search path. So the old algorithm is very path-dependent.

For example, the prototype of the new testcase is the following reference graph:

+-----------------+
|                 |
+-> a -+-> b -+-> c
       |      |
       +-> d -+

If we start from "a", and visit "b", we would find that "c" would go back to "a" which forms a cycle. But when we pop the stack until "a", and start visiting "d", we judge that "c" has been visited, so we skip, and consider "d" to be not in any cycle. However, if we start from "c", we would correctly find out that all nodes in this graph are in cycles.

Comment 5

[Xidorn Quan [:xidorn] UTC+10]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=d9a2168d6a4cb1747a9ee4917c6d2772552cefe2

Comment 6

[Emilio Cobos Álvarez (:emilio)]

Xidorn, I've been looking at custom props performance lately, mostly due to bug 1405411.

One of the ideas I'm going to try to implement tomorrow is to implement the cycle detection algorithm while substituting variable references from custom properties.

Basically, for each property we traverse resolving variables, we insert the name in a set of "edges visited during this substitution".

When we find an edge we've already visited, we know we're on a cycle. and all the properties we've visited so far also know that. We cannot return early, since we need to keep trying to substitute the rest of references to find the extra cycle that going through `d` would find (maybe it's not necessary if we defer the removal of cyclic properties?), but in any case that doesn't seem that complex to me.

Xidorn, does this look reasonable to you? I think it'd be a faster approach (specially in the common "no cycles" case), wdyt?

Comment 7

[Xidorn Quan [:xidorn] UTC+10]

Discussed with emilio on IRC. I explained several issues I met when I initially tried to fix this with an "easy" algorithm. Specifically, the problem is that we need to clearly distinguish whether a var is in loop, and they would have different behavior in those case.

e.g. in case like
> { --a: var(--b); --b: var(--a); --c: var(--a, 1); }
--c should be 1, because it is not in cycle, and it's referencing --a which is invalid because of dependency cycle. However, in
> { --a: var(--b, 1); --b: var(--a); }
--a should be invalid, because it is in cycle.

I think thes restrictions would rule out many mark-once algorithm.

emilio has acknowledged this potential issue, and would try to implement one which doesn't violate this.

I suspect that we would still end up implementing one of the strong connected component algorithms somehow (the Tarjan's, the Kosaraju's, or the path-based) if we want the best time complexity for worst case, though.

Comment 8

[Xidorn Quan [:xidorn] UTC+10]

Discussed with emilio on IRC after comment 7, and it seems he doesn't actually have an easier algorithm for resolving cycle dependency without an exponential time complexity.

Thinking about this a bit more, I think we should be able to combine the substitution and cycle removal in a single traversal to make the whole thing more performant. It can be integrated with the Tarjan's algorithm here.

I can probably try to implement the combined algorithm.

Comment 9

[Xidorn Quan [:xidorn] UTC+10]

I'm going to do this tomorrow morning...

Comment 10

[Simon Sapin (:SimonSapin)]

Comment on attachment 8913623 [details]
Rewrite cycle removal algorithm of custom properties.

https://reviewboard.mozilla.org/r/185014/#review193170

::: servo/components/style/custom_properties.rs:545
(Diff revision 1)
> +    struct Context<'a> {
> +        /// Number of vertics visited. This is used as the order index
> +        /// when we visit a new vertex.
> +        count: usize,
> +        /// The map from custom property name to its order index.
> +        index_map: HashMap<&'a Name, usize>,

Maybe this should be a FnvHashMap, or a PrecomputedHashMap?

::: servo/components/style/custom_properties.rs:550
(Diff revision 1)
> +        index_map: HashMap<&'a Name, usize>,
> +        /// Information of each vertex indexed by the order index.
> +        var_info: Vec<VarInfo<'a>>,
> +        /// The stack of order index of visited vertics. It contains all
> +        /// unfinished strong connected components.
> +        stack: Vec<usize>,

Maybe this and var_info should be SmallVec’s?

::: servo/components/style/custom_properties.rs:564
(Diff revision 1)
> +            Entry::Vacant(entry) => { entry.insert(context.count); }
> +        }
> +        let index = context.count;
> +        context.count += 1;
> +
> +        debug_assert!(index == context.var_info.len());

Could context.count be removed and context.var_info.len() used instead?

Comment 11

[Simon Sapin (:SimonSapin)]

Comment on attachment 8913624 [details]
Bug 1403839 - Add a more complicated test for custom properties loop eliminiation.

https://reviewboard.mozilla.org/r/185016/#review192536

::: layout/style/test/test_variables_loop.html:44
(Diff revision 1)
> +    for (let ref of test[v]) {
> +      refs.push(`var(--${ref}, ${v}${ref})`);
> +    }
> +    inner_style.push(`--${v}: ${refs.join(" ")};`);
> +  }
> +  inner_decl.style = inner_style.join("\n");

This whole procedural stylesheet construction is not easy to read. It seems like having a stylesheet "hard-coded" in a `<style>` element wouldn’t be more code?

::: layout/style/test/test_variables_loop.html:44
(Diff revision 1)
> +    for (let ref of test[v]) {
> +      refs.push(`var(--${ref}, ${v}${ref})`);
> +    }
> +    inner_style.push(`--${v}: ${refs.join(" ")};`);
> +  }
> +  inner_decl.style = inner_style.join("\n");

I feel this would be a lot simpler and easier to read with a test stylesheet "hard-coded" in a `<style>` element rather than generated programatically. Or is there some reason to prefer this that I’m missing?

Comment 12

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8913624 [details]
Bug 1403839 - Add a more complicated test for custom properties loop eliminiation.

https://reviewboard.mozilla.org/r/185016/#review192536

> I feel this would be a lot simpler and easier to read with a test stylesheet "hard-coded" in a `<style>` element rather than generated programatically. Or is there some reason to prefer this that I’m missing?

There are two reasons:
1. we can add other testcases in the future easily.
2. things would be less duplicate

But since the generating code itself is quite long, probably it isn't worth until we really need to add other testcase...

Comment 13

[Xidorn Quan [:xidorn] UTC+10]

Attachment: Rewrite cycle removal algorithm of custom properties and integrate it with substitution.

Review commit: https://reviewboard.mozilla.org/r/188268/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/188268/

Comment 14

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8913624 [details]
Bug 1403839 - Add a more complicated test for custom properties loop eliminiation.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/185016/diff/1-2/

Comment 15

[Simon Sapin (:SimonSapin)]

Comment on attachment 8917258 [details]
Rewrite cycle removal algorithm of custom properties and integrate it with substitution.

https://reviewboard.mozilla.org/r/188268/#review194240

Comment 16

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8917258 [details]
Rewrite cycle removal algorithm of custom properties and integrate it with substitution.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/188268/diff/1-2/

Comment 17

[Xidorn Quan [:xidorn] UTC+10]

Comment on attachment 8913624 [details]
Bug 1403839 - Add a more complicated test for custom properties loop eliminiation.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/185016/diff/2-3/

Comment 18

[Xidorn Quan [:xidorn] UTC+10]

Attachment: Servo PR

Comment 19

[Mozilla Autoland]

We're sorry - something has gone wrong while rewriting or rebasing your commits. The commits being pushed no longer match what was requested. Please file a bug.

Comment 20

[Mozilla Autoland]

We're sorry - something has gone wrong while rewriting or rebasing your commits. The commits being pushed no longer match what was requested. Please file a bug.

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/7898ef328bce
Add a more complicated test for custom properties loop eliminiation. r=SimonSapin

Comment 22

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/7898ef328bce