| blob | 9143d83a2919d5ec4ea9f09ce69958f973cc54ae |
1 # .tlv file generated by https://github.com/akkartik/teliva
2 # You may edit it if you are careful; however, you may see cryptic errors if you
3 # violate Teliva's assumptions.
4 #
5 # .tlv files are representations of Teliva programs. Teliva programs consist of
6 # sequences of definitions. Each definition is a table of key/value pairs. Keys
7 # and values are both strings.
8 #
9 # Lines in .tlv files always follow exactly one of the following forms:
10 # - comment lines at the top of the file starting with '#' at column 0
11 # - beginnings of definitions starting with '- ' at column 0, followed by a
12 # key/value pair
13 # - key/value pairs consisting of ' ' at column 0, containing either a
14 # spaceless value on the same line, or a multi-line value
15 # - multiline values indented by more than 2 spaces, starting with a '>'
16 #
17 # If these constraints are violated, Teliva may unceremoniously crash. Please
18 # report bugs at http://akkartik.name/contact
19 - __teliva_timestamp: original
20 str_helpers:
21 >-- some string helpers from http://lua-users.org/wiki/StringIndexing
22 >
23 >-- index characters using []
24 >getmetatable('').__index = function(str,i)
25 > if type(i) == 'number' then
26 > return str:sub(i,i)
27 > else
28 > return string[i]
29 > end
30 >end
31 >
32 >-- ranges using (), selected bytes using {}
33 >getmetatable('').__call = function(str,i,j)
34 > if type(i)~='table' then
35 > return str:sub(i,j)
36 > else
37 > local t={}
38 > for k,v in ipairs(i) do
39 > t[k]=str:sub(v,v)
40 > end
41 > return table.concat(t)
42 > end
43 >end
44 >
45 >-- iterate over an ordered sequence
46 >function q(x)
47 > if type(x) == 'string' then
48 > return x:gmatch('.')
49 > else
50 > return ipairs(x)
51 > end
52 >end
53 >
54 >-- insert within string
55 >function string.insert(str1, str2, pos)
56 > return str1:sub(1,pos)..str2..str1:sub(pos+1)
57 >end
58 >
59 >function string.remove(s, pos)
60 > return s:sub(1,pos-1)..s:sub(pos+1)
61 >end
62 >
63 >function string.pos(s, sub)
64 > return string.find(s, sub, 1, true) -- plain=true to disable regular expressions
65 >end
66 >
67 >-- TODO: backport utf-8 support from Lua 5.3
68 - __teliva_timestamp: original
69 debugy:
70 >debugy = 5
71 - __teliva_timestamp: original
72 dbg:
73 >-- helper for debug by print; overlay debug information towards the right
74 >-- reset debugy every time you refresh screen
75 >function dbg(window, s)
76 > local oldy = 0
77 > local oldx = 0
78 > oldy, oldx = window:getyx()
79 > window:mvaddstr(debugy, 60, s)
80 > debugy = debugy+1
81 > window:mvaddstr(oldy, oldx, '')
82 >end
83 - __teliva_timestamp: original
84 check:
85 >function check(x, msg)
86 > if x then
87 > Window:addch('.')
88 > else
89 > print('F - '..msg)
90 > print(' '..str(x)..' is false/nil')
91 > teliva_num_test_failures = teliva_num_test_failures + 1
92 > -- overlay first test failure on editors
93 > if teliva_first_failure == nil then
94 > teliva_first_failure = msg
95 > end
96 > end
97 >end
98 - __teliva_timestamp: original
99 check_eq:
100 >function check_eq(x, expected, msg)
101 > if eq(x, expected) then
102 > Window:addch('.')
103 > else
104 > print('F - '..msg)
105 > print(' expected '..str(expected)..' but got '..str(x))
106 > teliva_num_test_failures = teliva_num_test_failures + 1
107 > -- overlay first test failure on editors
108 > if teliva_first_failure == nil then
109 > teliva_first_failure = msg
110 > end
111 > end
112 >end
113 - __teliva_timestamp: original
114 eq:
115 >function eq(a, b)
116 > if type(a) ~= type(b) then return false end
117 > if type(a) == 'table' then
118 > if #a ~= #b then return false end
119 > for k, v in pairs(a) do
120 > if b[k] ~= v then
121 > return false
122 > end
123 > end
124 > for k, v in pairs(b) do
125 > if a[k] ~= v then
126 > return false
127 > end
128 > end
129 > return true
130 > end
131 > return a == b
132 >end
133 - __teliva_timestamp: original
134 str:
135 >-- smarter tostring
136 >-- slow; used only for debugging
137 >function str(x)
138 > if type(x) == 'table' then
139 > local result = ''
140 > result = result..#x..'{'
141 > for k, v in pairs(x) do
142 > result = result..str(k)..'='..str(v)..', '
143 > end
144 > result = result..'}'
145 > return result
146 > elseif type(x) == 'string' then
147 > return '"'..x..'"'
148 > end
149 > return tostring(x)
150 >end
151 - __teliva_timestamp: original
152 find_index:
153 >function find_index(arr, x)
154 > for n, y in ipairs(arr) do
155 > if x == y then
156 > return n
157 > end
158 > end
159 >end
160 - __teliva_timestamp: original
161 trim:
162 >function trim(s)
163 > return s:gsub('^%s*', ''):gsub('%s*$', '')
164 >end
165 - __teliva_timestamp: original
166 split:
167 >function split(s, d)
168 > result = {}
169 > for match in (s..d):gmatch("(.-)"..d) do
170 > table.insert(result, match);
171 > end
172 > return result
173 >end
174 - __teliva_timestamp: original
175 map:
176 >-- only for arrays
177 >function map(l, f)
178 > result = {}
179 > for _, x in ipairs(l) do
180 > table.insert(result, f(x))
181 > end
182 > return result
183 >end
184 - __teliva_timestamp: original
185 reduce:
186 >-- only for arrays
187 >function reduce(l, f, init)
188 > result = init
189 > for _, x in ipairs(l) do
190 > result = f(result, x)
191 > end
192 > return result
193 >end
194 - __teliva_timestamp: original
195 filter:
196 >function filter(h, f)
197 > result = {}
198 > for k, v in pairs(h) do
199 > if f(k, v) then
200 > result[k] = v
201 > end
202 > end
203 > return result
204 >end
205 - __teliva_timestamp: original
206 ifilter:
207 >-- only for arrays
208 >function ifilter(l, f)
209 > result = {}
210 > for _, x in ipairs(l) do
211 > if f(x) then
212 > table.insert(result, x)
213 > end
214 > end
215 > return result
216 >end
217 - __teliva_timestamp: original
218 sort_letters:
219 >function sort_letters(s)
220 > tmp = {}
221 > for i=1,#s do
222 > table.insert(tmp, s[i])
223 > end
224 > table.sort(tmp)
225 > local result = ''
226 > for _, c in pairs(tmp) do
227 > result = result..c
228 > end
229 > return result
230 >end
231 >
232 >function test_sort_letters(s)
233 > check_eq(sort_letters(''), '', 'test_sort_letters: empty')
234 > check_eq(sort_letters('ba'), 'ab', 'test_sort_letters: non-empty')
235 > check_eq(sort_letters('abba'), 'aabb', 'test_sort_letters: duplicates')
236 >end
237 - __teliva_timestamp: original
238 count_letters:
239 >-- TODO: handle unicode
240 >function count_letters(s)
241 > local result = {}
242 > for i=1,s:len() do
243 > local c = s[i]
244 > if result[c] == nil then
245 > result[c] = 1
246 > else
247 > result[c] = result[c] + 1
248 > end
249 > end
250 > return result
251 >end
252 - __teliva_timestamp: original
253 count:
254 >-- turn an array of elements into a map from elements to their frequency
255 >-- analogous to count_letters for non-strings
256 >function count(a)
257 > local result = {}
258 > for i, v in ipairs(a) do
259 > if result[v] == nil then
260 > result[v] = 1
261 > else
262 > result[v] = result[v] + 1
263 > end
264 > end
265 > return result
266 >end
267 - __teliva_timestamp: original
268 union:
269 >function union(a, b)
270 > for k, v in pairs(b) do
271 > a[k] = v
272 > end
273 > return a
274 >end
275 - __teliva_timestamp: original
276 subtract:
277 >-- set subtraction
278 >function subtract(a, b)
279 > for k, v in pairs(b) do
280 > a[k] = nil
281 > end
282 > return a
283 >end
284 - __teliva_timestamp: original
285 all:
286 >-- universal quantifier on sets
287 >function all(s, f)
288 > for k, v in pairs(s) do
289 > if not f(k, v) then
290 > return false
291 > end
292 > end
293 > return true
294 >end
295 - __teliva_timestamp: original
296 to_array:
297 >-- turn a set into an array
298 >-- drops values
299 >function to_array(h)
300 > local result = {}
301 > for k, _ in pairs(h) do
302 > table.insert(result, k)
303 > end
304 > return result
305 >end
306 - __teliva_timestamp: original
307 append:
308 >-- concatenate list 'elems' into 'l', modifying 'l' in the process
309 >function append(l, elems)
310 > for i=1,#elems do
311 > table.insert(l, elems[i])
312 > end
313 >end
314 - __teliva_timestamp: original
315 prepend:
316 >-- concatenate list 'elems' into the start of 'l', modifying 'l' in the process
317 >function prepend(l, elems)
318 > for i=1,#elems do
319 > table.insert(l, i, elems[i])
320 > end
321 >end
322 - __teliva_timestamp: original
323 all_but:
324 >function all_but(x, idx)
325 > if type(x) == 'table' then
326 > local result = {}
327 > for i, elem in ipairs(x) do
328 > if i ~= idx then
329 > table.insert(result,elem)
330 > end
331 > end
332 > return result
333 > elseif type(x) == 'string' then
334 > if idx < 1 then return x:sub(1) end
335 > return x:sub(1, idx-1) .. x:sub(idx+1)
336 > else
337 > error('all_but: unsupported type '..type(x))
338 > end
339 >end
340 >
341 >function test_all_but()
342 > check_eq(all_but('', 0), '', 'all_but: empty')
343 > check_eq(all_but('abc', 0), 'abc', 'all_but: invalid low index')
344 > check_eq(all_but('abc', 4), 'abc', 'all_but: invalid high index')
345 > check_eq(all_but('abc', 1), 'bc', 'all_but: first index')
346 > check_eq(all_but('abc', 3), 'ab', 'all_but: final index')
347 > check_eq(all_but('abc', 2), 'ac', 'all_but: middle index')
348 >end
349 - __teliva_timestamp: original
350 set:
351 >function set(l)
352 > local result = {}
353 > for i, elem in ipairs(l) do
354 > result[elem] = true
355 > end
356 > return result
357 >end
358 - __teliva_timestamp: original
359 set_eq:
360 >function set_eq(l1, l2)
361 > return eq(set(l1), set(l2))
362 >end
363 >
364 >function test_set_eq()
365 > check(set_eq({1}, {1}), 'set_eq: identical')
366 > check(not set_eq({1, 2}, {1, 3}), 'set_eq: different')
367 > check(set_eq({1, 2}, {2, 1}), 'set_eq: order')
368 > check(set_eq({1, 2, 2}, {2, 1}), 'set_eq: duplicates')
369 >end
370 - __teliva_timestamp: original
371 clear:
372 >function clear(lines)
373 > while #lines > 0 do
374 > table.remove(lines)
375 > end
376 >end
377 - __teliva_timestamp: original
378 zap:
379 >function zap(target, src)
380 > clear(target)
381 > append(target, src)
382 >end
383 - __teliva_timestamp: original
384 mfactorial:
385 >-- memoized version of factorial
386 >-- doesn't memoize recursive calls, but may be good enough
387 >mfactorial = memo1(factorial)
388 - __teliva_timestamp: original
389 factorial:
390 >function factorial(n)
391 > local result = 1
392 > for i=1,n do
393 > result = result*i
394 > end
395 > return result
396 >end
397 - __teliva_timestamp: original
398 memo1:
399 >-- a higher-order function that takes a function of a single arg
400 >-- (that never returns nil)
401 >-- and returns a memoized version of it
402 >function memo1(f)
403 > local memo = {}
404 > return function(x)
405 > if memo[x] == nil then
406 > memo[x] = f(x)
407 > end
408 > return memo[x]
409 > end
410 >end
411 >
412 >-- mfactorial doesn't seem noticeably faster
413 >function test_memo1()
414 > for i=0,30 do
415 > check_eq(mfactorial(i), factorial(i), 'memo1 over factorial: '..str(i))
416 > end
417 >end
418 - __teliva_timestamp: original
419 num_permutations:
420 >-- number of permutations of n distinct objects, taken r at a time
421 >function num_permutations(n, r)
422 > return factorial(n)/factorial(n-r)
423 >end
424 >
425 >-- mfactorial doesn't seem noticeably faster
426 >function test_memo1()
427 > for i=0,30 do
428 > for j=0,i do
429 > check_eq(num_permutations(i, j), mfactorial(i)/mfactorial(i-j), 'num_permutations memoizes: '..str(i)..'P'..str(j))
430 > end
431 > end
432 >end
433 - __teliva_timestamp: original
434 menu:
435 >-- To show app-specific hotkeys in the menu bar, add hotkey/command
436 >-- arrays of strings to the menu array.
437 >menu = {}
438 - __teliva_timestamp: original
439 Window:
440 >Window = curses.stdscr()
441 - __teliva_timestamp: original
442 window:
443 >-- constructor for fake screen and window
444 >-- call it like this:
445 >-- local w = window{
446 >-- kbd=kbd('abc'),
447 >-- scr=scr{h=5, w=4},
448 >-- }
449 >-- eventually it'll do everything a real ncurses window can
450 >function window(h)
451 > h.__index = h
452 > setmetatable(h, h)
453 > h.__index = function(table, key)
454 > return rawget(h, key)
455 > end
456 > h.attrset = function(self, x)
457 > self.scr.attrs = x
458 > end
459 > h.attron = function(self, x)
460 > -- currently same as attrset since Lua 5.1 doesn't have bitwise operators
461 > -- doesn't support multiple attrs at once
462 >-- local old = self.scr.attrs
463 >-- self.scr.attrs = old|x
464 > self.scr.attrs = x
465 > end
466 > h.attroff = function(self, x)
467 > -- currently borked since Lua 5.1 doesn't have bitwise operators
468 > -- doesn't support multiple attrs at once
469 >-- local old = self.scr.attrs
470 >-- self.scr.attrs = old & (~x)
471 > self.scr.attrs = curses.A_NORMAL
472 > end
473 > h.getch = function(self)
474 > local c = table.remove(h.kbd, 1)
475 > if c == nil then return c end
476 > return string.byte(c) -- for verisimilitude with ncurses
477 > end
478 > h.addch = function(self, c)
479 > local scr = self.scr
480 > if c == '\n' then
481 > scr.cursy = scr.cursy+1
482 > scr.cursx = 0
483 > return
484 > end
485 > if scr.cursy <= scr.h then
486 > scr[scr.cursy][scr.cursx] = {data=c, attrs=scr.attrs}
487 > scr.cursx = scr.cursx+1
488 > if scr.cursx > scr.w then
489 > scr.cursy = scr.cursy+1
490 > scr.cursx = 1
491 > end
492 > end
493 > end
494 > h.addstr = function(self, s)
495 > for i=1,s:len() do
496 > self:addch(s[i])
497 > end
498 > end
499 > h.mvaddch = function(self, y, x, c)
500 > self.scr.cursy = y
501 > self.scr.cursx = x
502 > self:addch(c)
503 > end
504 > h.mvaddstr = function(self, y, x, s)
505 > self.scr.cursy = y
506 > self.scr.cursx = x
507 > self:addstr(s)
508 > end
509 > h.clear = function(self)
510 > clear_scr(self.scr)
511 > end
512 > h.refresh = function(self)
513 > -- nothing
514 > end
515 > return h
516 >end
517 - __teliva_timestamp: original
518 kbd:
519 >function kbd(keys)
520 > local result = {}
521 > for i=1,keys:len() do
522 > table.insert(result, keys[i])
523 > end
524 > return result
525 >end
526 - __teliva_timestamp: original
527 scr:
528 >function scr(props)
529 > props.cursx = 1
530 > props.cursy = 1
531 > clear_scr(props)
532 > return props
533 >end
534 - __teliva_timestamp: original
535 clear_scr:
536 >function clear_scr(props)
537 > props.cursy = 1
538 > props.cursx = 1
539 > for y=1,props.h do
540 > props[y] = {}
541 > for x=1,props.w do
542 > props[y][x] = {data=' ', attrs=curses.A_NORMAL}
543 > end
544 > end
545 > return props
546 >end
547 - __teliva_timestamp: original
548 check_screen:
549 >function check_screen(window, contents, message)
550 > local x, y = 1, 1
551 > for i=1,contents:len() do
552 > check_eq(window.scr[y][x].data, contents[i], message..'/'..y..','..x)
553 > x = x+1
554 > if x > window.scr.w then
555 > y = y+1
556 > x = 1
557 > end
558 > end
559 >end
560 >
561 >-- putting it all together, an example test of both keyboard and screen
562 >function test_check_screen()
563 > local lines = {
564 > c='123',
565 > d='234',
566 > a='345',
567 > b='456',
568 > }
569 > local w = window{
570 > kbd=kbd('abc'),
571 > scr=scr{h=3, w=5},
572 > }
573 > local y = 1
574 > while true do
575 > local b = w:getch()
576 > if b == nil then break end
577 > w:mvaddstr(y, 1, lines[string.char(b)])
578 > y = y+1
579 > end
580 > check_screen(w, '345 '..
581 > '456 '..
582 > '123 ',
583 > 'test_check_screen')
584 >end
585 - __teliva_timestamp: original
586 check_reverse:
587 >function check_reverse(window, contents, message)
588 > local x, y = 1, 1
589 > for i=1,contents:len() do
590 > if contents[i] ~= ' ' then
591 > -- hacky version while we're without bitwise operators on Lua 5.1
592 >-- check(window.scr[y][x].attrs & curses.A_REVERSE, message..'/'..y..','..x)
593 > check_eq(window.scr[y][x].attrs, curses.A_REVERSE, message..'/'..y..','..x)
594 > else
595 > -- hacky version while we're without bitwise operators on Lua 5.1
596 >-- check(window.scr[y][x].attrs & (~curses.A_REVERSE), message..'/'..y..','..x)
597 > check(window.scr[y][x].attrs ~= curses.A_REVERSE, message..'/'..y..','..x)
598 > end
599 > x = x+1
600 > if x > window.scr.w then
601 > y = y+1
602 > x = 1
603 > end
604 > end
605 >end
606 - __teliva_timestamp: original
607 check_bold:
608 >function check_bold(window, contents, message)
609 > local x, y = 1, 1
610 > for i=1,contents:len() do
611 > if contents[i] ~= ' ' then
612 > -- hacky version while we're without bitwise operators on Lua 5.1
613 >-- check(window.scr[y][x].attrs & curses.A_BOLD, message..'/'..y..','..x)
614 > check_eq(window.scr[y][x].attrs, curses.A_BOLD, message..'/'..y..','..x)
615 > else
616 > -- hacky version while we're without bitwise operators on Lua 5.1
617 >-- check(window.scr[y][x].attrs & (~curses.A_BOLD), message..'/'..y..','..x)
618 > check(window.scr[y][x].attrs ~= curses.A_BOLD, message..'/'..y..','..x)
619 > end
620 > x = x+1
621 > if x > window.scr.w then
622 > y = y+1
623 > x = 1
624 > end
625 > end
626 >end
627 - __teliva_timestamp: original
628 check_color:
629 >-- check which parts of a screen have the given color_pair
630 >function check_color(window, cp, contents, message)
631 > local x, y = 1, 1
632 > for i=1,contents:len() do
633 > if contents[i] ~= ' ' then
634 > -- hacky version while we're without bitwise operators on Lua 5.1
635 >-- check(window.scr[y][x].attrs & curses.color_pair(cp), message..'/'..y..','..x)
636 > check_eq(window.scr[y][x].attrs, curses.color_pair(cp), message..'/'..y..','..x)
637 > else
638 > -- hacky version while we're without bitwise operators on Lua 5.1
639 >-- check(window.scr[y][x].attrs & (~curses.A_BOLD), message..'/'..y..','..x)
640 > check(window.scr[y][x].attrs ~= curses.color_pair(cp), message..'/'..y..','..x)
641 > end
642 > x = x+1
643 > if x > window.scr.w then
644 > y = y+1
645 > x = 1
646 > end
647 > end
648 >end
649 - __teliva_timestamp: original
650 sep:
651 >-- horizontal separator
652 >function sep(window)
653 > local y, _ = window:getyx()
654 > window:mvaddstr(y+1, 0, '')
655 > local _, cols = window:getmaxyx()
656 > for col=1,cols do
657 > window:addstr('_')
658 > end
659 >end
660 - __teliva_timestamp: original
661 render:
662 >function render(window)
663 > window:clear()
664 > -- draw stuff to screen here
665 > window:attron(curses.A_BOLD)
666 > window:mvaddstr(1, 5, "example app")
667 > window:attrset(curses.A_NORMAL)
668 > for i=0,15 do
669 > window:attrset(curses.color_pair(i))
670 > window:mvaddstr(3+i, 5, "========================")
671 > end
672 > window:refresh()
673 >end
674 - __teliva_timestamp: original
675 update:
676 >function update(window)
677 > local key = window:getch()
678 > -- process key here
679 >end
680 - __teliva_timestamp: original
681 doc:blurb:
682 >A REPL for queries about a graph in a .dot file.
683 - __teliva_timestamp: original
684 main:
685 >function main()
686 > if #arg == 0 then
687 > Window:clear()
688 > print('restart this app with the name of a .dot file')
689 > Window:refresh()
690 > while true do Window:getch(); end
691 > end
692 > Graph = read_dot_file(arg[1])
693 >
694 > while true do
695 > render(Window)
696 > update(Window)
697 > end
698 >end
699 - __teliva_timestamp: original
700 Graph:
701 >Graph = {}
702 - __teliva_timestamp: original
703 read_dot_file:
704 >function read_dot_file(filename)
705 > local graph = {}
706 > local infile = start_reading(nil, filename)
707 > if infile then
708 > local chars = graphviz_buffered_reader(infile)
709 > local tokens = graphviz_tokenizer(chars)
710 > parse_graph(tokens, graph)
711 > end
712 > return graph
713 >end
714 - __teliva_timestamp: original
715 graphviz_buffered_reader:
716 >-- a stream of characters that can peek up to two characters ahead at a time
717 >-- returns nil when there's nothing left to read
718 >function graphviz_buffered_reader(infile)
719 > return {
720 > infile = infile,
721 > peek = infile.read(1),
722 > peek2 = infile.read(1),
723 > read = function(self)
724 > local result = self.peek
725 > self.peek = self.peek2
726 > self.peek2 = self.infile.read(1)
727 > return result
728 > end,
729 > }
730 >end
731 - __teliva_timestamp: original
732 graphviz_tokenizer:
733 >-- a stream of tokens that can peek up to one token at a time
734 >-- returns nil when there's nothing left to read
735 >function graphviz_tokenizer(chars)
736 > return {
737 > chars = chars,
738 > peek = function(self)
739 > if not self.buffer then
740 > self.buffer = self:next_token()
741 > end
742 > return self.buffer
743 > end,
744 > read = function(self)
745 > local result
746 > if self.buffer then
747 > result = self.buffer
748 > self.buffer = nil
749 > else
750 > result = self:next_token()
751 > end
752 > return result
753 > end,
754 > next_token = function(self)
755 > self:skip_whitespace_and_comments()
756 > local c = self.chars.peek
757 > if c == nil then return nil end
758 > if string.pos('/*;,', c) then
759 > -- should be skipped as comments
760 > error('unexpected character '..c)
761 > elseif string.pos('[]{}():=', c) then
762 > -- single-char tokens
763 > return self.chars:read()
764 > elseif c == '"' then
765 > return self:string()
766 > elseif c == '<' then
767 > error('html strings are not implemented yet')
768 > elseif c == '-' then
769 > if self.chars.peek2 == '-' or self.chars.peek2 == '>' then
770 > return self:edgeop()
771 > else
772 > return self:numeral()
773 > end
774 > elseif string.pos('.0123456789', c) then
775 > return self:numeral()
776 > elseif string.match(c, '[%a_]') then
777 > return self:identifier()
778 > else
779 > error('unexpected character '..str(c))
780 > end
781 > end,
782 > skip_whitespace_and_comments = function(self)
783 > while true do
784 > local c = self.chars.peek
785 > if c == nil then
786 > break -- end of chars
787 > elseif string.match(c, '%s') then
788 > self.chars:read()
789 > elseif string.pos(',;', c) then
790 > self.chars:read()
791 > elseif c == '#' then
792 > self.chars:read() -- skip
793 > while self.chars:read() ~= '\n' do end
794 > elseif c == '/' then
795 > local c2 = self.chars.peek2
796 > if c2 == '*' then
797 > self.chars:read() -- skip '/'
798 > self.chars:read() -- skip '*'
799 > while true do
800 > if self.chars.peek == '*' and self.chars.peek2 == '/' then
801 > self.chars:read() -- skip '*'
802 > self.chars:read() -- skip '/'
803 > break
804 > end
805 > end
806 > elseif c2 == '/' then
807 > self.chars:read() -- skip '/'
808 > self.chars:read() -- skip '/'
809 > while self.chars:read() ~= '\n' do end
810 > else
811 > error('unexpected character after "/": '..c)
812 > end
813 > else
814 > break
815 > end
816 > end
817 > end,
818 > string = function(self)
819 > assert(self.chars.peek == '"')
820 > local result = self.chars:read()
821 > while true do
822 > local c = self.chars.peek
823 > if c == nil then
824 > error('unterminated string literal')
825 > end
826 > result = result..self.chars:read()
827 > if c == '\\' then
828 > result = result..self.chars:read() -- unconditionally read next char
829 > elseif c == '"' then
830 > break
831 > end
832 > end
833 > return result
834 > end,
835 > numeral = function(self)
836 > local result = ''
837 > while true do
838 > local c = self.chars.peek
839 > if c == nil then
840 > return result
841 > elseif string.pos('-.0123456789', c) then
842 > result = result..self.chars:read()
843 > else
844 > break
845 > end
846 > end
847 > if string.match(self.chars.peek, '%w') then
848 > error('invalid character after numeral '..result)
849 > end
850 > return result
851 > end,
852 > identifier = function(self)
853 > local result = ''
854 > while true do
855 > local c = self.chars.peek
856 > if c == nil then
857 > error('unterminated string literal')
858 > elseif string.match(c, '[%w_]') then
859 > result = result..self.chars:read()
860 > else
861 > break
862 > end
863 > end
864 > return result
865 > end,
866 > edgeop = function(self)
867 > return self.chars:read()..self.chars:read()
868 > end,
869 > }
870 >end
871 >
872 >function check_tokenizer(stream, expected, msg)
873 > local infile = fake_file_stream(stream)
874 > local chars = graphviz_buffered_reader(infile)
875 > local tokens = graphviz_tokenizer(chars)
876 > check_eq(tokens:read(), expected, msg)
877 >end
878 >
879 >function test_graphviz_tokenizer()
880 > check_tokenizer('123', '123', 'tokenizer: numeral')
881 > check_tokenizer(' 123', '123', 'tokenizer: skips whitespace')
882 > check_tokenizer('123 124', '123', 'tokenizer: numeral')
883 > check_tokenizer('-12.3 124', '-12.3', 'tokenizer: numeral')
884 > check_tokenizer('a123 124', 'a123', 'tokenizer: identifier')
885 > check_tokenizer('"abc def" 124', '"abc def"', 'tokenizer: string')
886 > check_tokenizer('', nil, 'tokenizer: eof')
887 >end
888 - __teliva_timestamp: original
889 parse_graph:
890 >-- https://graphviz.org/doc/info/lang.html
891 >function parse_graph(tokens, graph)
892 > local t = tokens:read()
893 > if t == 'strict' then
894 > t = tokens:read()
895 > end
896 > if t == 'graph' then
897 > error('undirected graphs not supported just yet')
898 > elseif t == 'digraph' then
899 > return parse_directed_graph(tokens, graph)
900 > else
901 > error('parse_graph: unexpected token '..t)
902 > end
903 >end
904 - __teliva_timestamp:
905 >Fri Mar 18 16:52:39 2022
906 skip_attr_list:
907 >function skip_attr_list(tokens)
908 > while true do
909 > local tok = tokens:read()
910 > if tok == nil then
911 > error('unterminated attr list; looked for "]" in vain')
912 > end
913 > if tok == ']' then break end
914 > end
915 >end
916 - __teliva_timestamp:
917 >Fri Mar 18 17:01:49 2022
918 parse_directed_graph:
919 >function parse_directed_graph(tokens, graph)
920 > tokens:read() -- skip name
921 > assert(tokens:read() == '{')
922 > while true do
923 > if tokens:peek() == nil then
924 > error('file not terminated with "}"')
925 > end
926 > if tokens:peek() == '}' then break end
927 > local tok1 = tokens:read()
928 > if tok1 == '[' then
929 > skip_attr_list(tokens)
930 > else
931 > local tok2 = tokens:read()
932 > if tok2 == '[' then
933 > -- node_stmt
934 > skip_attr_list(tokens)
935 > -- otherwise ignore node declarations;
936 > -- we'll assume the graph is fully connected
937 > -- and we can focus on just edges
938 > elseif tok2 == '->' then
939 > -- edge_stmt
940 > local tok3 = tokens:read()
941 > if graph[tok1] == nil then
942 > graph[tok1] = {}
943 > end
944 > graph[tok1][tok3] = true
945 > elseif tok2 == '--' then
946 > error('unexpected token "--" in digraph; edges should be directed using "->"')
947 > elseif tok2 == '=' then
948 > -- id '=' id
949 > -- skip
950 > tokens:read()
951 > else
952 > error('unexpected token '..tok2)
953 > end
954 > end
955 > end
956 > assert(tokens:read() == '}')
957 >end
958 - __teliva_timestamp:
959 >Fri Mar 18 17:21:16 2022
960 Focus:
961 >-- The focus is a set of nodes we're constantly running
962 >-- certain queries against.
963 >Focus = {}
964 - __teliva_timestamp:
965 >Fri Mar 18 17:21:40 2022
966 Graph:
967 >-- The set of edges parsed from the given .dot file.
968 >Graph = {}
969 - __teliva_timestamp:
970 >Fri Mar 18 17:29:25 2022
971 render_focus:
972 >function render_focus(window)
973 > window:attrset(curses.A_BOLD)
974 > window:mvaddstr(5, 1, 'focus: ')
975 > window:attrset(curses.A_NORMAL)
976 > for _, node in ipairs(Focus) do
977 > window:addstr(node)
978 > window:addstr(' ')
979 > end
980 >
981 > window:mvaddstr(8, 0, '')
982 > local lines, cols = window:getmaxyx()
983 > for col=1,cols do
984 > window:addstr('_')
985 > end
986 >end
987 - __teliva_timestamp:
988 >Fri Mar 18 17:30:11 2022
989 render_queries_on_focus:
990 >function render_queries_on_focus(window)
991 > window:attrset(curses.A_BOLD)
992 > window:mvaddstr(10, 1, '')
993 > -- TODO
994 >end
995 - __teliva_timestamp:
996 >Fri Mar 18 17:30:39 2022
997 render:
998 >function render(window)
999 > window:clear()
1000 > render_basic_stats(window)
1001 > render_focus(window)
1002 > render_queries_on_focus(window)
1003 > window:refresh()
1004 >end
1005 - __teliva_timestamp:
1006 >Fri Mar 18 17:35:20 2022
1007 sources:
1008 >function sources(Graph)
1009 > local is_target = {}
1010 > for source, targets in pairs(Graph) do
1011 > for target, _ in pairs(targets) do
1012 > is_target[target] = true
1013 > end
1014 > end
1015 > local result = {}
1016 > for source, _ in pairs(Graph) do
1017 > if not is_target[source] then
1018 > table.insert(result, source)
1019 > end
1020 > end
1021 > return result
1022 >end
1023 - __teliva_timestamp:
1024 >Fri Mar 18 17:35:57 2022
1025 render_basic_stats:
1026 >function render_basic_stats(window)
1027 > window:attrset(curses.A_BOLD)
1028 > window:mvaddstr(1, 1, 'sources: ')
1029 > window:attrset(curses.A_NORMAL)
1030 > local sources = sources(Graph)
1031 > for _, node in ipairs(sources) do
1032 > window:addstr(node)
1033 > window:addstr(' ')
1034 > end
1035 > window:mvaddstr(3, 0, '')
1036 > local lines, cols = window:getmaxyx()
1037 > for col=1,cols do
1038 > window:addstr('_')
1039 > end
1040 >end
1041 - __teliva_timestamp:
1042 >Fri Mar 18 17:51:18 2022
1043 main:
1044 >function main()
1045 > if #arg == 0 then
1046 > Window:clear()
1047 > print('restart this app with the name of a .dot file')
1048 > Window:refresh()
1049 > while true do Window:getch(); end
1050 > end
1051 > for _, filename in ipairs(arg) do
1052 > read_dot_file(filename, Graph)
1053 > end
1054 >
1055 > while true do
1056 > render(Window)
1057 > update(Window)
1058 > end
1059 >end
1060 - __teliva_timestamp:
1061 >Fri Mar 18 17:51:32 2022
1062 read_dot_file:
1063 >function read_dot_file(filename, graph)
1064 > local infile = start_reading(nil, filename)
1065 > if infile then
1066 > local chars = graphviz_buffered_reader(infile)
1067 > local tokens = graphviz_tokenizer(chars)
1068 > parse_graph(tokens, graph)
1069 > end
1070 >end
1071 - __teliva_timestamp:
1072 >Fri Mar 18 18:59:24 2022
1073 count:
1074 >function count(h)
1075 > local result = 0
1076 > for k, v in pairs(h) do
1077 > result = result+1
1078 > end
1079 > return result
1080 >end
1081 - __teliva_timestamp:
1082 >Fri Mar 18 18:59:24 2022
1083 num_nodes:
1084 >function num_nodes(Graph)
1085 > local nodes = {}
1086 > for k, v in pairs(Graph) do
1087 > nodes[k] = true
1088 > for k, v in pairs(v) do
1089 > nodes[k] = true
1090 > end
1091 > end
1092 > local result = 0
1093 > for k, v in pairs(nodes) do
1094 > result = result+1
1095 > end
1096 > return result
1097 >end
1098 - __teliva_timestamp:
1099 >Fri Mar 18 19:00:19 2022
1100 render_basic_stats:
1101 >function render_basic_stats(window)
1102 > window:attrset(curses.A_BOLD)
1103 > window:mvaddstr(1, 1, 'sources: ')
1104 > window:attrset(curses.A_NORMAL)
1105 > local sources = sources(Graph)
1106 > for _, node in ipairs(sources) do
1107 > window:addstr(node)
1108 > window:addstr(' ')
1109 > end
1110 > window:attrset(curses.A_BOLD)
1111 > window:addstr('size: ')
1112 > window:attrset(curses.A_NORMAL)
1113 > window:addstr(tostring(num_nodes(Graph)))
1114 > window:addstr(' nodes')
1115 > window:mvaddstr(3, 0, '')
1116 > local lines, cols = window:getmaxyx()
1117 > for col=1,cols do
1118 > window:addstr('_')
1119 > end
1120 >end
1121 - __teliva_timestamp:
1122 >Fri Mar 18 19:01:49 2022
1123 main:
1124 >function main()
1125 > if #arg == 0 then
1126 > Window:clear()
1127 > print('restart this app with the name of a .dot file')
1128 > Window:refresh()
1129 > while true do Window:getch(); end
1130 > end
1131 > for _, filename in ipairs(arg) do
1132 > read_dot_file(filename, Graph)
1133 > end
1134 > Focus = sources(Graph)
1135 >
1136 > while true do
1137 > render(Window)
1138 > update(Window)
1139 > end
1140 >end
1141 - __teliva_timestamp:
1142 >Fri Mar 18 19:09:56 2022
1143 reachable:
1144 >function reachable(graph, node)
1145 > local reached = {}
1146 > local todo = {node}
1147 > while #todo > 0 do
1148 > local curr = table.remove(todo)
1149 > if reached[curr] == nil then
1150 > reached[curr] = true
1151 > local targets = graph[curr]
1152 > if targets then
1153 > for target, _ in pairs(graph[curr]) do
1154 > table.insert(todo, target)
1155 > end
1156 > end
1157 > end
1158 > end
1159 > return reached
1160 >end
1161 - __teliva_timestamp:
1162 >Fri Mar 18 20:27:16 2022
1163 bold:
1164 >function bold(window, text)
1165 > window:attrset(curses.A_BOLD)
1166 > window:addstr(text)
1167 > window:attrset(curses.A_NORMAL)
1168 >end
1169 - __teliva_timestamp:
1170 >Fri Mar 18 20:30:39 2022
1171 render_queries_on_focus:
1172 >function render_queries_on_focus(window)
1173 > render_reachable_sets(window)
1174 >end
1175 - __teliva_timestamp:
1176 >Fri Mar 18 20:30:39 2022
1177 render_reachable_sets:
1178 >function render_reachable_sets(window)
1179 > local deps = {}
1180 > local needed_by = {}
1181 > for _, node in ipairs(Focus) do
1182 > deps[node] = reachable(Graph, node)
1183 > for dep, _ in pairs(deps[node]) do
1184 > if needed_by[dep] == nil then
1185 > needed_by[dep] = {}
1186 > end
1187 > append(needed_by[dep], {node})
1188 > end
1189 > end
1190 > for k, v in ipairs(needed_by) do
1191 > table.sort(v)
1192 > end
1193 > window:mvaddstr(10, 0, '')
1194 > local sets = {Focus} -- queue
1195 > local done = {}
1196 > while #sets > 0 do
1197 > local from_nodes = table.remove(sets, 1)
1198 > if #from_nodes == 0 then break end
1199 > table.sort(from_nodes)
1200 > local key = table.concat(from_nodes)
1201 > if done[key] == nil then
1202 > done[key] = true
1203 > local y, x = window:getyx()
1204 > window:mvaddstr(y+2, 0, '')
1205 > window:attrset(curses.A_BOLD)
1206 > render_list(window, from_nodes)
1207 > window:attrset(curses.A_NORMAL)
1208 > window:addstr(' -> ')
1209 > render_set(window, filter(needed_by, function(node, users) return set_eq(users, from_nodes) end))
1210 > for i, elem in ipairs(from_nodes) do
1211 > table.insert(sets, all_but(from_nodes, i))
1212 > end
1213 > end
1214 > end
1215 >end
1216 - __teliva_timestamp:
1217 >Fri Mar 18 20:32:18 2022
1218 render_list:
1219 >function render_list(window, l)
1220 > window:addstr('{')
1221 > for i, node in ipairs(l) do
1222 > if i > 1 then window:addstr(' ') end
1223 > window:addstr(node)
1224 > end
1225 > window:addstr('}')
1226 >end
1227 - __teliva_timestamp:
1228 >Fri Mar 18 20:32:18 2022
1229 render_set:
1230 >function render_set(window, h)
1231 > window:addstr('(')
1232 > window:addstr(count(h))
1233 > window:addstr(') ')
1234 > for node, _ in pairs(h) do
1235 > window:addstr(node)
1236 > window:addstr(' ')
1237 > end
1238 >end
1239 - __teliva_timestamp:
1240 >Sat Mar 19 09:19:10 2022
1241 main:
1242 >function main()
1243 > if #arg == 0 then
1244 > Window:clear()
1245 > print('restart this app with the name of a .dot file')
1246 > Window:refresh()
1247 > while true do Window:getch(); end
1248 > end
1249 > for _, filename in ipairs(arg) do
1250 > read_dot_file(filename, Graph)
1251 > end
1252 > Focus = sources(Graph)
1253 > Nodes = toposort(Graph)
1254 >
1255 > while true do
1256 > render(Window)
1257 > update(Window)
1258 > end
1259 >end
1260 - __teliva_timestamp:
1261 >Sat Mar 19 09:32:33 2022
1262 nodes:
1263 >function nodes(graph)
1264 > local result = {}
1265 > for n, deps in pairs(graph) do
1266 > result[n] = true
1267 > for n, _ in pairs(deps) do
1268 > result[n] = true
1269 > end
1270 > end
1271 > return result
1272 >end
1273 - __teliva_timestamp:
1274 >Sat Mar 19 16:27:32 2022
1275 toposort:
1276 >-- stable sort of nodes in a graph
1277 >-- nodes always occur before all their dependencies
1278 >-- disconnected nodes are in alphabetical order
1279 >function toposort(graph)
1280 > -- non-map variables are arrays
1281 > -- result = leaves in graph
1282 > -- candidates = non-leaves
1283 > local result = {}
1284 > local resultMap = {}
1285 > local candidatesMap = nodes(graph)
1286 > local leavesMap = filter(candidatesMap, function(k, v) return graph[k] == nil end)
1287 > local leaves = to_array(leavesMap)
1288 > table.sort(leaves)
1289 > union(resultMap, leavesMap)
1290 > prepend(result, leaves)
1291 > subtract(candidatesMap, leavesMap)
1292 >
1293 > function in_result(x, _) return resultMap[x] end
1294 > function all_deps_in_result(k, _) return all(graph[k], in_result) end
1295 > while true do
1296 > local oldcount = count(candidatesMap)
1297 > if oldcount == 0 then break end
1298 > local inducteesMap = filter(candidatesMap, all_deps_in_result)
1299 > local inductees = to_array(inducteesMap)
1300 > table.sort(inductees)
1301 > union(resultMap, inducteesMap)
1302 > prepend(result, inductees)
1303 > subtract(candidatesMap, inducteesMap)
1304 > if oldcount == count(candidatesMap) then
1305 > error('toposort: graph is not connected')
1306 > end
1307 > end
1308 > return result
1309 >end
1310 - __teliva_timestamp:
1311 >Sat Mar 19 16:32:24 2022
1312 render_focus:
1313 >function render_focus(window)
1314 > local y, _ = window:getyx()
1315 > window:mvaddstr(y+1, 0, '')
1316 > bold(window, 'focus: ')
1317 > for _, node in ipairs(Focus) do
1318 > window:addstr(node)
1319 > window:addstr(' ')
1320 > end
1321 > sep(window)
1322 >end
1323 - __teliva_timestamp:
1324 >Sat Mar 19 16:33:19 2022
1325 render_basic_stats:
1326 >function render_basic_stats(window)
1327 > bold(window, tostring(#Nodes)..' nodes: ')
1328 > for i, node in ipairs(Nodes) do
1329 > window:attrset(curses.A_REVERSE)
1330 > window:addstr(i)
1331 > window:attrset(curses.A_NORMAL)
1332 > window:addstr(' ')
1333 > window:addstr(node)
1334 > window:addstr(' ')
1335 > end
1336 > sep(window)
1337 >end
1338 - __teliva_timestamp:
1339 >Sat Mar 19 16:35:34 2022
1340 render_reachable_sets:
1341 >function render_reachable_sets(window)
1342 > local deps = {}
1343 > local needed_by = {}
1344 > for _, node in ipairs(Focus) do
1345 > deps[node] = reachable(Graph, node)
1346 > for dep, _ in pairs(deps[node]) do
1347 > if needed_by[dep] == nil then
1348 > needed_by[dep] = {}
1349 > end
1350 > append(needed_by[dep], {node})
1351 > end
1352 > end
1353 > for k, v in ipairs(needed_by) do
1354 > table.sort(v)
1355 > end
1356 > local sets = {Focus} -- queue
1357 > local done = {}
1358 > while #sets > 0 do
1359 > local from_nodes = table.remove(sets, 1)
1360 > if #from_nodes == 0 then break end
1361 > table.sort(from_nodes)
1362 > local key = table.concat(from_nodes)
1363 > if done[key] == nil then
1364 > done[key] = true
1365 > local y, x = window:getyx()
1366 > window:mvaddstr(y+2, 0, '')
1367 > window:attrset(curses.A_BOLD)
1368 > render_list(window, from_nodes)
1369 > window:attrset(curses.A_NORMAL)
1370 > window:addstr(' -> ')
1371 > render_set(window, filter(needed_by, function(node, users) return set_eq(users, from_nodes) end))
1372 > for i, elem in ipairs(from_nodes) do
1373 > table.insert(sets, all_but(from_nodes, i))
1374 > end
1375 > end
1376 > end
1377 >end
1378 - __teliva_timestamp:
1379 >Sat Mar 19 21:05:05 2022
1380 toposort:
1381 >-- stable sort of nodes in a graph
1382 >-- nodes always occur before all their dependencies
1383 >-- disconnected nodes are in alphabetical order
1384 >function toposort(graph)
1385 > -- non-map variables are arrays
1386 > -- result = leaves in graph
1387 > -- candidates = non-leaves
1388 > local inResultMap = {}
1389 > local candidatesMap = nodes(graph)
1390 > local leavesMap = filter(candidatesMap, function(k, v) return graph[k] == nil end)
1391 > local leaves = to_array(leavesMap)
1392 > table.sort(leaves)
1393 > union(inResultMap, leavesMap)
1394 > local result = {leaves}
1395 > subtract(candidatesMap, leavesMap)
1396 >
1397 > function in_result(x, _) return inResultMap[x] end
1398 > function all_deps_in_result(k, _) return all(graph[k], in_result) end
1399 > while true do
1400 > local oldcount = count(candidatesMap)
1401 > if oldcount == 0 then break end
1402 > local inducteesMap = filter(candidatesMap, all_deps_in_result)
1403 > local inductees = to_array(inducteesMap)
1404 > table.sort(inductees)
1405 > union(inResultMap, inducteesMap)
1406 > table.insert(result, 1, inductees)
1407 > subtract(candidatesMap, inducteesMap)
1408 > if oldcount == count(candidatesMap) then
1409 > error('toposort: graph is not connected')
1410 > end
1411 > end
1412 > return result
1413 >end
1414 - __teliva_timestamp:
1415 >Sat Mar 19 21:05:57 2022
1416 render_basic_stats:
1417 >function render_basic_stats(window)
1418 > bold(window, tostring(#Nodes)..' nodes:')
1419 > local i = 1
1420 > for _, stratum in ipairs(Nodes) do
1421 > window:addstr('\n ')
1422 > for _, node in ipairs(stratum) do
1423 > window:attrset(curses.A_REVERSE)
1424 > window:addstr(i)
1425 > window:attrset(curses.A_NORMAL)
1426 > window:addstr(' ')
1427 > window:addstr(node)
1428 > window:addstr(' ')
1429 > i = i+1
1430 > end
1431 > end
1432 > sep(window)
1433 >end