1(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[3834],{14:function(e,n,s){(window.__NEXT_P=window.__NEXT_P||[]).push(["/blog/bad-apple-with-regex-in-vim",function(){return s(4411)}])},4411:function(e,n,s){"use strict";s.r(n),s.d(n,{default:function(){return d},frontmatter:function(){return o},tableOfContents:function(){return l}});var a=s(5893),t=s(9843),c=s(1582);let o={title:"Bad Apple but it's 6,500 regexes that I search for in vim",short_title:"Bad Apple",subhead:"Why should I leave vim to watch a video?",date:"2025-01-10",filter_categories:["game-in-thing","toy"],assets_dir:"bad-apple-with-regex-in-vim",image:"title-image.png",description:"There's no reason I should exit vim just to watch a video",rss_description:"Look. There's simply no reason that I should have to exit vim when I want to watch Bad Apple, the shadow-art video that folks enjoy embedding in fun spots. So I got Bad Apple running inside vim just using vim's search functionality and some stupid hacks."},l=[{level:2,text:"Wait, sorry, what is Bad Apple",id:"toc:wait-sorry-what-is-bad-apple",href:"#toc:wait-sorry-what-is-bad-apple"},{level:2,text:"Getting the frames",id:"toc:getting-the-frames",href:"#toc:getting-the-frames"},{level:2,text:"Drawing in vim",id:"toc:drawing-in-vim",href:"#toc:drawing-in-vim"},{level:3,text:"Drawing arbitrary rectangles",id:"toc:drawing-arbitrary-rectangles",href:"#toc:drawing-arbitrary-rectangles"},{level:2,text:"Frames into rectangles",id:"toc:frames-into-rectangles",href:"#toc:frames-into-rectangles"},{level:3,text:"Pathological cases",id:"toc:pathological-cases",href:"#toc:pathological-cases"},{level:2,text:"Wait, so how do you actually run this inside vim",id:"toc:wait-so-how-do-you-actually-run-this-inside-vim",href:"#toc:wait-so-how-do-you-actually-run-this-inside-vim"},{level:3,text:"The macro",id:"toc:the-macro",href:"#toc:the-macro"},{level:2,text:"Wrapping up",id:"toc:wrapping-up",href:"#toc:wrapping-up"}],i=function(e){let{children:n}=e;return(0,a.jsx)(c.Z,{post:o,tableOfContents:l,children:n})};function r(e){let n={a:"a",code:"code",em:"em",h2:"h2",h3:"h3",li:"li",p:"p",pre:"pre",span:"span",ul:"ul",...(0,t.a)(),...e.components},{Expand:s,FT:c,FTD:o,SingleImage:l,SingleVideo:i}=n;return s||h("Expand",!0),c||h("FT",!0),o||h("FTD",!0),l||h("SingleImage",!0),i||h("SingleVideo",!0),(0,a.jsxs)(a.Fragment,{children:["\n",(0,a.jsx)(n.p,{children:"Well the title of this post promised you Bad Apple in vim only using search queries. So hereâs Bad Apple in vim, but the only thing thatâs changing is the search query:"}),"\n",(0,a.jsx)(i,{src:"badapple-optimized-1500-small.mp4",width:1510,height:932,alt:"The first several seconds of 'bad apple.' The video is playing inside of vim at a low resolution. On the bottom of the screen search queries scroll by as the video plays",description:"Unfortunately this is only 120x90; my screen isn't big enough to size up more"}),"\n",(0,a.jsx)(n.p,{children:"Letâs talk about how this works!"}),"\n","\n",(0,a.jsx)(n.h2,{id:"toc:wait-sorry-what-is-bad-apple",children:"Wait, sorry, what is Bad Apple"}),"\n",(0,a.jsxs)(n.p,{children:[(0,a.jsx)(n.a,{href:"https://knowyourmeme.com/memes/bad-apple",children:"Bad Apple"})," is a visually compelling music video that folks enjoy embedding in surprising places. Itâs a meme in the same way that running DOOM on a smartfridge is a meme."]}),"\n",(0,a.jsxs)(n.p,{children:["Iâve wanted to run Bad Apple somewhere since I saw ",(0,a.jsx)(n.a,{href:"https://x.com/delatoid/status/1806130369269580081",children:"this video"})," purporting to run it on One Million Checkboxes."]}),"\n",(0,a.jsx)(n.h2,{id:"toc:getting-the-frames",children:"Getting the frames"}),"\n",(0,a.jsxs)(n.p,{children:["The first step here was pretty simple. I needed data for each frame of Bad Apple. ",(0,a.jsx)(n.a,{href:"https://github.com/Felixoofed",children:"Felixoofed"})," had already done some of the work for me; I cloned ",(0,a.jsx)(n.a,{href:"https://github.com/Felixoofed/badapple-frames",children:"their repo"})," which gave me the video along with a suggestion of an ",(0,a.jsx)(n.code,{children:"ffmpeg"})," command to turn the video into ~6,500 PNGs representing each frame."]}
1),"\n",(0,a.jsx)(n.p,{children:"Then I wrote a little bit of Python code to turn each of those PNGs into a 2D array of 0s and 1s (where 1 represented a black pixel). The video was originally 480x360 - I shrunk it down to 120x90 after taking some measurements of my terminal and concluding that I couldnât really go any bigger."}),"\n",(0,a.jsx)(n.pre,{className:"language-python",children:(0,a.jsxs)(n.code,{className:"language-python code-highlight",children:[(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"from"})," PIL ",(0,a.jsx)(n.span,{className:"token keyword",children:"import"})," Image\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"import"})," numpy ",(0,a.jsx)(n.span,{className:"token keyword",children:"as"})," np\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"process_image"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"path",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," target_width",(0,a.jsx)(n.span,{className:"token operator",children:"="}),(0,a.jsx)(n.span,{className:"token number",children:"120"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," target_height",(0,a.jsx)(n.span,{className:"token operator",children:"="}),(0,a.jsx)(n.span,{className:"token number",children:"90"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" img ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," Image",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),(0,a.jsx)(n.span,{className:"token builtin",children:"open"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"path",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" img ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," img",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"resize",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"target_width",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," target_height",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," Image",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"Resampling",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"LANCZOS",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," img",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"mode ",(0,a.jsx)(n.span,{className:"token operator",children:"!="})," ",(0,a.jsx)(n.span,{className:"token string",children:'"L"'}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," img ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," img",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"convert",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token string",children:'"L"'}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" pixels ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," np",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"array",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"img",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" binary_pixels ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"pixels ",(0,a.jsx)(n.span,{className:"token operator",children:"<"})," ",(0,a.jsx)(n.span,{className:"token number",children:"10"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"astype",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token builtin",children:"int"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token comment",children:"# 1 for dark, 0 for light"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," binary_pixels\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"text_preview"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"binary_pixels",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" chars ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),(0,a.jsx)(n.span,{className:"token number",children:"0"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token string",children:'"."'}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token number",children:"1"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token string",children:'"#"'}),(0,a.jsx)(n.span,{className:"token punctuation",children:"}"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token string",children:'"\\n"'}),(0,a.jsx)(n.span,{className:"token punctuation",children:"."}
1),"join",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token string",children:'""'}),(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"join",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"chars",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),"px",(0,a.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," px ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," row ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," binary_pixels",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]})]})}),"\n",(0,a.jsxs)(n.p,{children:["I ran this against a couple of frames and printed out their ",(0,a.jsx)(n.code,{children:"text_preview"}),"s to confirm that they looked ok. They did!"]}),"\n",(0,a.jsx)(n.h2,{id:"toc:drawing-in-vim",children:"Drawing in vim"}),"\n",(0,a.jsx)(n.p,{children:"So how do we draw something in vim? Well, to start I made a grid of text with a drawing embedded inside it. Hereâs a grid that mostly has As, but if you search for B you see a little stick figure:"}),"\n",(0,a.jsx)(l,{src:"grid-blue.png",width:1370,height:920,description:"hey little guy",alt:"a vim window with a bunch of text. most of the text is the letter A, but there are some Bs. The Bs form a stick figure. The user has searched for 'B' so the Bs are highlighted blue."}),"\n",(0,a.jsx)(n.p,{children:"So that kinda lets us create a drawing! But there are some problems. One is that the blue highlighting here (which I think is the default thing vim does?) isnât super clear."}),"\n",(0,a.jsxs)(n.p,{children:["But vim highlighting is very configurable! We can tell it to highlight the foreground and background of each matched character with the same color. The invocation I use is ",(0,a.jsx)(n.code,{children:"hi Search cterm=NONE ctermfg=grey ctermbg=grey"})," which gives us nice blocks instead:"]}),"\n",(0,a.jsx)(l,{src:"grid-blocks.png",width:1370,height:920,description:"much nicer",alt:"a vim window with a bunch of text. most of the text is the letter A, but there is a stick figure that is drawn using monocolor rectangles"}),"\n",(0,a.jsxs)(n.p,{children:["But thereâs one more problem - we want square pixels! But right now each of our characters is more of a rectangle, because most fonts are taller than they are wide! I searched around and found ",(0,a.jsx)(n.a,{href:"https://strlen.com/square/",children:"Square"}),", a font that isâ¦square! Itâs designed for roguelike games played in the terminal, and using it here gives us a very nice grid:"]}),"\n",(0,a.jsx)(l,{src:"grid-square.png",width:2630,height:834,description:"all squared away",alt:"a vim window with a bunch of text. most of the text is the letter A, but there is a stick figure that is drawn using monocolor rectangles. The font is square"}),"\n",(0,a.jsxs)(n.p,{children:["So that lets us create pictures by highlighting text. But how do we highlight the ",(0,a.jsx)(n.em,{children:"right"})," text for each frame of Bad Apple?"]}),"\n",(0,a.jsx)(n.h3,{id:"toc:drawing-arbitrary-rectangles",children:"Drawing arbitrary rectangles"}),"\n",(0,a.jsx)(n.p,{children:"I kicked around a bunch of vague ideas about file structure - maybe there was a way to analyze my frames, figure out which pixels were âhot,â and then generate a file that was optimized for regexs selecting those pixels?"}),"\n",(0,a.jsxs)(n.p,{children:["But before going too far down this path I decided to read through vimâs docs on searching. I knew that vimâs search had all sorts of crazy features ",(0,a.jsx)(c,{i:1})," and I wanted to know what tools I had available. And it turns out that vim already had exactly what I needed!"]}),"\n",(0,a.jsx)(o,{i:1,children:(0,a.jsxs)(n.p,{children:["My favorites are ",(0,a.jsx)(n.code,{children:"\\zs"})," and ",(0,a.jsx)(n.code,{children:"\\ze"}),", which let you declare when a match starts or\nends. Itâs basically a way to say âtreat everything behind/ahead of me as a\nlookahead/lookbehindâ - itâs very ergonomic!"]})}),"\n",(0,a.jsx)(n.pre,{className:"language-vim",children:(0,a.jsxs)(n.code,{className:"language-vim co
1de-highlight",children:[(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token operator",children:"/"}),"\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," ",(0,a.jsx)(n.span,{className:"token operator",children:"/"}),"\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:">"}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," ",(0,a.jsx)(n.span,{className:"token operator",children:"/"}),"\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:"<"}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," E951 E1204 E1273\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),"23l Matches ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," a specific line",(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:"<"}),"23l Matches above a specific line ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"lower line ",(0,a.jsx)(n.span,{className:"token keyword",children:"number"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:">"}),"23l Matches below a specific line ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"higher line ",(0,a.jsx)(n.span,{className:"token keyword",children:"number"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:"."}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," Matches at the cursor line",(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:"<"}),(0,a.jsx)(n.span,{className:"token operator",children:"."}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," Matches above the cursor line",(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["\\",(0,a.jsx)(n.span,{className:"token operator",children:"%"}),(0,a.jsx)(n.span,{className:"token operator",children:">"}),(0,a.jsx)(n.span,{className:"token operator",children:"."}),(0,a.jsx)(n.span,{className:"token keyword",children:"l"})," Matches below the cursor line",(0,a.jsx)(n.span,{className:"token operator",children:"."}),"\n"]})]})}),"\n",(0,a.jsxs)(n.p,{children:["vim searches can match on specific line numbers (and column numbers). And you can combine several of these searches together - for example ",(0,a.jsx)(n.code,{children:"\\%>5c\\%<15c\\%>4l\\%<9l"})," matches the rectangle between columns 5 and 15 and between lines 4 and 9."]}),"\n",(0,a.jsxs)(n.p,{children:["And better yet, you can OR ",(0,a.jsx)(n.em,{children:"those"})," patterns together just like any other vim search - ",(0,a.jsx)(n.code,{children:"\\%>5c\\%<15c\\%>4l\\%<9l\\|\\%>12c\\%<25c\\%>10l\\%<15l"})," finds both our previous rectangle and the one between cols 12 and 25 and lines 10 and 15. So itâs easy to draw many rectangles to the screen with a single search."]}),"\n",(0,a.jsx)(l,{src:"square-drawing.png",width:2630,height:770,alt:"A vim window with two highlighted squares. A vim search string is visible (the squares are selected by the search string). The search string is \\%>5c\\%<15c\\%>4l\\%<9l\\|\\%>12c\\%<25c\\%>10l\\%<15l",description:"two squares from one search string!"}),"\n",(0,a.jsx)(n.p,{children:"This transformed the problem - now the goal was to decompose each frame into a series of rectangles that we could search for!"}),"\n",(0,a.jsx)(n.h2,{id:"toc:frames-into-rectangles",children:"Frames into rectangles"}),"\n",(0,a.jsx)(n.p,{children:"Our grid was 90x120 so we had ~10,000 pixels. This meant that a super naive approach would potentially look for thousands of different rectangles and generate a search string tens of thousands of characters long. Some basic testing showed me that while vimâs search was fast, search strings that long would kill my framerate."}),"\n",(0,a.jsxs)(n.p,{children:["âDecompose this grid into the minimum number of rectangles required to fill itâ seemed like the type of thing that would have a de-facto solution, so I looked for existing solutions. But I didnât find much! Thereâs ",(0,a.jsx)(n.a,{href:"https://stackoverflow.com/questions/4304750/how-can-i-reduce-a-gri
1d-of-equal-sized-squares-to-a-minimum-set-of-rectangles",children:"a 14 year old stack overflow question"})," where the accepted answer is âitâs hard.â"]}),"\n",(0,a.jsx)(n.p,{children:"So I wrote something naive. The approach I took was:"}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsx)(n.li,{children:"Detect all runs of â1sâ in the first row"}),"\n",(0,a.jsx)(n.li,{children:"Look at the next row, and find runs that overlap with the runs from the previous row"}),"\n",(0,a.jsx)(n.li,{children:"âMergeâ those runs into a rectangle if the area of the merged rectangle is greater than the area of either row alone (remember, the runs may not overlap fully)"}),"\n",(0,a.jsx)(n.li,{children:"Keep going, making sure to merge new runs into old rectangles whenever possible"}),"\n"]}),"\n",(0,a.jsx)(n.p,{children:"The actual code is pretty long and Iâm not sure itâs worth reading, but here it is if youâre curious:"}),"\n",(0,a.jsx)(s,{summary:"The code, which I'm not sure you really need to see",children:(0,a.jsx)(n.pre,{className:"language-python",children:(0,a.jsxs)(n.code,{className:"language-python code-highlight",children:[(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"class"})," ",(0,a.jsx)(n.span,{className:"token class-name",children:"Rect"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"__init__"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row_end",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," row_start\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," row_end\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," col_start\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," col_end\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"height"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end ",(0,a.jsx)(n.span,{className:"token operator",children:"-"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_start\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"width"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end ",(0,a.jsx)(n.span,{className:"token operator",children:"-"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"area"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"height",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token operator",children:"*"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"width",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"to_vim_pattern"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token comment",children:"# vim is 1-indexed and exclusive in both directions"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" row_start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}
1),"row_start\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" row_end ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end ",(0,a.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,a.jsx)(n.span,{className:"token number",children:"1"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" col_start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" col_end ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end ",(0,a.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,a.jsx)(n.span,{className:"token number",children:"1"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsxs)(n.span,{className:"token string-interpolation",children:[(0,a.jsx)(n.span,{className:"token string",children:'fr"\\%>'}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:"c\\%<"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:"c\\%>"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:"l\\%<"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"row_end",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:'l"'})]}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"__repr__"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" width ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"width",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" height ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"height",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsxs)(n.span,{className:"token string-interpolation",children:[(0,a.jsx)(n.span,{className:"token string",children:'f"R: ('}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"width",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:"x"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"height",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:") "}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}
1),"row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:":"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:", "}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:":"}),(0,a.jsxs)(n.span,{className:"token interpolation",children:[(0,a.jsx)(n.span,{className:"token punctuation",children:"{"}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:"}"})]}),(0,a.jsx)(n.span,{className:"token string",children:'"'})]}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"test_merge_horizontal"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," run_end ",(0,a.jsx)(n.span,{className:"token operator",children:"<="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token boolean",children:"False"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," run_start ",(0,a.jsx)(n.span,{className:"token operator",children:">="})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token boolean",children:"False"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" overlap_start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"max"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" overlap_end ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"min"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" overlap_rect ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"overlap_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," overlap_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}
1),"row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token operator",children:"+"}),(0,a.jsx)(n.span,{className:"token number",children:"1"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token comment",children:"# rects that are no longer eligible for merging"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" top_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," overlap_start ",(0,a.jsx)(n.span,{className:"token operator",children:">"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," overlap_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," overlap_end ",(0,a.jsx)(n.span,{className:"token operator",children:"<"})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"overlap_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"col_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," self",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"row_end",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token comment",children:"# rects that are split from the current run but eligible for merging"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token comment",children:"# with stuff below"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" bot_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," overlap_start ",(0,a.jsx)(n.span,{className:"token operator",children:">"})," run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" bot_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," overlap_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token operator",children:"+"}),(0,a.jsx)(n.span,{className:"token number",children:"1"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," overlap_end ",(0,a.jsx)(n.span,{className:"token operator",children:"<"})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" bot_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"overlap_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token operator",children:"+"}),(0,a.jsx)(n.span,{className:"token number",children:"1"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token boolean",children:"True"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," bot_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:" \n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"find_runs"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" runs ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," i",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," val ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"enumerate"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," val ",(0,a.jsx)(n.span,{className:"token operator",children:"=="})," ",(0,a.jsx)(n.span,{className:"token number",children:"1"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"and"})," start ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," i\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"elif"})," val ",(0,a.jsx)(n.span,{className:"token operator",children:"=="})," ",(0,a.jsx)(n.span,{className:"token number",children:"0"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"and"})," start ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"not"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" runs",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" start ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," start ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"not"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" runs",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"len"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," runs\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"try_merge_with_prev_row"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" candidate_merges ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," i",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," rect ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"enumerate"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" merge_result ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"test_merge_horizontal",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," merge_result",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token number",children:"0"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," candidate_merges",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"merge_result",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best_idx ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best_merge_result ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" run_length ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," run_end ",(0,a.jsx)(n.span,{className:"token operator",children:"-"})," run_start\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"candidate",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," candidate_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," candidate_merges",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" _",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," bot_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="}
1)," candidate\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" overlap_area ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"area",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," best ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"or"})," overlap_area ",(0,a.jsx)(n.span,{className:"token operator",children:">"})," best",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," overlap_area\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best_idx ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," candidate_idx\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best_merge_result ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," bot_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," best ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"elif"})," best ",(0,a.jsx)(n.span,{className:"token operator",children:">"})," run_length",(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"best_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," best_merge_result",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"else"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,a.jsx)(n.span,{className:"token function",children:"to_horizontal_merge_rect_representation"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"binary_pixels",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" completed_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" mergeable_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," row_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,a.jsx)(n.span,{className:"token builtin",children:"enumerate"}),(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"binary_pixels",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" next_mergeable_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"["}),(0,a.jsx)(n.span,{className:"token punctuation",children:"]"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" runs ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," find_runs",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"row",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," runs",(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" best_merge_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," best_merge_result ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," try_merge_with_prev_row",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"if"})," best_merge_idx ",(0,a.jsx)(n.span,{className:"token keyword",children:"is"})," ",(0,a.jsx)(n.span,{className:"token boolean",children:"None"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" r ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," Rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"run_start",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," run_end",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," row_idx",(0,a.jsx)(n.span,{className:"token operator",children:"+"}),(0,a.jsx)(n.span,{className:"token number",children:"1"}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" next_mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"r",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"else"}),(0,a.jsx)(n.span,{className:"token punctuation",children:":"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"pop",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"best_merge_idx",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:","})," bot_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," best_merge_result\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"extend",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"top_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" next_mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"append",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"overlap_rect",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" next_mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"extend",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"bot_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" completed_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"extend",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" mergeable_rects ",(0,a.jsx)(n.span,{className:"token operator",children:"="})," next_mergeable_rects\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"}),(0,a.jsxs)(n.span,{className:"code-line",children:[" completed_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"extend",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"mergeable_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:[" ",(0,a.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,a.jsx)(n.span,{className:"token string",children:'r"\\|"'}),(0,a.jsx)(n.span,{className:"token punctuation",children:"."}
1),"join",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"rect",(0,a.jsx)(n.span,{className:"token punctuation",children:"."}),"to_vim_pattern",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,a.jsx)(n.span,{className:"token keyword",children:"for"})," rect ",(0,a.jsx)(n.span,{className:"token keyword",children:"in"})," completed_rects",(0,a.jsx)(n.span,{className:"token punctuation",children:")"}),"\n"]}),(0,a.jsx)(n.span,{className:"code-line",children:"\n"})]})})}),"\n",(0,a.jsxs)(n.p,{children:["So probably donât read that. But the point is that itâs far from optimal ",(0,a.jsx)(c,{i:2}),". For example, the code never looks more than one row ahead, so it discards merges that are a bad idea ",(0,a.jsx)(n.em,{children:"now"})," but would work out well based on following rows."]}),"\n",(0,a.jsx)(o,{center:!0,i:2,children:(0,a.jsxs)(n.p,{children:["it ",(0,a.jsx)(n.em,{children:"was"})," really fun to write though"]})}),"\n",(0,a.jsxs)(n.p,{children:["But I knew the code was naive when I wrote it - I just wanted to get something vaguely reasonable down to see how itâd perform. I generated search queries for each frame and wrote them to a file. And then I set up a simple vim animation test harness ",(0,a.jsx)(c,{i:3}),", and found that the performance was fine! Well, in some cases."]}),"\n",(0,a.jsx)(o,{center:!0,i:3,children:(0,a.jsx)(n.p,{children:"weâll talk about how this works in a second"})}),"\n",(0,a.jsx)(n.h3,{id:"toc:pathological-cases",children:"Pathological cases"}),"\n",(0,a.jsxs)(n.p,{children:["My naive algorithm worked really well in some cases and totally fell over in others. Many of the search strings were 500 - 2000 characters long, but the search string that it generates for this image is over 10,000 characters ",(0,a.jsx)(c,{i:4}),"!"]}),"\n",(0,a.jsx)(o,{i:4,children:(0,a.jsxs)(n.p,{children:["Length of a search string is not a perfect proxy for performance, but I think itâs pretty good. Our search strings are just a bunch of patterns (of similar length) ORâd together. The longer a search string, the more patterns. And search time should scale with the number of patterns, since vim has to check each one before deciding that a search doesnât match. ",(0,a.jsx)("br",{}),(0,a.jsx)("br",{})," That said I did no principled profiling here and may be totally wrong in some way!"]})}),"\n",(0,a.jsx)(l,{src:"pathological.png",width:1942,height:1462,alt:"A vim window. A frame from bad apple is visible. A woman stands on a boat holding a scythe, visible from the side.",description:"cool image tbh"}),"\n",(0,a.jsx)(n.p,{children:"These long search strings dramatically reduced frames per second - we went from around ~40 FPS to the single digits."}),"\n",(0,a.jsxs)(n.p,{children:["I hunted for optimizations ",(0,a.jsx)(c,{i:5}),". I came up with a bunch of ideas for tweaks, but wasnât confident that any of them would help much with the bad cases. And I didnât have the time to find a good general-purpose algorithm: I was working on this the night before weekly presentations at the ",(0,a.jsx)(n.a,{href:"https://www.recurse.com/",children:"Recurse Center"})," and I wanted to present it the next day!"]}),"\n",(0,a.jsx)(o,{i:5,children:(0,a.jsxs)(n.p,{children:["My favorite rabbit hole was trying to improve ",(0,a.jsx)(n.em,{children:"vimâs"})," search performance instead of my regexs. My setup for playing the video had multiple buffers open and the searches were ran over each buffer. I thought if I could prevent that (or prevent ",(0,a.jsx)(n.em,{children:"highlighting"})," in other buffers) that might help. But I couldnât get that to work."]})}),"\n",(0,a.jsxs)(n.p,{children:["So I pulled out one of my favorite tricks ",(0,a.jsx)(c,{i:6})," - instead of trying to write one great algorithm, write several mediocre ones and use them all!"]}),"\n",(0,a.jsx)(o,{i:6,children:(0,a.jsxs)(n.p,{children:["which I originaly learned many years ago from my friend ",(0,a.jsx)(n.a,{href:"https://github.com/eliothedeman",children:"Eliot"}),", who is also the person who ",(0,a.jsx)(n.a,{href:"https://eieio.games/blog/scaling-one-million-checkboxes/#toc:rewrite-in-go",children:"made One Million Checkboxes faster"})]})}),"\n",(0,a.jsx)(n.p,{children:"I wrote two more naive solutions:"}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsx)(n.li,{children:"A version of my âbuild re
1cts top to bottomâ algorithm that went left to right instead"}),"\n",(0,a.jsxs)(n.li,{children:["A simple ",(0,a.jsx)(n.a,{href:"https://en.wikipedia.org/wiki/Run-length_encoding",children:"RLE"})," that only looked at individual rows"]}),"\n"]}),"\n",(0,a.jsx)(n.p,{children:"And then I updated my code to run each frame through all three algorithms and pick the shortest search pattern generated!"}),"\n",(0,a.jsxs)(n.p,{children:["This worked great. While each of these algorithms had pathological cases, they had ",(0,a.jsx)(n.em,{children:"very different"})," pathological cases. So in (almost) all cases, at least one of them generated a search pattern that was good enough."]}),"\n",(0,a.jsx)(n.p,{children:"RLE ended up most often generating the âbestâ solution - although when itâs bad itâs really bad (which is why I avoided using it to start). And my original approach was used the least often! oops."}),"\n",(0,a.jsx)(n.pre,{className:"language-bash",children:(0,a.jsxs)(n.code,{className:"language-bash code-highlight",children:[(0,a.jsxs)(n.span,{className:"code-line",children:[(0,a.jsx)(n.span,{className:"token comment",children:"# Number of times each approach was picked"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["original approach ",(0,a.jsx)(n.span,{className:"token punctuation",children:"("}),"top to bottom merging",(0,a.jsx)(n.span,{className:"token punctuation",children:")"})," - ",(0,a.jsx)(n.span,{className:"token number",children:"1110"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["left to right merging - ",(0,a.jsx)(n.span,{className:"token number",children:"2239"}),"\n"]}),(0,a.jsxs)(n.span,{className:"code-line",children:["single-row RLE - ",(0,a.jsx)(n.span,{className:"token number",children:"3300"}),"\n"]})]})}),"\n",(0,a.jsx)(n.h2,{id:"toc:wait-so-how-do-you-actually-run-this-inside-vim",children:"Wait, so how do you actually run this inside vim"}),"\n",(0,a.jsx)(n.p,{children:"Yes, right, thatâs a good question."}),"\n",(0,a.jsx)(n.p,{children:"Hereâs an image of the vim setup:"}),"\n",(0,a.jsx)(l,{src:"vimsetup.png",width:3020,height:1720,alt:"vim. There are 2 rows of windows - the first row contains a large window with an image from Bad Apple, flanked by two smaller empty buffers. The bottom row contains a single wide window with a lot of unreadable small text.",description:"it's all clear now right?"}),"\n",(0,a.jsx)(n.p,{children:"The center window on the top is where we play the video. Itâs a file that contains 90 lines of 120 spaces (remember that our images are 120x90); since weâre matching on rows and columns it doesnât need to have any content. To its left and right are some empty buffers that are sized to center the image."}),"\n",(0,a.jsx)(n.p,{children:"The bottom window is our list of search patterns! All ~6,500 of them."}),"\n",(0,a.jsxs)(n.p,{children:["To play the video we use a vim macro. If you havenât seen vim macros, theyâre a way to record a series of arbitrary keystrokes to be replayed later. Theyâre extremely powerful - since you do ~everything in vim via the keyboard, you can trivially record and replay ",(0,a.jsx)(n.em,{children:"any"})," action. And if you set up your macro right (so that it ends with the cursor in the right spot for the next iteration) you can tell vim to run the macro many times in a row!"]}),"\n",(0,a.jsx)(n.h3,{id:"toc:the-macro",children:"The macro"}),"\n",(0,a.jsxs)(n.p,{children:["The macro is ",(0,a.jsx)(n.code,{children:'"ay$:let @/=@a^M+'}),". That is:"]}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:'"a'})," Operate over register a"]}),"\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:"y$"})," Yank until the end of the line"]}),"\n"]}),"\n",(0,a.jsx)(n.p,{children:(0,a.jsx)(n.em,{children:"Vim has ânamedâ registers that can hold text - âaâ now contains the current line"})}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:":"})," Enter command mode"]}),"\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:"let @/=@a"})," set the contents of register ",(0,a.jsx)(n.code,{children:"/"})," to the contents of register ",(0,a.jsx)(n.code,{children:"a"})]}),"\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:"^M"})," execute the command (",(0,a.jsx)(n.code,{children:"^M"})," represents the enter key)"]}),"\n"]}),"\n",(0,a.jsx)(n.p,{children:(0,a.jsxs)(n.em,{children:["To reference a register in command mode you use ",(0,a.jsx)(n.code,{children:"@"})," followed by the register name. Vim has special registers - the ",(0,a.jsx)(n.code,{children:"/"})," register represents the current search. At this point vim is searching for the query that is on the current line"]})}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsxs)(n.li,{children:[(0,a.jsx)(n.code,{children:"+"})," move to the start of the next line"]}),"\n"]}),"\n",(0,a.jsx)(n.p,{children:(0,a.jsx)(n.em,{children:"This is what I meant b
1y âif you set up your macro right you can make it replayableâ - weâre prepared to execute our macro again because the cursor is now on the start of the next line!"})}),"\n",(0,a.jsxs)(n.p,{children:["This might look like nonsense to you - Iâm pretty comfortable with macros because of the years that Iâve spent ",(0,a.jsx)(n.a,{href:"https://www.vimgolf.com/",children:"vim golfing"}),". But it works!"]}),"\n",(0,a.jsxs)(n.p,{children:["The most interesting optimization is ",(0,a.jsx)(n.code,{children:"let @/=@a"})," - an alternative is to do something like ",(0,a.jsx)(n.code,{children:"/^Ra^M"})," (begin a search, pastes the output of register ",(0,a.jsx)(n.code,{children:"a"}),", enter), but this is a problem because it requires directly pasting a query that is potentially thousands of characters long. This causes the search window to expand to fit the query, which creates a flickering effect and reduces framerate."]}),"\n",(0,a.jsxs)(n.p,{children:["But now we can run ",(0,a.jsx)(n.code,{children:"1500@q"})," (assuming we recorded the macro into register ",(0,a.jsx)(n.code,{children:"q"}),") to play the macro 1500 times - meaning that weâll run through 1500 frames as quickly as we can."]}),"\n",(0,a.jsx)(n.p,{children:"And that gives us this!"}),"\n",(0,a.jsx)(i,{src:"badapple-optimized-1500-small.mp4",width:1510,height:932,alt:"The first ~30 seconds of 'bad apple.' The video is playing inside of vim at a low resolution. On the bottom of the screen search queries scroll by as the video plays",description:"not bad"}),"\n",(0,a.jsx)(n.h2,{id:"toc:wrapping-up",children:"Wrapping up"}),"\n",(0,a.jsx)(n.p,{children:"This was really fun! I built this in a single day, but if I wanted to spend more time on it I might make a few tweaks:"}),"\n",(0,a.jsxs)(n.ul,{children:["\n",(0,a.jsx)(n.li,{children:"I think itâd be more magical if I had gone the âcreate a well-structured file that I can craft traditional regexs overâ route instead of using vimâs line/col search feature. You might (reasonably) quibble that these arenât real regexs!"}),"\n",(0,a.jsxs)(n.li,{children:["I make no effort to keep a ",(0,a.jsx)(n.em,{children:"stable"})," framerate, and the framerate definitely fluctuates a bit over the course of the video."]}),"\n"]}),"\n",(0,a.jsxs)(n.p,{children:["But this was good enough for my purposes. And I think itâs neat that Iâve built most of a general-purpose solution for playing a video inside of vim using search queries. Someone suggested that I record a video of me running Bad Apple in vim and play ",(0,a.jsx)(n.em,{children:"that"})," video in vim. So I guess Iâll get on that."]}),"\n",(0,a.jsxs)(n.p,{children:["Beyond that, I made this in my first week of a new batch at ",(0,a.jsx)(n.a,{href:"https://recurse.com",children:"The Recurse Center"}),", a place that offers something like a writers retreat but for programming. I presented it to folks there and got a lovely response. I really love Recurse, and if you love nonsense like this I bet youâd like it too. Consider ",(0,a.jsx)(n.a,{href:"https://recurse.com/apply",children:"applying!"}),"."]}),"\n",(0,a.jsxs)(n.p,{children:["Finally, the code is super messy but if you want to poke around ",(0,a.jsx)(n.a,{href:"https://github.com/nolenroyalty/vim-badapple",children:"you can see it here"}),"."]}),"\n",(0,a.jsx)(n.p,{children:"And thatâs all Iâve got. As always, Iâll be back with more nonsense soon."})]})}function d(){let e=arguments.length>0&&void 0!==arguments[0]?arguments[0]:{};return(0,a.jsx)(i,{...e,children:(0,a.jsx)(r,{...e})})}function h(e,n){throw Error("Expected "+(n?"component":"object")+" `"+e+"` to be defined: you likely forgot to import, pass, or provide it.")}},1582:function(e,n,s){"use strict";s.d(n,{Z:function(){return v}});var a=s(5893),t=s(7294),c=s(1754),o=s(1686),l=s(9711),i=s(2172);let r=o.ZP.a.withConfig({componentId:"sc-d1d98fc4-0"})(["font-family:var(--regular-font);color:var(--color-white-dim);text-decoration:none;line-height:1.2;margin:0;width:fit-content;&:visited{color:var(--color-white-dim);}@media (hover:hover){&:hover{color:var(--color-white);}}"]),d=(0,o.ZP)(r).withConfig({componentId:"sc-d1d98fc4-1"})(["font-size:var(--font-size-lsmall);&:not(:first-child){margin-top:0.375rem;}"]),h=(0,o.ZP)(r).withConfig({componentId:"sc-d1d98fc4-2"})(["font-size:var(--font-size-lsmall);margin-top:0.375rem;"]),p=(0,o.ZP)(r).withConfig({componentId:"sc-d1d98fc4-3"})(["font-size:var(--font-size-small);margin-left:0.25rem;margin-top:0.125rem;"]),m=(0,o.ZP)(r).withConfig({componentId:"sc-d1d98fc4-4"})(["font-size:var(--font-size-xsmall);margin-left:0.25rem;margin-top:0.125rem;"]),u=(0,o.ZP)(r).withConfig({componentId:"sc-d1d98fc4-5"})(["font-size:var(--font-size-xsmall);margin-left:0.25rem;margin-top:0.125rem;"]),x=o.ZP.nav.withConfig({componentId:"sc-d1d98fc4-6"})(["display:flex;flex-direction:column;padding-right:64px;"]),j="toc:title";var N=t.memo(function(e){let{items:n,title:s}=e;return s&&(n=[{level:1,text:s,id:j,href:"#".concat(j)},...n]),(0,a.jsx)(x,{children:n.map(e=>{let{id:n,href:s}=e,t=null;return 1===e.level?t=d:2===e.level?t=h:3===e.level?t=p:4===e.level?t=m:5===e.level&&(t=u),(0,a.jsx)(t,{href:s,children:e.text},n)})})}),k=s(3715),g=s(9332),f=s(1916),w=s(337),y=s(1413);let b=o.ZP.nav.withConfig({componentId:"sc-67c5266d-0"})(["display:none;@media ","{display:revert;position:sticky;top:2rem;}"],c.vb.TWO_COLUMN_LAYOUT),_=o.ZP.h4.withConfig({componentId:"sc-67c5266d-1"})(["margin-top:0;font-size:var(--font-size-large);"]);var v=function(e){let{children:n,post:s,tableOfContents:c,noFooter:o=!1}=e,r=t.useRef(null),d=null!=c&&c.length>0,h=(0,g.usePathname)(),p=d?(0,a.jsxs)(b,{children:[(0,a.jsx)(_,{children:"Table of Contents"}),(0,a.jsx)(N,{items:c,title:s.short_title})]}):null,m=(0,a.jsx)(l.Dr,{contentRef:r}),u=s.image?"https://eieio.games/images/".concat(s.assets_dir,"/").concat(s.image):null;return(0,a.jsxs)(a.Fragment,{children:[(0,a.jsx)(y.Z,{title:s.title,de
1scription:s.description,image:u,type:"article",date:s.date}),(0,a.jsx)(l.pD,{children:(0,a.jsx)(l.Od,{id:1,children:(0,a.jsx)(i.CL,{path:s.assets_dir,children:(0,a.jsx)(f.Z,{additionalLeftContent:p,additionalRightContent:m,noFooter:o,children:(0,a.jsxs)(w.Ls,{ref:r,children:[(0,a.jsx)(k.Z,{titleId:j,title:s.title,subhead:s.subhead,date:s.date,href:h}),n]})})})})})]})}}},function(e){e.O(0,[959,4952,3299,2888,9774,179],function(){return e(e.s=14)}),_N_E=e.O()}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.