CSS Minification via Constraint Solving. / Hague, Matthew; Lin, Anthony; Hong, Chih-Duo.

In: ACM Transactions on Programming Languages and Systems, Vol. 41, No. 2, 12, 21.06.2019, p. 1-76.

Research output: Contribution to journalArticle

Published

Documents

  • Accepted Manuscript

    Rights statement: © ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn (Details to be added on publication.)

    Accepted author manuscript, 829 KB, PDF document

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 33183303