25:["$","title",null,{"children":"Pretty Printing | Dylan Freedman | Observable"}] 4b:T5ca,md`## The Pretty Printing Algorithm So, now we are equipped with a structure to describe how we might want to format documents and are ready to develop our pretty printing algorithm. We'll follow the approach outlined by Philip Wadler in ["A Prettier Printer"](https://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf) (2003), which is a modern version of Derek Oppen's 1980 paper ["Prettyprinting"](https://www.cs.tufts.edu/~nr/cs257/archive/derek-oppen/prettyprinting.pdf). Let's outline our approach and some helper methods. The crux is we want a method that consumes the document sequentially and outputs formatted text as it goes. The method should only have to look ahead a line at a time, and essentially it should optimistically try to place everything on the same line if possible, only breaking lines if needed. The three helper methods that we'll define below are as follows: * *lazy*: wraps a function so that it only has to be computed once and then the value is cached thereafter * *layout*: returns a structure which stores some formatted text and a lazy function that returns the next layout structure (functions as a lazy linked list) * *fits*: returns if there's enough room on the current line to output the passed in layout structure We are setting up routines to lazily evaluate layout possibilities, which allows us to only compute what's needed in a performant manner while retaining the ability to express an exponential pool of possibilities.`4c:T4b7,function best(maxLineWidth, lineWidth, documentPairs) { if (documentPairs.length == 0) return layout('null'); // end of layout chain // Grab current indentation level and document from head of list const [indent, doc] = documentPairs[0]; const nextDocs = documentPairs.slice(1); // Convenience function to recurse const _best = (newDocs=[], lw=lineWidth) => { return best(maxLineWidth, lw, newDocs.concat(nextDocs)); }; if (doc.type == 'nil') return _best(); if (doc.type == 'concat') return _best(doc.docs.map(doc => [indent, doc])); if (doc.type == 'nest') return _best([[indent + doc.indent, doc.doc]]); if (doc.type == 'union') { // See if first doc in union fits; if not, use second const doc1 = _best([[indent, doc.a()]]); if (fits(maxLineWidth - lineWidth, doc1)) return doc1; return _best([[indent, doc.b()]]); } // Text and lines output layout chains if (doc.type == 'text') { const newLineWidth = lineWidth + doc.text.length; return layout('text', doc.text, lazy(() => _best([], newLineWidth)), doc.color); } if (doc.type == 'line') { return layout('line', `\n${' '.repeat(indent)}`, lazy(() => _best([], indent))); } }4d:T7ea,function draw(lineWidth, nodes, showScroll=true, fontHeight = drawFontHeight) { const maxHeight = 300; const lineCount = nodes.reduce((x, y) => y.text.split('\n').length + x - 1, 0) + 1; const allText = nodes.reduce((x, y) => x + y.text, ''); const maxLineLength = allText.split('\n').reduce((x, y) => Math.max(x, y.length), 0); const ctx = DOM.context2d(width, maxHeight); ctx.font = `bold ${fontHeight}px Courier New, Courier, monospace`; const letterWidth = ctx.measureText('M').width; function _draw(yOffset = 0, xOffset = 0) { ctx.clearRect(0, 0, width, maxHeight); let x = -xOffset; let y = -yOffset + drawLineHeight * fontHeight; for (const {text, color} of nodes) { ctx.fillStyle = color || 'black'; const lines = text.split('\n'); for (let i = 0; i < lines.length; i++) { const line = lines[i]; if (i != 0) { y += fontHeight * drawLineHeight; x = -xOffset; } ctx.fillText(line, x, y); x += line.length * letterWidth; } } ctx.beginPath(); ctx.strokeStyle = 'gainsboro'; ctx.setLineDash([4, 4]); ctx.moveTo(lineWidth * letterWidth - xOffset, 0); ctx.lineTo(lineWidth * letterWidth - xOffset, 500); ctx.stroke(); } _draw(); const scroller = showScroll ? html`

` : ''; if (showScroll) { scroller.onscroll = e => { _draw(scroller.scrollTop, scroller.scrollLeft); } } return html`

${scroller} ${ctx.canvas}

`; }4e:[] 47:{"id":"b8e5d54b82624bf3","slug":"pretty-printing","title":"Pretty Printing","thumbnail":"e12b3822eb89e6a8b5758f67e881255d7b219b06b9f9dd92ddbc23bdfde62ba1","access_level":"public","create_time":"$D2021-02-07T17:27:50.523Z","update_time":"$D2022-11-20T15:56:22.154Z","view_time":null,"first_public_time":"$D2021-02-15T17:36:51.056Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"38ab6d7c2dc7f1de","login":"freedmand","name":"Dylan Freedman","avatar_url":"https://avatars-next.observableusercontent.com/d56e4f48a1c7d706179444fea717006647786e759cefe364af89e5f63f473b8a","tier":"starter_2024","bio":"Senior software engineer at the Washington Post\nCreating Poly, a new programming language for the web (poly.dev)","following":false},"version":1342,"publish_version":1342,"role":null,"authored":false,"authors":[{"type":"individual","id":"571a5f35aafb86e1","login":"freedmand","name":"Dylan Freedman","avatar_url":"https://avatars-next.observableusercontent.com/d56e4f48a1c7d706179444fea717006647786e759cefe364af89e5f63f473b8a","tier":null,"bio":"Machine learning / AI Initiatives at the New York Times. Creating Poly, a new programming language for the web (poly.dev)","following":false}],"members":[{"type":"individual","id":"571a5f35aafb86e1","login":"freedmand","name":"Dylan Freedman","avatar_url":"https://avatars-next.observableusercontent.com/d56e4f48a1c7d706179444fea717006647786e759cefe364af89e5f63f473b8a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Pretty Printing","cells":[{"id":0,"value":"doc = md`# Pretty Printing\n\n*A brief primer on how code auto-formatters work*\n\nPretty printing is an art and a science — the distinctly human endeavor of formatting code to look *pretty*.\n\nI recently learned about how pretty printers work after I implemented one for my early-stage programming language, [Poly](poly.dev), to formalize the language's style. In the process of researching pretty printers, I was amazed to find that the technique is over 40 years old and the elegant underlying algorithm back then is still in use in modern, popular tools like [Prettier](https://prettier.io/).\n\nIn this computational essay, we'll build an HTML formatter (and a bonus syntax highlighter) from the ground up to learn how pretty printing works.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":461,"value":"{\n await visibility(); // only render if visible\n return table(\n draw(demoLineWidth, prettyHtml(demoLineWidth, documentNodes), false, 12),\n 0.8,\n draw(demoLineWidth, prettyHtml(demoLineWidth, documentNodes), false, 2),\n 0.2,\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":656,"value":"md`*real-time formatting of the source code of this notebook (computed in-browser)*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":684,"value":"md`## Overview\n\nWhy format source code? In addition to making code look nicer, formatters...\n\n* **help catch bugs** — formatted code reveals mistakes like mismatched braces.\n* **unify code style** — eliminate debates on appropriate style by enforcing one.\n* **improve developer experience** — make working with code editors pleasant. For example, the *\"Format on save\"* option provided in apps like Visual Studio Code is a satisfying way to prettify error-free code every time you hit save.\n* **result in concise diffs** — repositories like GitHub show new changes, or *diffs*, in source code. Some formatting approaches aim to make diffs as small as possible for minor tweaks.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":739,"value":"md`## Documents\n\nA *document* is a tree-like structure that can contain text, newlines, nested blocks, and unions of multiple possible layouts. The purpose of the document type is to provide the building blocks to represent how we want source text to be formatted. Here's how we define our document structure:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"Doc = ({\n // An empty document\n nil: {type: 'nil'},\n\n // A text document (optional color for syntax highlighting)\n text: (text, color='black') => ({type: 'text', text, color}),\n\n // A newline separator that flattens to a space by default\n line: (reducedText=' ') => ({type: 'line', reducedText}),\n\n // An indented document\n nest: (indent, doc) => ({type: 'nest', indent, doc}),\n \n // The concatenation, or joining, of multiple documents\n concat: (docs) => ({type: 'concat', docs}),\n\n // A union of documents that favors `a` if there's room\n union: (a, b) => ({type: 'union', a, b}),\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":920,"value":"md`### Text\n\nThe simplest type of document is a *text document*, which just contains some text. Text documents should not contain newline characters, since line breaks are handled specially.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":780,"value":"md`### Line\n\n*Line documents* represent line breaks and are useful in handling indentation and other behavior. Documents can be flattened to a single line with a flatten method we'll define below; when flattened, line breaks turn into the specified reduced text, typically a space or empty string.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":806,"value":"md`### Concatenation\n\n*Concatenation documents* take a list of documents and join them into one document. For instance, the example below illustrates joining text and line documents to display some multi-line text.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":788,"value":"display(\n Doc.concat([\n Doc.text(\"Hello\"),\n Doc.line(),\n Doc.text(\"world\"),\n ]),\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":811,"value":"md`### Nesting\n\nIndentation is commonly used in formatting to represent enclosed data. A *nest document* takes in a number and a sub-document, representing indenting the sub-document passed in a number of spaces. In practice, indenting means each occurrence of a newline is prepended with a number of spaces.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":814,"value":"display(\n Doc.concat([\n Doc.text('['),\n Doc.nest(2, Doc.concat([\n Doc.line(),\n Doc.text('arrayElement,'),\n ])),\n Doc.line(),\n Doc.text(']'),\n ])\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":837,"value":"md`### Union\n\nA *union document* is the secret sauce to pretty printing. The other document types just define a fixed layout, with no mechanism to handle text wrapping. A union document stores two sub-documents that flatten to the same layout, where the first one has a longer first line. When pretty printing, the first document of the union is tried, and if the maximum line width is exceeded, the second document is rendered instead.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":854,"value":"displaySmallAndLargeWidth(\n Doc.union(() => Doc.concat([Doc.text(\"Hi\"), Doc.text(' '), Doc.text(\"there\")]),\n () => Doc.concat([Doc.text(\"Hi\"), Doc.line(), Doc.text(\"there\")])),\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":873,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":601,"value":"// Take in a function and wrap it so that the function is cached\n// on first invocation and returns results instantly thereafter.\nfunction lazy(closure) {\n let cached = null;\n return () => cached == null ? (cached = closure()) : cached;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"function layout(type, text=null, next=null, color='black') {\n // Type can be \"text\", \"line\", or \"nil\"\n return {type, text, color, next};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"function fits(remainingWidth, layoutDoc) {\n if (remainingWidth < 0) return false;\n if (layoutDoc.type == 'text') {\n return fits(remainingWidth - layoutDoc.text.length, layoutDoc.next());\n }\n // If the layout is of type `line` or `nil` it always fits.\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":995,"value":"md`We're ready to define the *best* method, which finds the ideal layout structure given a *max line width* and document. To make the function work well, it's a recursive method that is actually passed a list of *document pairs*, which each contain a document structure and that document's current level of indentation. The method is also passed the *line width*, to account for how much room is left in the current line.\n\nThe method proceeds by examining the first document pair and recursively calling itself as necessary, expanding the list of document pairs to examine based on the first document type. Union documents are picked apart with the *fits* method, expanding to use the first document if there is room and the second if not. When text and line documents are encountered, they output layout structures which we can unravel later to reconstruct the formatted text.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1012,"value":"md`Once *best* returns, it will output a layout structure, which is a linked list of text and lines. Let's add a convenience method to *unravel* the layout, which converts this linked list into an array of \\`{text, color}\\` objects which can then be rendered to the screen!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":155,"value":"function unravelLayout(layoutDoc) {\n const results = [];\n while (layoutDoc.type != 'null') {\n results.push({text: layoutDoc.text, color: layoutDoc.color});\n layoutDoc = layoutDoc.next();\n }\n return results;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1094,"value":"function render(unraveledLayout) {\n const pre = document.createElement('pre');\n unraveledLayout.forEach(({color, text}) => {\n const span = document.createElement('span');\n span.style.color = color;\n span.textContent = text;\n pre.appendChild(span);\n });\n return pre;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1015,"value":"md`Finally, the *pretty* method combines all of the above, taking in the desired line width and the document and returning the unraveled best layout.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"function pretty(lineWidth, doc) {\n return unravelLayout(best(lineWidth, 0, [[0, doc]]));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1029,"value":"md`## Usage in Practice\n\nLet's see how one could make a text-wrapping formatter function in practice. The definition of *union* above had an example with the text \"Hi there\" on one line or two depending on avaialble width. That can be expressed as follows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1106,"value":"hiThere = Doc.union(() => Doc.concat([Doc.text(\"Hi\"), Doc.text(' '), Doc.text(\"there\")]),\n () => Doc.concat([Doc.text(\"Hi\"), Doc.line(), Doc.text(\"there\")]))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1113,"value":"md`Essentially, this union will display the text \"Hi\" and \"there\" separated by a space if there's room and a newline if there's not.`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1119,"value":"render(pretty(80, hiThere))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1123,"value":"render(pretty(5, hiThere))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1126,"value":"md`In practice, there are many use cases where you want text to go on the same line if possible and separate lines otherwise. To help construct formatters, certain helper functions are useful.\n\nThe *flatten* method takes a document and returns a version where everything occurs on the same line. It does this by converting line documents to their reduced text (typically space or empty text) and always picking the first option in a union (which will always be the longer line by definition).\n\nThe *group* function is a convenience method to automatically construct a union of the flattened version of a document with itself.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"function flatten(doc) {\n // Flatten always picks the first option in a union\n while (doc.type == 'union') doc = doc.a();\n\n if (doc.type == 'concat') return Doc.concat(doc.docs.map(flatten));\n if (doc.type == 'nest') return Doc.nest(doc.indent, flatten(doc.doc));\n // Convert lines to their reduced text\n if (doc.type == 'line') return Doc.text(doc.reducedText);\n\n // If doc is text or nil, it's unchanged\n return doc;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"function group(doc) {\n // Unions are evaluated lazily\n return Doc.union(lazy(() => flatten(doc)), lazy(() => doc));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1131,"value":"md`Our \"Hi there\" above example can be simplified with *group*:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1136,"value":"hiThere2 = group(Doc.concat([Doc.text(\"Hi\"), Doc.line(), Doc.text(\"there\")]))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1133,"value":"render(pretty(80, hiThere2))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1141,"value":"render(pretty(5, hiThere2))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":911,"value":"md`## Formatting HTML code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1019,"value":"md`Let's show a more practical pretty printer example. Generally, to put a pretty printer to use, we need to define methods on top of a parse tree to transform it into a document. As an example, we'll make a pretty printer for HTML, since the browser has built-in methods to parse HTML.\n\nLet's start by defining an HTML structure that can contain elements and text nodes:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"HTML = ({\n element: (tag, attrs={}, children=[]) => {\n const attributes = Object.entries(attrs);\n return {type: 'element', tag, attributes, children};\n },\n text: (text) => ({type: 'text', text}),\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1026,"value":"md`Below, we define helpers to format HTML code. *showHTML* traverses the HTML structure, calling *showTag* to render HTML tags. *showList* renders a list of items without spaces in-between and relies on *show* to ensure list items are grouped in a way so that HTML tags tend to have lines to themselves. *showAttribute* renders the key/value pair for an HTML element attribute.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":210,"value":"// HTML syntax-highlighting colors\nColor = ({\n tag: 'green',\n property: '#ae39e8',\n attribute: 'blue',\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"function showHTML(html) {\n if (html.type == 'element') {\n if (html.children.length == 0) {\n return [showTag(html, \"/>\")];\n } else {\n return [\n Doc.concat([showTag(html, \">\"),\n showList(showHTML, html.children),\n Doc.text(``, Color.tag)])\n ];\n }\n } else {\n return html.text.split(/\\s/).map(word => Doc.text(word));\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"function showTag(html, endTag) {\n const space = html.attributes.length > 0 ? ' ' : '';\n return Doc.concat([\n Doc.text(`<${html.tag}${space}`, Color.tag),\n showList(showAttribute, html.attributes),\n Doc.text(endTag, Color.tag),\n ]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":205,"value":"function showAttribute(attr) {\n return [\n Doc.concat([\n Doc.text(`${attr[0]}=`, Color.property),\n Doc.text(JSON.stringify(attr[1]), Color.attribute),\n ]),\n ];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"function showList(fn, l) {\n if (l.length == 0) return Doc.nil;\n const mapped = l.map(fn).reduce((x, y) => x.concat(y), []);\n \n return group(Doc.concat([\n Doc.nest(2, Doc.concat([Doc.line(''), show(mapped)])),\n Doc.line(''),\n ]));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":542,"value":"function show(l) {\n // method called \"fill\" in Wadler's paper. He describes:\n // \"[fill] collapses a list of documents into a\n // document. It puts a space between two documents when\n // this leads to reasonable layout, and a newline\n // otherwise.\n // ... Note the use of flatten to ensure that a space\n // is only inserted between documents which occupy a\n // single line.\"\n if (l.length == 0) return Doc.nil;\n if (l.length == 1) return l[0];\n return Doc.union(\n lazy(() => Doc.concat([flatten(l[0]), Doc.text(' '),\n show([flatten(l[1]), ...l.slice(2)])])),\n lazy(() => Doc.concat([l[0], Doc.line(''), show(l.slice(1))])),\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1279,"value":"md`To prettify at HTML structure, we define *prettyHtml*, which pretty-prints the concatenated list-style output of *showHTML*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":518,"value":"prettyHtml = (lineWidth, element) => pretty(lineWidth, Doc.concat(showHTML(element)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1285,"value":"md`Now, let's test the method with an example HTML structure.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"testHtml =\n // example adapted from Wadler\n HTML.element('p', {color: 'blue', font: 'Times', size: '10'}, [\n HTML.text('Here is some'),\n HTML.element('em', {}, [HTML.text('emphasized')]),\n HTML.text('text.'),\n HTML.text('Here is a'),\n HTML.element('a', {href: 'https://example.com'}, [HTML.text('link')]),\n HTML.text('elsewhere.')\n ])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1289,"value":"render(prettyHtml(80, testHtml))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1296,"value":"render(prettyHtml(10, testHtml))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1298,"value":"md`Hooray, it works! And notice how we got syntax highlighting practically for free by painting the text as we format it.\n\nNow for the fun part: JavaScript has free access to the page's HTML, which means we can write a method to convert an actual HTML element into the HTML structure we defined above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":464,"value":"function htmlFromDom(element) {\n if (element.nodeType == Node.TEXT_NODE) return HTML.text(element.textContent.trim());\n return HTML.element(\n element.tagName.toLowerCase(),\n Object.fromEntries(Array.from(element.attributes).map(a => [a.name, a.value])),\n Array.from(element.childNodes).map(htmlFromDom),\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1302,"value":"md`To get the HTML structure for the source code of this Observable notebook, we can call *htmlFromDom* on the notebook's HTML element. At the very top of this notebook, I stored the rendered markdown of the intro paragraph as a variable called \\`doc\\`. It turns out, \\`doc.parentElement.parentElement\\` points to the HTML element that contains all the nodes in this notebook.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":557,"value":"documentNodes = htmlFromDom(doc.parentElement.parentElement)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1312,"value":"md`Let's render it! Try dragging the slider to change the print width and reformat the document. You can also scroll through the formatted document to see its full contents.\n\n*(Note: because there's so much HTML in this notebook, the formatted text is super slow to display using our \n\\`render\\` method (HTML-based). Instead, I define a \\`draw\\` method you can find below which renders to canvas instead and is much more performant.)*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":248,"value":"viewof printWidth = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":507,"value":"html`Print width: ${printWidth}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":748,"value":"draw(printWidth, prettyHtml(printWidth, documentNodes))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1326,"value":"md`So, there you have it. Hopefully this guide serves as a fun way to explore an interesting algorithm and an instructive guide for anyone trying to make a formatter for their language.\n\nIf you want to learn more, I recommend reading the papers that informed this piece:\n\n* [\"A Prettier Printer\" by Philip Wadler (2003)](https://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf)\n* [\"Prettyprinting\" by Derek Oppen (1980)](https://www.cs.tufts.edu/~nr/cs257/archive/derek-oppen/prettyprinting.pdf)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":672,"value":"md`# \n\n#### *Supporting code for drawing and demoing*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1184,"value":"drawFontHeight = 12","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1186,"value":"drawLineHeight = 1.3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":759,"value":"function display(doc, width=1) {\n const nodes = pretty(width, doc);\n const pre = html`

`;\n const displayNodes = nodes.forEach(({text, color}) => {\n pre.appendChild(html`${text}`);\n });\n return pre;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":859,"value":"function displaySmallAndLargeWidth(doc) {\n const pre1 = display(doc, 1);\n const pre2 = display(doc, 30);\n return html`\n \n \n \n \n \n \n \n \n \n

Small width:	Large width:
${pre1}	${pre2}

${elem1}

${elem2}

`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1223,"value":"{\n function update() {\n const lineWidth = Math.round(Math.sin(Date.now() / 2500) * 30 + 40);\n if ((viewof demoLineWidth).value != lineWidth) {\n set(viewof demoLineWidth, lineWidth);\n }\n requestAnimationFrame(update);\n }\n requestAnimationFrame(update);\n return md`\\`update\\``;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":631,"value":"import { set, Inputs } from '@observablehq/synchronized-inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4e","stdlib":"1"}} 24:null