local z=require("\112\108\046\117\116\105\108\115")local e,K=pcall(require,"\112\108\046\108\117\097\098\097\108\097\110\099\101\100")if not e then K=require("\108\117\097\098\097\108\097\110\099\101\100")end local D=math.max local O=table.concat local n={list={init=" \123\125 ";accum=" \095\095\114\101\115\117\108\116\091\035\095\095\114\101\115\117\108\116\043\049\093 \061 \040\037\115\041 "};table={init=" \123\125 ";accum=" \108\111\099\097\108 \095\095\107\044 \095\095\118 \061 \037\115 \095\095\114\101\115\117\108\116\091\095\095\107\093 \061 \095\095\118 "};sum={init=" \048 ",accum=" \095\095\114\101\115\117\108\116 \061 \095\095\114\101\115\117\108\116 \043 \040\037\115\041 "},min={init=" \110\105\108 ";accum=" \108\111\099\097\108 \095\095\116\109\112 \061 \037\115  \105\102 \095\095\114\101\115\117\108\116 \116\104\101\110 \105\102 \095\095\116\109\112 \060 \095\095\114\101\115\117\108\116 \116\104\101\110 \095\095\114\101\115\117\108\116 \061 \095\095\116\109\112 \101\110\100 \101\108\115\101 \095\095\114\101\115\117\108\116 \061 \095\095\116\109\112 \101\110\100 "},max={init=" \110\105\108 ",accum=" \108\111\099\097\108 \095\095\116\109\112 \061 \037\115  \105\102 \095\095\114\101\115\117\108\116 \116\104\101\110 \105\102 \095\095\116\109\112 \062 \095\095\114\101\115\117\108\116 \116\104\101\110 \095\095\114\101\115\117\108\116 \061 \095\095\116\109\112 \101\110\100 \101\108\115\101 \095\095\114\101\115\117\108\116 \061 \095\095\116\109\112 \101\110\100 "}}local function t(z)local e=1 local n local t,b=z:match("\094\037\115\042\040\091\037\097\095\093\091\037\119\095\093\042\041\037\115\042\037\040\040\041",e)local P=#z+1 if t then local D,O=K.match_bracketed(z,b-1)assert(D,"\115\121\110\116\097\120 \101\114\114\111\114")if z:match("\094\037\115\042\036",O)then n=t P=O-1 e=b end end n=n or"\108\105\115\116"local A A,e=K.match_explist(z,e)assert(A,"\115\121\110\116\097\120 \101\114\114\111\114\058 \109\105\115\115\105\110\103 \101\120\112\114\101\115\115\105\111\110 \108\105\115\116")A=O(A,"\044 ")local c={}local f={}local a={}while 1 do local D=z:match("\094\037\115\042\102\111\114\037\115\043\040\041",e)if not D then break end e=D local O O,e=K.match_namelist(z,e)assert(#O>0,"\115\121\110\116\097\120 \101\114\114\111\114\058 \122\101\114\111 \118\097\114\105\097\098\108\101\115")for z,e in ipairs(O)do assert(not e:match("\094\095\095"),"\105\100\101\110\116\105\102\105\101\114 "..(e.." \109\097\121 \110\111\116 \099\111\110\116\097\105\110 \095\095 \112\114\101\102\105\120"))end f[#f+1]=O local n,t=z:match("\094\040\061\041\037\115\042\040\041",e)if not n then n,t=z:match("\094\040\105\110\041\037\115\043\040\041",e)end if n then e=t local D D,e=K.match_explist(z,e)assert(#D>0,"\115\121\110\116\097\120 \101\114\114\111\114\058 \122\101\114\111 \101\120\112\114\101\115\115\105\111\110\115")assert(n~="\061"or#D==2 or#D==3,"\115\121\110\116\097\120 \101\114\114\111\114\058 \110\117\109\101\114\105\099 \102\111\114 \114\101\113\117\105\114\101\115 \050 \111\114 \116\104\114\101\101 \101\120\112\114\101\115\115\105\111\110\115")c[#f]=n a[#f]=D else c[#f]=false a[#f]=false end end assert(#f>0,"\115\121\110\116\097\120 \101\114\114\111\114\058 \109\105\115\115\105\110\103 \"\102\111\114\" \099\108\097\117\115\101")local U={}while 1 do local D=z:match("\094\037\115\042\105\102\037\115\043\040\041",e)if not D then break end e=D local O O,e=K.match_expression(z,e)assert(O,"\115\121\110\116\097\120 \101\114\114\111\114\058 \112\114\101\100\105\099\097\116\101\100 \101\120\112\114\101\115\115\105\111\110 \110\111\116 \102\111\117\110\100")U[#U+1]=O end local T=""K.gsub(z,function(z,e)if z=="\101"then T=T..(" "..(e.." "))end end)local p=0 T:gsub("\091\037\097\095\093\091\037\119\095\093\042",function(z)local e=z:match("\094\095\040\037\100\043\041\036")if e then p=D(p,tonumber(e))end end)if e~=P then assert(false,"\115\121\110\116\097\120 \101\114\114\111\114\058 \117\110\114\101\099\111\103\110\105\122\101\100 "..z:sub(e))end return A,c,f,a,U,n,p end local function b(z,e,K,D,t,b,P)local A=assert(n[b])local c=A.accum:gsub("\037\037\115",z)for z=#t,1,-1 do local e=t[z]c=" \105\102 "..(e..(" \116\104\101\110 "..(c.." \101\110\100 ")))end for z=#K,1,-1 do if not e[z]then local e="\095\095\105\110"..z local D="\095\095\105\100\120"..z c=" \102\111\114 "..(D..(" \061 \049\044 \035"..(e..(" \100\111 "..(" \108\111\099\097\108 "..(K[z][1]..(" \061 "..(e..("\091"..(D..("\093 "..(c.." \101\110\100 "))))))))))))else c=" \102\111\114 "..(O(K[z],"\044 ")..(" "..(e[z]..(" "..(O(D[z],"\044 ")..(" \100\111 "..(c.." \101\110\100 ")))))))end end c=" \108\111\099\097\108 \095\095\114\101\115\117\108\116 \061 \040 "..(A.init..(" \041 "..c))return c end local function P(e,K,D,n,t)assert(K>0)local b={}for z=1,D,1 do b[#b+1]="\095"..z end for z=1,K,1 do if not n[z]then local e="\095\095\105\110"..z b[#b+1]=e end end if#b>0 then e=" \108\111\099\097\108 "..(O(b,"\044 ")..(" \061 \046\046\046 "..e))end e=e.." \114\101\116\117\114\110 \095\095\114\101\115\117\108\116 "local P,A=z.load(e,"\116\109\112","\116",t)if not P then assert(false,A..(" \119\105\116\104 \103\101\110\101\114\097\116\101\100 \099\111\100\101 "..e))end return P end local function A(z,e)local K,D,O,n,A,c,f=t(z)local a=b(K,D,O,n,A,c,f)local U=P(a,#O,f,n,e)return U end local function c(e)if not e then e=z.getfenv(2)end local K={}local D=setmetatable({},K)function K.__index(K,z)local D=A(z,e)K[z]=D return D end K.__call=K.__index D.new=c return D end local f={}f.new=c return f
--- 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
