Detecting Redundant CSS Rules in HTML5
Applications: A Tree Rewriting Approach
Anthony W. Lin (with Matthew Hague and Luke Ong)

Yale-NUS College, Singapore
Royal Holloway, University of London, UK
Oxford University, UKIntroduction to Webpages<html><head><title>Super Heroes</title><style>.side-img { float: left; height: 3cm;}.info { background-color: lightgray; }.info > .name { font-weight: bold; }.info > .date { font-style: italic; }</style></head><body><h1>Super Heroes</h1><img class="side-img" src="superman.jpg"/><div class="info"><div class="name">Superman</div><div class="date"/></div><button class="del">Delete</button><script src="jquery-1.9.0.min.js"></script><script>$(document).ready(function() {// add date$(".info > .date").html("1938");// remove if clicked$(’.del’).click(function(e){$(’.side-img’).remove();$(’.info’).remove();$(’.del’).remove();});});</script></body></html>A webpage has three main components...

Introduction to Webpages<body><h1>Super Heroes</h1><img class="side-img"
src="superman.jpg"/><div class="info"><div class="name">Superman</div><div class="date"/></div><button class="del">Delete</button></body>The Document Object Model (DOM) tree.

Introduction to Webpages<script>$(document).ready(function() {// add date$(".info > .date").html("1938");// remove if clicked$(’.del’).click(function(e){$(’.side-img’).remove();$(’.info’).remove();$(’.del’).remove();});});</script>

A dynamic / scripting component.

Introduction to Webpages<script>$(document).ready(function() {// add date$(".info > .date").html("1938");// remove if clicked$(’.del’).click(function(e){$(’.side-img’).remove();$(’.info’).remove();$(’.del’).remove();});});</script>

A dynamic / scripting component.

Introduction to Webpages<style>.side-img { float: left; }.info { background-color: lightgray; }.info > .name { font-weight: bold; }.info > .date { font-style: italic; }</style>The CSS component.

The CSS Redundancy Problem
CSS Stylesheets can become very large.

Usual development bloat (e.g. plugins with generic stylesheets).
E.g. Nivo-Slider has 172 selectors, 131 redundant in demo above.

The CSS Redundancy Problem
CSS Stylesheets can become very large.

Usual development bloat (e.g. plugins with generic stylesheets).
E.g. Nivo-Slider has 172 selectors, 131 redundant in demo above.
60% of them are redundant... [Mesbah and Mirshokraie]
30% of rendering time is spent on selectors [Meyerovich andBodik].

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.
Both of these approaches can remove useful CSS rules.
This can ruin the look of your website.

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.
Both of these approaches can remove useful CSS rules.
This can ruin the look of your website.

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.
Both of these approaches can remove useful CSS rules.
This can ruin the look of your website.

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.
Both of these approaches can remove useful CSS rules.
This can ruin the look of your website.

Existing Solutions

Existing tools for cleaning CSS are quite limited:
Cilla [Mesbah and Mirshokraie] and UnCSS [Martino]
Explores as much of a page as it can.
Reports which selectors were not used.
Unsound.
Both of these approaches can remove useful CSS rules.
This can ruin the look of your website.
And break functionality (UnCSS breaks Nivo-Slider).

Static Analysis?

Static Analysis?

Leading tools: WALA and TAJSStatic Analysis?

Leading tools: WALA and TAJS
Using them to identify redundant CSS is challenging.

Static Analysis?

Leading tools: WALA and TAJS
Using them to identify redundant CSS is challenging.
Problem 1: Call graph of JS+jQuery is hard to construct

Static Analysis?

Leading tools: WALA and TAJS
Using them to identify redundant CSS is challenging.
Problem 1: Call graph of JS+jQuery is hard to construct
Problem 2: DOM tree is not precisely tracked

Static Analysis?

Leading tools: WALA and TAJS
Using them to identify redundant CSS is challenging.
Problem 1: Call graph of JS+jQuery is hard to construct
Problem 2: DOM tree is not precisely tracked
See Andreasen and Moller’14 for an up-to-date survey on static analysis of JavaScript+jQuery.

Our Contributions

Clean tree-rewriting model of DOM dynamics due to JS.
PreciseAutomatic analysis (via reduction to symbolic pushdown systems)Our Contributions

Clean tree-rewriting model of DOM dynamics due to JS.
PreciseAutomatic analysis (via reduction to symbolic pushdown systems)
Proof-of-concept translation from HTML5 to our model.
Models jQuery functions in how they modify the DOM.
Does not yet support many features of JavaScript.

Our Contributions

Clean tree-rewriting model of DOM dynamics due to JS.
PreciseAutomatic analysis (via reduction to symbolic pushdown systems)
Proof-of-concept translation from HTML5 to our model.
Models jQuery functions in how they modify the DOM.
Does not yet support many features of JavaScript.
Promising experimental results.

Our approach (in a nutshell)

Aim to overapproximate DOM dynamics with tree-rewritingmodel ROur approach (in a nutshell)Aim to overapproximate DOM dynamics with tree-rewriting
model R
Redundant node selectors in R ⇒ redundant in HTML5

Our Tree-Rewriting Model: Domain<body >
<h1 > <img > <div info ><div name > <div date >DOM is abstracted as an (unordered) unranked tree with class labels.

Our Tree-Rewriting Model: Domain<body >
<h1 > <img > <div info ><div name > <div date >DOM is abstracted as an (unordered) unranked tree with class labels.
HTML elements and node IDs are treated as constant classes

Our Tree-Rewriting Model: Rewrite Rules

A rewrite rule is a pair (g, χ), where:g is a “guard” (a.k.a. “node selector”): modal logic formula withmodalities ⟨↑⟩, ⟨↑+⟩, ⟨↓⟩, ⟨↓+⟩,
χ is a rewrite operation: AddClass, AddChild, RemoveClass,RemoveNode.

Our Tree-Rewriting Model: Rewrite Rules

A rewrite rule is a pair (g, χ), where:g is a “guard” (a.k.a. “node selector”): modal logic formula withmodalities ⟨↑⟩, ⟨↑+⟩, ⟨↓⟩, ⟨↓+⟩,
χ is a rewrite operation: AddClass, AddChild, RemoveClass,RemoveNode.
A tree-rewrite system is a finite set of rewrite rules.

Examples<body ><h1 > <img > <div info ><div name > <div date >A jQuery line$(".info").appendChild("<div class=’comic’>DC Comics</div>")

is represented by(info, AddChild(div comic))

Examples<body >
<h1 > <img > <div info ><div name > <div date > <div comic >A jQuery line$(".info").appendChild("<div class=’comic’>DC Comics</div>")

is represented by(info, AddChild(div comic))

Examples<body >
<h1 > <img > <div info ><div name > <div date > <div comic >A CSS Selector.info > .date { font-style: italic; }can be represented by(date ∧ ⟨↑⟩info, AddClass(cssrule1))

Operational Semantics of TRS

T1 →R T2 if T1 can be rewritten into T2i.e. ∃ a node v in T1 where some rule (g, χ) in R can be “fired”.

Redundancy Problem

a TRS R, an initial DOM tree T ,and a S set of node selectors
QUESTION : Identify selectors in S that cannot be matched(in all reachable trees)

INPUT :

Solving the Redundancy Problem
Q: given a tree, rules and classes, which classes are redundant?

Solving the Redundancy Problem
Q: given a tree, rules and classes, which classes are redundant?
CSS redundancy is undecidable in generalSolving the Redundancy Problem
Q: given a tree, rules and classes, which classes are redundant?
CSS redundancy is undecidable in general
In practice, suﬃces to restrict to positive guards

Solving the Redundancy Problem
Q: given a tree, rules and classes, which classes are redundant?
CSS redundancy is undecidable in general
In practice, suﬃces to restrict to positive guards
e.g. date ∧ ⟨↑⟩infoSolving the Redundancy Problem
Q: given a tree, rules and classes, which classes are redundant?
CSS redundancy is undecidable in general
In practice, suﬃces to restrict to positive guards
e.g. date ∧ ⟨↑⟩info
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.

The Reduction
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.
One boolean variable for each classThe Reduction
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.
One boolean variable for each class
Stack used in a “depth-first search” of the tree.

The Reduction
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.
One boolean variable for each class
Stack used in a “depth-first search” of the tree.
New nodes can be created by pushing onto the stack.

The Reduction
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.
One boolean variable for each class
Stack used in a “depth-first search” of the tree.
New nodes can be created by pushing onto the stack.
Backtrack by popping.

The Reduction
Theorem: The redundancy problem for positive TRS iseﬃciently reducible to analysis of symbolic PDS,
which is EXP-complete, but for which fastsolvers exist.
One boolean variable for each class
Stack used in a “depth-first search” of the tree.
New nodes can be created by pushing onto the stack.
Backtrack by popping.
(Since guards are positive, we can always recreate nodes.)Implementation

We implemented a tool TreePed to test the approach.
A rough tool for extracting rules from jQuery script.
jMoped used as a pushdown backend.
Tested on a number of examples (next slide).
Reasonable run times.
Identified all and only redundant rules.
Two real-world examples, five made up examples.

Results TableCase Study

NsSs

Ls Rs Timebikes.html
2218 (0)97comments.html
513 (1)43
example.html
111 (0)28
example-up.html
81 (1)
15
igloo/
261 (89)
index.html
145
24
engineering.html 236
24
Nivo-Slider/demo.html
15 172 (131) 501
transactions.html 199 (0)
37

37
26
4
3

3.6s
2.9s
.6s
.6s
3.4s

1
1
21
6

6.3s
1.6s

Ns — # of HTML elements in the initial tree
Ss — # of CSS rules (redundant CSS rules)
Ls — # of lines of JavaScript (cloc)
Rs — # of rules extracted from JS

Summary and Future WorkWeb pages are dynamic programs:
Manipulate a tree data structure (DOM).
Can be modelled by tree rewrite systems.
Model-checking can be used for optimising CSS rules.
Future work:
Systematically extracting rewrite rules from JavaScript.
JavaScript analysis is hard! (c.f. Moller et al)