CSS Minification via Constraint Solving

Matthew Hague, Anthony Lin, Chih-Duo Hong

Research output: Contribution to journalArticlepeer-review

74 Downloads (Pure)

Abstract

Minification is a widely-accepted technique which aims at reducing the size of
the code transmitted over the web. This paper concerns the problem of
semantic-preserving minification of Cascading Style Sheets (CSS) --- the de
facto language for styling web documents --- based on merging similar rules.

The cascading nature of CSS makes the semantics of CSS files sensitive to the
ordering of rules in the file. To automatically identify rule-merging
opportunities that best minimise file size, we reduce the rule-merging problem
to a problem concerning ``CSS-graphs'', i.e., node-weighted bipartite graphs
with a dependency ordering on the edges, where weights capture the number of
characters.

Constraint solving plays a key role in our approach. Transforming a CSS file into
a CSS-graph problem requires us to extract the dependency ordering on the edges (an NP-hard problem), which requires us to solve the selector intersection
problem. To this end, we provide the first full formalisation of CSS3 selectors
(the most stable version of CSS) and reduce their selector intersection problem
to satisfiability of quantifier-free integer linear arithmetic, for which
highly-optimised SMT-solvers are available. To solve the above NP-hard graph
optimisation problem, we show how Max-SAT solvers can be effectively employed. We have implemented our rule-merging algorithm, and tested it against approximately 70 real-world examples (including examples from each of the top 20 most popular websites).

We also used our benchmarks to compare our tool against six well-known minifiers (which implement other optimisations). Our experiments suggest that our tool produced larger savings. A substantially better minification rate was shown when our tool is used together with these minifiers.
Original languageEnglish
Article number12
Pages (from-to)1-76
Number of pages76
JournalACM Transactions on Programming Languages and Systems
Volume41
Issue number2
DOIs
Publication statusPublished - 21 Jun 2019

Keywords

  • CSS
  • Web optimization
  • Semantics
  • Max-SAT

Cite this