{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:12:28Z","timestamp":1755839548315,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T00:00:00Z","timestamp":1686009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["SaTC-1908494, ITE-2132318, CCF-2122950, ITE-2029457, ITE-1936731, CCF-1918027, IIS-1924435"],"award-info":[{"award-number":["SaTC-1908494, ITE-2132318, CCF-2122950, ITE-2029457, ITE-1936731, CCF-1918027, IIS-1924435"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HARDEN, FA8750-16-2-0032"],"award-info":[{"award-number":["HARDEN, FA8750-16-2-0032"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Faculty Research Award"],"award-info":[{"award-number":["Faculty Research Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,6,6]]},"abstract":"<jats:p>Modern web browsers rely on layout engines to convert HTML documents to layout trees that specify color, size, and position. However, existing layout engines are notoriously difficult to maintain because of the complexity of web standards. This is especially true for incremental layout engines, which are designed to improve performance by updating only the parts of the layout tree that need to be changed.<\/jats:p>\n          <jats:p>In this paper, we propose Medea, a new framework for automatically generating incremental layout engines. Medea separates the specification of the layout engine from its incremental implementation, and guarantees correctness through layout engine synthesis. The synthesis is driven by a new iterative algorithm based on detecting conflicts that prevent optimality of the incremental algorithm.<\/jats:p>\n          <jats:p>We evaluated Medea on a fragment of HTML layout that includes challenging features such as margin collapse, floating layout, and absolute positioning. Medea successfully synthesized an incremental layout engine for this fragment. The synthesized layout engine is both correct and efficient. In particular, we demonstrated that it avoids real-world bugs that have been reported in the layout engines of Chrome, Firefox, and Safari. The incremental layout engine synthesized by Medea is up to 1.82\u00d7 faster than a naive incremental baseline. We also demonstrated that our conflict-driven algorithm produces engines that are 2.74\u00d7 faster than a baseline without conflict analysis.<\/jats:p>","DOI":"10.1145\/3591246","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T20:06:24Z","timestamp":1686081984000},"page":"638-659","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Conflict-Driven Synthesis for Layout Engines"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9656-7073","authenticated-orcid":false,"given":"Junrui","family":"Liu","sequence":"first","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6494-3126","authenticated-orcid":false,"given":"Yanju","family":"Chen","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8396-1258","authenticated-orcid":false,"given":"Eric","family":"Atkinson","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1000-1229","authenticated-orcid":false,"given":"Yu","family":"Feng","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6639-1647","authenticated-orcid":false,"given":"Rastislav","family":"Bodik","sequence":"additional","affiliation":[{"name":"Google, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/320719.322588"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032305.2032319"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642918.2647357"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/266180.266361"},{"key":"e_1_2_1_5_1","unstructured":"Bert Bos. 2016. CSS 2.2: Collapsing Margins. https:\/\/tinyurl.com\/j66mfru \t\t\t\t  Bert Bos. 2016. CSS 2.2: Collapsing Margins. https:\/\/tinyurl.com\/j66mfru"},{"key":"e_1_2_1_6_1","unstructured":"Bert Bos Tantek \u00c7elik Ian Hickson and H\u00e5kon Wium Lie. 2011. CSS 2.1: Collapsing Margins. https:\/\/tinyurl.com\/rspsl2j \t\t\t\t  Bert Bos Tantek \u00c7elik Ian Hickson and H\u00e5kon Wium Lie. 2011. CSS 2.1: Collapsing Margins. https:\/\/tinyurl.com\/rspsl2j"},{"key":"e_1_2_1_7_1","volume-title":"Chris Lilley, and Ian Jacobs.","author":"Bos Bert","year":"1998","unstructured":"Bert Bos , H\u00e5kon Wium Lie , Chris Lilley, and Ian Jacobs. 1998 . CSS 2: Collapsing Margins . https:\/\/tinyurl.com\/seb5h92 Bert Bos, H\u00e5kon Wium Lie, Chris Lilley, and Ian Jacobs. 1998. CSS 2: Collapsing Margins. https:\/\/tinyurl.com\/seb5h92"},{"key":"e_1_2_1_8_1","unstructured":"Browserling. 2018. https:\/\/www.browserling.com\/ \t\t\t\t  Browserling. 2018. https:\/\/www.browserling.com\/"},{"key":"e_1_2_1_9_1","unstructured":"Browsershots. 2018. http:\/\/browsershots.org\/ \t\t\t\t  Browsershots. 2018. http:\/\/browsershots.org\/"},{"key":"e_1_2_1_10_1","unstructured":"Browserstack. 2018. https:\/\/www.browserstack.com\/screenshots \t\t\t\t  Browserstack. 2018. https:\/\/www.browserstack.com\/screenshots"},{"key":"e_1_2_1_11_1","unstructured":"Matt Brubeck. 2014. Incorrect layout of element following a float involving margins. https:\/\/github.com\/servo\/servo\/issues\/4307 \t\t\t\t  Matt Brubeck. 2014. Incorrect layout of element following a float involving margins. https:\/\/github.com\/servo\/servo\/issues\/4307"},{"key":"e_1_2_1_12_1","unstructured":"Matt Brubeck. 2021. The Robinson Layout Engine. https:\/\/github.com\/mbrubeck\/robinson \t\t\t\t  Matt Brubeck. 2021. The Robinson Layout Engine. https:\/\/github.com\/mbrubeck\/robinson"},{"key":"e_1_2_1_13_1","unstructured":"caniuse. 2019. Compare Firefox 51 Firefox 58 Chrome 56 and Chrome 64. https:\/\/caniuse.com\/#compare=firefox+51 firefox+58 chrome+56 chrome+6&compare_cats=CSS \t\t\t\t  caniuse. 2019. Compare Firefox 51 Firefox 58 Chrome 56 and Chrome 64. https:\/\/caniuse.com\/#compare=firefox+51 firefox+58 chrome+56 chrome+6&compare_cats=CSS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507751"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2012.97"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908103"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_18_1","unstructured":"Emil Eklund. 2019. LayoutNG. https:\/\/www.chromium.org\/blink\/layoutng \t\t\t\t  Emil Eklund. 2019. LayoutNG. https:\/\/www.chromium.org\/blink\/layoutng"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192382"},{"key":"e_1_2_1_20_1","unstructured":"Github. 2013. Electron | Build cross platform desktop apps with JavaScript HTML and CSS. https:\/\/electronjs.org\/ \t\t\t\t  Github. 2013. Electron | Build cross platform desktop apps with JavaScript HTML and CSS. https:\/\/electronjs.org\/"},{"key":"e_1_2_1_21_1","unstructured":"LLC Gurobi Optimization. 2019. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com \t\t\t\t  LLC Gurobi Optimization. 2019. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com"},{"key":"e_1_2_1_22_1","volume-title":"Verification and Validation (ICST), 2015 IEEE 8th International Conference on. IEEE","author":"Hall\u00e9 Sylvain","year":"2015","unstructured":"Sylvain Hall\u00e9 , Nicolas Bergeron , Francis Guerin , and Gabriel Le Breton . 2015 . Testing Web Applications Through Layout Constraints. In Software Testing , Verification and Validation (ICST), 2015 IEEE 8th International Conference on. IEEE , Graz, Austria. 1\u20138. Sylvain Hall\u00e9, Nicolas Bergeron, Francis Guerin, and Gabriel Le Breton. 2015. Testing Web Applications Through Layout Constraints. In Software Testing, Verification and Validation (ICST), 2015 IEEE 8th International Conference on. IEEE, Graz, Austria. 1\u20138."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/142621.142635"},{"key":"e_1_2_1_24_1","unstructured":"Anantha Keesara. 2007. Bug 15662 - layout is coming down because of style \u2019float:left\u2019 of <div>. https:\/\/bugs.webkit.org\/show_bug.cgi?id=15662 \t\t\t\t  Anantha Keesara. 2007. Bug 15662 - layout is coming down because of style \u2019float:left\u2019 of <div>. https:\/\/bugs.webkit.org\/show_bug.cgi?id=15662"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Donald E. Knuth. 1968. Semantics of Context-Free Languages. In In Mathematical Systems Theory. 127\u2013145. \t\t\t\t  Donald E. Knuth. 1968. Semantics of Context-Free Languages. In In Mathematical Systems Theory. 127\u2013145.","DOI":"10.1007\/BF01692511"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1939141.1939161"},{"key":"e_1_2_1_27_1","volume-title":"Automated Repair of Mobile Friendly Problems in Web Pages. In International Conference on Software Engineering (ICSE","author":"Mahajan Sonal","year":"2018","unstructured":"Sonal Mahajan , Negarsadat Abolhassani , Phil McMinn , and William G.J. Halfond . 2018 . Automated Repair of Mobile Friendly Problems in Web Pages. In International Conference on Software Engineering (ICSE 2018 ). ACM, 140\u2013150. Sonal Mahajan, Negarsadat Abolhassani, Phil McMinn, and William G.J. Halfond. 2018. Automated Repair of Mobile Friendly Problems in Web Pages. In International Conference on Software Engineering (ICSE 2018). ACM, 140\u2013150."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092703.3092726"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2018.00030"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985870"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442535"},{"key":"e_1_2_1_32_1","unstructured":"Mozilla. 2019. Margins collapse on body element that creates a BFC. https:\/\/tinyurl.com\/v2284y6 \t\t\t\t  Mozilla. 2019. Margins collapse on body element that creates a BFC. https:\/\/tinyurl.com\/v2284y6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322198"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192407"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984010"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSM.2010.5609723"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314626"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 1996 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201996)","author":"Jo\u00e3o","year":"1867","unstructured":"Jo\u00e3o P. Marques Silva and Karem A. Sakallah. 1997. GRASP\u2014a New Search Algorithm for Satisfiability . In Proceedings of the 1996 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201996) . IEEE Computer Society, USA. 220\u2013227. isbn:08 1867 5977 Jo\u00e3o P. Marques Silva and Karem A. Sakallah. 1997. GRASP\u2014a New Search Algorithm for Satisfiability. In Proceedings of the 1996 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201996). IEEE Computer Society, USA. 220\u2013227. isbn:0818675977"},{"volume-title":"Program Synthesis by Sketching. Ph. D. Dissertation","author":"Solar-Lezama Armando","key":"e_1_2_1_40_1","unstructured":"Armando Solar-Lezama . 2008. Program Synthesis by Sketching. Ph. D. Dissertation . Berkeley, CA, USA . isbn:978-1-109-09745-0 AAI 3353225 Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph. D. Dissertation. Berkeley, CA, USA. isbn:978-1-109-09745-0 AAI3353225"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168919.1168907"},{"key":"e_1_2_1_42_1","unstructured":"stshine. 2016. Floats fails to interact with inline elements in the simplest case. https:\/\/github.com\/servo\/servo\/issues\/13683 \t\t\t\t  stshine. 2016. Floats fails to interact with inline elements in the simplest case. https:\/\/github.com\/servo\/servo\/issues\/13683"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800265.810742"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509586"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660208"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/357299.357303"},{"key":"e_1_2_1_48_1","unstructured":"W3C. 2007. CSS basic box model. http:\/\/www.w3.org\/TR\/css3-box \t\t\t\t  W3C. 2007. CSS basic box model. http:\/\/www.w3.org\/TR\/css3-box"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092703.3092712"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.31"},{"key":"e_1_2_1_51_1","unstructured":"Patrick Walton. 2014. Block formatting contexts should never collapse margins. https:\/\/github.com\/servo\/servo\/issues\/10449 \t\t\t\t  Patrick Walton. 2014. Block formatting contexts should never collapse margins. https:\/\/github.com\/servo\/servo\/issues\/10449"},{"volume-title":"The Grammar of Graphics (Statistics and Computing)","author":"Wilkinson Leland","key":"e_1_2_1_52_1","unstructured":"Leland Wilkinson . 2005. The Grammar of Graphics (Statistics and Computing) . Springer-Verlag New York, Inc. , Secaucus, NJ, USA . isbn:0387245448 Leland Wilkinson. 2005. The Grammar of Graphics (Statistics and Computing). Springer-Verlag New York, Inc., Secaucus, NJ, USA. isbn:0387245448"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/108844.109005"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591246","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:47Z","timestamp":1750178867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":53,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2023,6,6]]}},"alternative-id":["10.1145\/3591246"],"URL":"https:\/\/doi.org\/10.1145\/3591246","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2023,6,6]]},"assertion":[{"value":"2023-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}