TL;DR
Researchers have developed TreePed, a tool that uses formal tree-rewriting logic to soundly identify redundant CSS rules in dynamic HTML5 applications. By modeling JavaScript DOM manipulations as monotonic tree updates and reducing the problem to symbolic pushdown systems, they can prove a CSS rule is truly obsolete, even in complex, script-heavy environments.
What Problem Does This Paper Address?
Modern web applications are often "bloated" with Cascading Style Sheets (CSS) rules that are never actually used. Studies show that in some industrial applications, up to 60% of CSS rules are redundant. This isn't just a matter of messy code; it increases bandwidth requirements and forces browsers to spend significant CPU time (up to 30%) parsing and matching selectors.
The challenge lies in JavaScript. Because scripts dynamically add, remove, or change classes on HTML elements, a CSS rule that looks unused at load time might be triggered later by a user action. Existing tools usually rely on dynamic analysis (testing the app and seeing what rules fire), which is never "sound"—it can’t prove a rule will never be used, leading to "false positives" where necessary styling is accidentally deleted.
Methods
The authors propose a static analysis framework based on Tree Rewriting Systems (TRS).
- Tree Representation: The HTML DOM is modeled as an unordered, unranked tree where nodes are labeled with sets of classes and tags.
- Event-Driven Abstraction: JavaScript and jQuery calls (like
.addClass(),.append(), or.remove()) are translated into a set of rewrite rules. These rules consist of a guard (a condition that must be met, like a CSS selector) and an operation (the change to the tree). - Monotonic Abstraction: To make the math tractable, the authors focus on "positive guards" (avoiding negations like
:not()). This creates a monotonic system where adding information to a tree doesn't invalidate previous matches, allowing for a "saturation" algorithm. - Algorithmic Reduction: The core of the solution is reducing the "redundancy problem" to a reachability analysis in Symbolic Pushdown Systems (sPDS). This allows the researchers to leverage highly optimized solvers like
jMopedto check if a specific CSS selector can ever match any node in any reachable state of the DOM.
Datasets
The authors evaluated their tool, TreePed, on several case studies:
- Igloo: A mock company website from the benchmark suite of Cilla (a competing dynamic analysis tool).
- Nivo-Slider: A popular, real-world jQuery plugin for image sliders, representing a complex script-heavy environment.
- Hand-built examples:
bikes.html,comments.html, andtransactions.html, designed to test frequent DOM additions and removals via AJAX. - Tutorial examples: A modified version of a dynamic input field tutorial.
Key Insights and Ideas
- The "Simplicity" of DOM Updates: Despite JavaScript being Turing-complete and notoriously hard to analyze, the authors observed that the actual tree updates performed by most web apps are remarkably simple. This makes tree-rewriting a perfect intermediate language.
- Soundness over Completeness: Unlike dynamic tools that guess what is redundant, TreePed aims for soundness. If TreePed says a rule is redundant, it is definitely redundant within the modeled fragment. This prevents the "broken UI" bugs common with aggressive CSS purgers.
- Complexity vs. Practice: While they proved the general redundancy problem is EXP-complete, they found that for the types of trees and rules found in actual web development, the analysis is efficient enough for practical use.
Key Results
- Accuracy: In the
Igloocase study, TreePed correctly identified that the.touchedclass was reachable via a JavaScript polyfill for placeholder text. Both Cilla and UnCSS (popular industry tools) incorrectly flagged it as redundant. - Efficiency: For the
Nivo-Sliderplugin (501 lines of JS), TreePed abstracted the logic into just 21 rewrite rules and analyzed 172 CSS selectors in 6.3 seconds. - Redundancy Detection: In the
Nivo-Sliderdemo, TreePed identified 131 out of 172 rules as redundant. In contrast, UnCSS reported 152, meaning it would have deleted 21 rules that were actually necessary for the app to function correctly.
Limitations and Future Work
- Prototype Translator: The current tool uses a "proof-of-concept" translator for JavaScript/jQuery. It doesn't handle the full, messy reality of the JavaScript language (like complex data-flow or all library features).
- Negation: The monotonic model struggles with the CSS
:not()selector. While the authors suggest over-approximating these as "always true," it leads to less precise results. - Future Integration: The authors suggest that their tree-rewriting model could be integrated into more robust JavaScript static analyzers (like TAJS or WALA) to create a production-ready CSS optimizer.
Summary updated