lunarmodules / Penlight / 548

Committed 16 Jul 2024 01:53PM UTC coverage: 89.677% (+0.8%) from 88.86%

Build # 548

Build Type

push

appveyor

Committed by

web-flow

Commit Message

docs(path): fix documentation of path.exists (#483)

Run Details

5499 of 6132 relevant lines covered (89.68%)

347.94 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.8

/lua/pl/comprehension.lua

--- List comprehensions implemented in Lua.
--
-- See the [wiki page](http://lua-users.org/wiki/ListComprehensions)
--
--    local C= require 'pl.comprehension' . new()
--
--    C ('x for x=1,10') ()
--    ==> {1,2,3,4,5,6,7,8,9,10}
--    C 'x^2 for x=1,4' ()
--    ==> {1,4,9,16}
--    C '{x,x^2} for x=1,4' ()
--    ==> {{1,1},{2,4},{3,9},{4,16}}
--    C '2*x for x' {1,2,3}
--    ==> {2,4,6}
--    dbl = C '2*x for x'
--    dbl {10,20,30}
--    ==> {20,40,60}
--    C 'x for x if x % 2 == 0' {1,2,3,4,5}
--    ==> {2,4}
--    C '{x,y} for x = 1,2 for y = 1,2' ()
--    ==> {{1,1},{1,2},{2,1},{2,2}}
--    C '{x,y} for x for y' ({1,2},{10,20})
--    ==> {{1,10},{1,20},{2,10},{2,20}}
--    assert(C 'sum(x^2 for x)' {2,3,4} == 2^2+3^2+4^2)
--
-- (c) 2008 David Manura. Licensed under the same terms as Lua (MIT license).
--
-- Dependencies: `pl.utils`, `pl.luabalanced`
--
-- See @{07-functional.md.List_Comprehensions|the Guide}
-- @module pl.comprehension

local utils = require 'pl.utils'

local status,lb = pcall(require, "pl.luabalanced")
if not status then
    lb = require 'luabalanced'
end

local math_max = math.max
local table_concat = table.concat

-- fold operations
-- http://en.wikipedia.org/wiki/Fold_(higher-order_function)
local ops = {
  list = {init=' {} ', accum=' __result[#__result+1] = (%s) '},
  table = {init=' {} ', accum=' local __k, __v = %s __result[__k] = __v '},
  sum = {init=' 0 ', accum=' __result = __result + (%s) '},
  min = {init=' nil ', accum=' local __tmp = %s ' ..
                             ' if __result then if __tmp < __result then ' ..
                             '__result = __tmp end else __result = __tmp end '},
  max = {init=' nil ', accum=' local __tmp = %s ' ..
                             ' if __result then if __tmp > __result then ' ..
                             '__result = __tmp end else __result = __tmp end '},
}


-- Parses comprehension string expr.
-- Returns output expression list <out> string, array of for types
-- ('=', 'in' or nil) <fortypes>, array of input variable name
-- strings <invarlists>, array of input variable value strings
-- <invallists>, array of predicate expression strings <preds>,
-- operation name string <opname>, and number of placeholder
-- parameters <max_param>.
--
-- The is equivalent to the mathematical set-builder notation:
--
--   <opname> { <out> | <invarlist> in <invallist> , <preds> }
--
-- @usage   "x^2 for x"                 -- array values
-- @usage  "x^2 for x=1,10,2"          -- numeric for
-- @usage  "k^v for k,v in pairs(_1)"  -- iterator for
-- @usage  "(x+y)^2 for x for y if x > y"  -- nested
--
local function parse_comprehension(expr)
  local pos = 1

  -- extract opname (if exists)
  local opname
  local tok, post = expr:match('^%s*([%a_][%w_]*)%s*%(()', pos)
  local pose = #expr + 1
  if tok then
    local tok2, posb = lb.match_bracketed(expr, post-1)
    assert(tok2, 'syntax error')
    if expr:match('^%s*$', posb) then
      opname = tok
      pose = posb - 1
      pos = post
    end
  end
  opname = opname or "list"

  -- extract out expression list
  local out; out, pos = lb.match_explist(expr, pos)
  assert(out, "syntax error: missing expression list")
  out = table_concat(out, ', ')

  -- extract "for" clauses
  local fortypes = {}
  local invarlists = {}
  local invallists = {}
  while 1 do
    local post = expr:match('^%s*for%s+()', pos)
    if not post then break end
    pos = post

    -- extract input vars
    local iv; iv, pos = lb.match_namelist(expr, pos)
    assert(#iv > 0, 'syntax error: zero variables')
    for _,ident in ipairs(iv) do
      assert(not ident:match'^__',
             "identifier " .. ident .. " may not contain __ prefix")
    end
    invarlists[#invarlists+1] = iv

    -- extract '=' or 'in' (optional)
    local fortype, post = expr:match('^(=)%s*()', pos)
    if not fortype then fortype, post = expr:match('^(in)%s+()', pos) end
    if fortype then
      pos = post
      -- extract input value range
      local il; il, pos = lb.match_explist(expr, pos)
      assert(#il > 0, 'syntax error: zero expressions')
      assert(fortype ~= '=' or #il == 2 or #il == 3,
             'syntax error: numeric for requires 2 or three expressions')
      fortypes[#invarlists] = fortype
      invallists[#invarlists] = il
    else
      fortypes[#invarlists] = false
      invallists[#invarlists] = false
    end
  end
  assert(#invarlists > 0, 'syntax error: missing "for" clause')

  -- extract "if" clauses
  local preds = {}
  while 1 do
    local post = expr:match('^%s*if%s+()', pos)
    if not post then break end
    pos = post
    local pred; pred, pos = lb.match_expression(expr, pos)
    assert(pred, 'syntax error: predicated expression not found')
    preds[#preds+1] = pred
  end

  -- extract number of parameter variables (name matching "_%d+")
  local stmp = ''; lb.gsub(expr, function(u, sin)  -- strip comments/strings
    if u == 'e' then stmp = stmp .. ' ' .. sin .. ' ' end
  end)
  local max_param = 0; stmp:gsub('[%a_][%w_]*', function(s)
    local s = s:match('^_(%d+)$')
    if s then max_param = math_max(max_param, tonumber(s)) end
  end)

  if pos ~= pose then
    assert(false, "syntax error: unrecognized " .. expr:sub(pos))
  end

  --DEBUG:
  --print('----\n', string.format("%q", expr), string.format("%q", out), opname)
  --for k,v in ipairs(invarlists) do print(k,v, invallists[k]) end
  --for k,v in ipairs(preds) do print(k,v) end

  return out, fortypes, invarlists, invallists, preds, opname, max_param
end


-- Create Lua code string representing comprehension.
-- Arguments are in the form returned by parse_comprehension.
local function code_comprehension(
    out, fortypes, invarlists, invallists, preds, opname, max_param
)
  local op = assert(ops[opname])
  local code = op.accum:gsub('%%s',  out)

  for i=#preds,1,-1 do local pred = preds[i]
    code = ' if ' .. pred .. ' then ' .. code .. ' end '
  end
  for i=#invarlists,1,-1 do
    if not fortypes[i] then
      local arrayname = '__in' .. i
      local idx = '__idx' .. i
      code =
        ' for ' .. idx .. ' = 1, #' .. arrayname .. ' do ' ..
        ' local ' .. invarlists[i][1] .. ' = ' .. arrayname .. '['..idx..'] ' ..
        code .. ' end '
    else
      code =
        ' for ' ..
        table_concat(invarlists[i], ', ') ..
        ' ' .. fortypes[i] .. ' ' ..
        table_concat(invallists[i], ', ') ..
        ' do ' .. code .. ' end '
    end
  end
  code = ' local __result = ( ' .. op.init .. ' ) ' .. code
  return code
end


-- Convert code string represented by code_comprehension
-- into Lua function.  Also must pass ninputs = #invarlists,
-- max_param, and invallists (from parse_comprehension).
-- Uses environment env.
local function wrap_comprehension(code, ninputs, max_param, invallists, env)
  assert(ninputs > 0)
  local ts = {}
  for i=1,max_param do
    ts[#ts+1] = '_' .. i
  end
  for i=1,ninputs do
    if not invallists[i] then
      local name = '__in' .. i
      ts[#ts+1] = name
    end
  end
  if #ts > 0 then
    code = ' local ' .. table_concat(ts, ', ') .. ' = ... ' .. code
  end
  code = code .. ' return __result '
  --print('DEBUG:', code)
  local f, err = utils.load(code,'tmp','t',env)
  if not f then assert(false, err .. ' with generated code ' .. code) end
  return f
end


-- Build Lua function from comprehension string.
-- Uses environment env.
local function build_comprehension(expr, env)
  local out, fortypes, invarlists, invallists, preds, opname, max_param
    = parse_comprehension(expr)
  local code = code_comprehension(
    out, fortypes, invarlists, invallists, preds, opname, max_param)
  local f = wrap_comprehension(code, #invarlists, max_param, invallists, env)
  return f
end


-- Creates new comprehension cache.
-- Any list comprehension function created are set to the environment
-- env (defaults to caller of new).
local function new(env)
  -- Note: using a single global comprehension cache would have had
  -- security implications (e.g. retrieving cached functions created
  -- in other environments).
  -- The cache lookup function could have instead been written to retrieve
  -- the caller's environment, lookup up the cache private to that
  -- environment, and then looked up the function in that cache.
  -- That would avoid the need for this <new> call to
  -- explicitly manage caches; however, that might also have an undue
  -- performance penalty.

  if not env then
    env = utils.getfenv(2)
  end

  local mt = {}
  local cache = setmetatable({}, mt)

  -- Index operator builds, caches, and returns Lua function
  -- corresponding to comprehension expression string.
  --
  -- Example: f = comprehension['x^2 for x']
  --
  function mt:__index(expr)
    local f = build_comprehension(expr, env)
    self[expr] = f  -- cache
    return f
  end

  -- Convenience syntax.
  -- Allows comprehension 'x^2 for x' instead of comprehension['x^2 for x'].
  mt.__call = mt.__index

  cache.new = new

  return cache
end


local comprehension = {}
comprehension.new = new

return comprehension

1	--- List comprehensions implemented in Lua.
2	--
3	-- See the [wiki page](http://lua-users.org/wiki/ListComprehensions)
4	--
5	-- local C= require 'pl.comprehension' . new()
6	--
7	-- C ('x for x=1,10') ()
8	-- ==> {1,2,3,4,5,6,7,8,9,10}
9	-- C 'x^2 for x=1,4' ()
10	-- ==> {1,4,9,16}
11	-- C '{x,x^2} for x=1,4' ()
12	-- ==> {{1,1},{2,4},{3,9},{4,16}}
13	-- C '2*x for x' {1,2,3}
14	-- ==> {2,4,6}
15	-- dbl = C '2*x for x'
16	-- dbl {10,20,30}
17	-- ==> {20,40,60}
18	-- C 'x for x if x % 2 == 0' {1,2,3,4,5}
19	-- ==> {2,4}
20	-- C '{x,y} for x = 1,2 for y = 1,2' ()
21	-- ==> {{1,1},{1,2},{2,1},{2,2}}
22	-- C '{x,y} for x for y' ({1,2},{10,20})
23	-- ==> {{1,10},{1,20},{2,10},{2,20}}
24	-- assert(C 'sum(x^2 for x)' {2,3,4} == 2^2+3^2+4^2)
25	--
26	-- (c) 2008 David Manura. Licensed under the same terms as Lua (MIT license).
27	--
28	-- Dependencies: `pl.utils`, `pl.luabalanced`
29	--
30	-- See @{07-functional.md.List_Comprehensions\|the Guide}
31	-- @module pl.comprehension
32
33	local utils = require 'pl.utils'	8✔
34
35	local status,lb = pcall(require, "pl.luabalanced")	8✔
36	if not status then	8✔
37	lb = require 'luabalanced'	×
38	end
39
40	local math_max = math.max	8✔
41	local table_concat = table.concat	8✔
42
43	-- fold operations
44	-- http://en.wikipedia.org/wiki/Fold_(higher-order_function)
45	local ops = {	8✔
46	list = {init=' {} ', accum=' __result[#__result+1] = (%s) '},	8✔
47	table = {init=' {} ', accum=' local __k, __v = %s __result[__k] = __v '},	8✔
48	sum = {init=' 0 ', accum=' __result = __result + (%s) '},	8✔
49	min = {init=' nil ', accum=' local __tmp = %s ' ..	8✔
50	' if __result then if __tmp < __result then ' ..	11✔
51	'__result = __tmp end else __result = __tmp end '},	11✔
52	max = {init=' nil ', accum=' local __tmp = %s ' ..	8✔
53	' if __result then if __tmp > __result then ' ..	11✔
54	'__result = __tmp end else __result = __tmp end '},	11✔
55	}
56
57
58	-- Parses comprehension string expr.
59	-- Returns output expression list <out> string, array of for types
60	-- ('=', 'in' or nil) <fortypes>, array of input variable name
61	-- strings <invarlists>, array of input variable value strings
62	-- <invallists>, array of predicate expression strings <preds>,
63	-- operation name string <opname>, and number of placeholder
64	-- parameters <max_param>.
65	--
66	-- The is equivalent to the mathematical set-builder notation:
67	--
68	-- <opname> { <out> \| <invarlist> in <invallist> , <preds> }
69	--
70	-- @usage "x^2 for x" -- array values
71	-- @usage "x^2 for x=1,10,2" -- numeric for
72	-- @usage "k^v for k,v in pairs(_1)" -- iterator for
73	-- @usage "(x+y)^2 for x for y if x > y" -- nested
74	--
75	local function parse_comprehension(expr)
76	local pos = 1	232✔
77
78	-- extract opname (if exists)
79	local opname
80	local tok, post = expr:match('^%s([%a_][%w_])%s*%(()', pos)	232✔
81	local pose = #expr + 1	232✔
82	if tok then	232✔
83	local tok2, posb = lb.match_bracketed(expr, post-1)	160✔
84	assert(tok2, 'syntax error')	160✔
85	if expr:match('^%s*$', posb) then	160✔
86	opname = tok	160✔
87	pose = posb - 1	160✔
88	pos = post	160✔
89	end
90	end
91	opname = opname or "list"	232✔
92
93	-- extract out expression list
94	local out; out, pos = lb.match_explist(expr, pos)	348✔
95	assert(out, "syntax error: missing expression list")	232✔
96	out = table_concat(out, ', ')	232✔
97
98	-- extract "for" clauses
99	local fortypes = {}	232✔
100	local invarlists = {}	232✔
101	local invallists = {}	232✔
102	while 1 do	260✔
103	local post = expr:match('^%s*for%s+()', pos)	520✔
104	if not post then break end	520✔
105	pos = post	296✔
106
107	-- extract input vars
108	local iv; iv, pos = lb.match_namelist(expr, pos)	444✔
109	assert(#iv > 0, 'syntax error: zero variables')	296✔
110	for _,ident in ipairs(iv) do	608✔
111	assert(not ident:match'^__',	640✔
112	"identifier " .. ident .. " may not contain __ prefix")	320✔
113	end
114	invarlists[#invarlists+1] = iv	288✔
115
116	-- extract '=' or 'in' (optional)
117	local fortype, post = expr:match('^(=)%s*()', pos)	288✔
118	if not fortype then fortype, post = expr:match('^(in)%s+()', pos) end	288✔
119	if fortype then	288✔
120	pos = post	72✔
121	-- extract input value range
122	local il; il, pos = lb.match_explist(expr, pos)	108✔
123	assert(#il > 0, 'syntax error: zero expressions')	72✔
124	assert(fortype ~= '=' or #il == 2 or #il == 3,	144✔
125	'syntax error: numeric for requires 2 or three expressions')	72✔
126	fortypes[#invarlists] = fortype	72✔
127	invallists[#invarlists] = il	72✔
128	else
129	fortypes[#invarlists] = false	216✔
130	invallists[#invarlists] = false	216✔
131	end
132	end
133	assert(#invarlists > 0, 'syntax error: missing "for" clause')	224✔
134
135	-- extract "if" clauses
136	local preds = {}	224✔
137	while 1 do	140✔
138	local post = expr:match('^%s*if%s+()', pos)	280✔
139	if not post then break end	280✔
140	pos = post	56✔
141	local pred; pred, pos = lb.match_expression(expr, pos)	84✔
142	assert(pred, 'syntax error: predicated expression not found')	56✔
143	preds[#preds+1] = pred	56✔
144	end
145
146	-- extract number of parameter variables (name matching "_%d+")
147	local stmp = ''; lb.gsub(expr, function(u, sin) -- strip comments/strings	448✔
148	if u == 'e' then stmp = stmp .. ' ' .. sin .. ' ' end	280✔
149	end)
150	local max_param = 0; stmp:gsub('[%a_][%w_]*', function(s)	448✔
151	local s = s:match('^_(%d+)$')	1,368✔
152	if s then max_param = math_max(max_param, tonumber(s)) end	1,368✔
153	end)
154
155	if pos ~= pose then	224✔
156	assert(false, "syntax error: unrecognized " .. expr:sub(pos))	×
157	end
158
159	--DEBUG:
160	--print('----\n', string.format("%q", expr), string.format("%q", out), opname)
161	--for k,v in ipairs(invarlists) do print(k,v, invallists[k]) end
162	--for k,v in ipairs(preds) do print(k,v) end
163
164	return out, fortypes, invarlists, invallists, preds, opname, max_param	224✔
165	end
166
167
168	-- Create Lua code string representing comprehension.
169	-- Arguments are in the form returned by parse_comprehension.
170	local function code_comprehension(
171	out, fortypes, invarlists, invallists, preds, opname, max_param
172	)
173	local op = assert(ops[opname])	224✔
174	local code = op.accum:gsub('%%s', out)	224✔
175
176	for i=#preds,1,-1 do local pred = preds[i]	311✔
177	code = ' if ' .. pred .. ' then ' .. code .. ' end '	56✔
178	end
179	for i=#invarlists,1,-1 do	512✔
180	if not fortypes[i] then	288✔
181	local arrayname = '__in' .. i	216✔
182	local idx = '__idx' .. i	216✔
183	code =	×
184	' for ' .. idx .. ' = 1, #' .. arrayname .. ' do ' ..	216✔
185	' local ' .. invarlists[i][1] .. ' = ' .. arrayname .. '['..idx..'] ' ..	216✔
186	code .. ' end '	216✔
187	else
188	code =	×
189	' for ' ..	72✔
190	table_concat(invarlists[i], ', ') ..	72✔
191	' ' .. fortypes[i] .. ' ' ..	72✔
192	table_concat(invallists[i], ', ') ..	72✔
193	' do ' .. code .. ' end '	72✔
194	end
195	end
196	code = ' local __result = ( ' .. op.init .. ' ) ' .. code	224✔
197	return code	224✔
198	end
199
200
201	-- Convert code string represented by code_comprehension
202	-- into Lua function. Also must pass ninputs = #invarlists,
203	-- max_param, and invallists (from parse_comprehension).
204	-- Uses environment env.
205	local function wrap_comprehension(code, ninputs, max_param, invallists, env)
206	assert(ninputs > 0)	224✔
207	local ts = {}	224✔
208	for i=1,max_param do	304✔
209	ts[#ts+1] = '_' .. i	80✔
210	end
211	for i=1,ninputs do	512✔
212	if not invallists[i] then	288✔
213	local name = '__in' .. i	216✔
214	ts[#ts+1] = name	216✔
215	end
216	end
217	if #ts > 0 then	224✔
218	code = ' local ' .. table_concat(ts, ', ') .. ' = ... ' .. code	208✔
219	end
220	code = code .. ' return __result '	224✔
221	--print('DEBUG:', code)
222	local f, err = utils.load(code,'tmp','t',env)	224✔
223	if not f then assert(false, err .. ' with generated code ' .. code) end	224✔
224	return f	224✔
225	end
226
227
228	-- Build Lua function from comprehension string.
229	-- Uses environment env.
230	local function build_comprehension(expr, env)
231	local out, fortypes, invarlists, invallists, preds, opname, max_param
232	= parse_comprehension(expr)	232✔
233	local code = code_comprehension(	448✔
234	out, fortypes, invarlists, invallists, preds, opname, max_param)	224✔
235	local f = wrap_comprehension(code, #invarlists, max_param, invallists, env)	224✔
236	return f	224✔
237	end
238
239
240	-- Creates new comprehension cache.
241	-- Any list comprehension function created are set to the environment
242	-- env (defaults to caller of new).
243	local function new(env)
244	-- Note: using a single global comprehension cache would have had
245	-- security implications (e.g. retrieving cached functions created
246	-- in other environments).
247	-- The cache lookup function could have instead been written to retrieve
248	-- the caller's environment, lookup up the cache private to that
249	-- environment, and then looked up the function in that cache.
250	-- That would avoid the need for this <new> call to
251	-- explicitly manage caches; however, that might also have an undue
252	-- performance penalty.
253
254	if not env then	16✔
255	env = utils.getfenv(2)	8✔
256	end
257
258	local mt = {}	16✔
259	local cache = setmetatable({}, mt)	16✔
260
261	-- Index operator builds, caches, and returns Lua function
262	-- corresponding to comprehension expression string.
263	--
264	-- Example: f = comprehension['x^2 for x']
265	--
266	function mt:__index(expr)	16✔
267	local f = build_comprehension(expr, env)	232✔
268	self[expr] = f -- cache	224✔
269	return f	224✔
270	end
271
272	-- Convenience syntax.
273	-- Allows comprehension 'x^2 for x' instead of comprehension['x^2 for x'].
274	mt.__call = mt.__index	16✔
275
276	cache.new = new	16✔
277
278	return cache	16✔
279	end
280
281
282	local comprehension = {}	8✔
283	comprehension.new = new	8✔
284
285	return comprehension	8✔

lunarmodules / Penlight / 548

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous