src/lib/metalua/table2.lua

   1 ---------------------------------------------------------------------
   2 ----------------------------------------------------------------------
   3 --
   4 -- Table module extension
   5 --
   6 ----------------------------------------------------------------------
   7 ----------------------------------------------------------------------
   8
   9 -- todo: table.scan (scan1?) fold1? flip?
  10
  11 function table.transpose(t)
  12    local tt = { }
  13    for a, b in pairs(t) do tt[b] = a end
  14    return tt
  15 end
  16
  17 function table.iforeach(f, ...)
  18    -- assert (type (f) == "function") [wouldn't allow metamethod __call]
  19    local nargs = select("#", ...)
  20    if nargs==1 then -- Quick iforeach (most common case), just one table arg
  21       local t = ...
  22       assert (type (t) == "table")
  23       for i = 1, #t do
  24          local result = f (t[i])
  25          -- If the function returns non-false, stop iteration
  26          if result then return result end
  27       end
  28    else -- advanced case: boundaries and/or multiple tables
  29
  30       -- fargs:       arguments fot a single call to f
  31       -- first, last: indexes of the first & last elements mapped in each table
  32       -- arg1:        index of the first table in args
  33
  34       -- 1 - find boundaries if any
  35       local  args, fargs, first, last, arg1 = {...}, { }
  36       if     type(args[1]) ~= "number" then first, arg1 = 1, 1 -- no boundary
  37       elseif type(args[2]) ~= "number" then first, last, arg1 = 1, args[1], 2
  38       else   first,  last, arg1 = args[1], args[2], 3 end
  39       assert (nargs >= arg1) -- at least one table
  40       -- 2 - determine upper boundary if not given
  41       if not last then for i = arg1, nargs do
  42             assert (type (args[i]) == "table")
  43             last = max (#args[i], last)
  44       end end
  45       -- 3 - remove non-table arguments from args, adjust nargs
  46       if arg1>1 then args = { select(arg1, unpack(args)) }; nargs = #args end
  47
  48       -- 4 - perform the iteration
  49       for i = first, last do
  50          for j = 1, nargs do fargs[j] = args[j][i] end -- build args list
  51          local result = f (unpack (fargs)) -- here is the call
  52          -- If the function returns non-false, stop iteration
  53          if result then return result end
  54       end
  55    end
  56 end
  57
  58 function table.imap (f, ...)
  59    local result, idx = { }, 1
  60    local function g(...) result[idx] = f(...);  idx=idx+1 end
  61    table.iforeach(g, ...)
  62    return result
  63 end
  64
  65 function table.ifold (f, acc, ...)
  66    local function g(...) acc = f (acc,...) end
  67    table.iforeach (g, ...)
  68    return acc
  69 end
  70
  71 -- function table.ifold1 (f, ...)
  72 --    return table.ifold (f, acc, 2, false, ...)
  73 -- end
  74
  75 function table.izip(...)
  76    local function g(...) return {...} end
  77    return table.imap(g, ...)
  78 end
  79
  80 function table.ifilter(f, t)
  81    local yes, no = { }, { }
  82    for i=1,#t do table.insert (f(t[i]) and yes or no, t[i]) end
  83    return yes, no
  84 end
  85
  86 function table.icat(...)
  87    local result = { }
  88    for t in values {...} do
  89       for x in values (t) do
  90          table.insert (result, x)
  91       end
  92    end
  93    return result
  94 end
  95
  96 function table.iflatten (x) return table.icat (unpack (x)) end
  97
  98 function table.irev (t)
  99    local result, nt = { }, #t
 100    for i=0, nt-1 do result[nt-i] = t[i+1] end
 101    return result
 102 end
 103
 104 function table.isub (t, ...)
 105    local ti, u = table.insert, { }
 106    local args, nargs = {...}, select("#", ...)
 107    for i=1, nargs/2 do
 108       local a, b = args[2*i-1], args[2*i]
 109       for i=a, b, a<=b and 1 or -1 do ti(u, t[i]) end
 110    end
 111    return u
 112 end
 113
 114 function table.iall (f, ...)
 115    local result = true
 116    local function g(...) return not f(...) end
 117    return not table.iforeach(g, ...)
 118    --return result
 119 end
 120
 121 function table.iany (f, ...)
 122    local function g(...) return not f(...) end
 123    return not table.iall(g, ...)
 124 end
 125
 126 function table.shallow_copy(x)
 127    local y={ }
 128    for k, v in pairs(x) do y[k]=v end
 129    return y
 130 end
 131
 132 -- Warning, this is implementation dependent: it relies on
 133 -- the fact the [next()] enumerates the array-part before the hash-part.
 134 function table.cat(...)
 135    local y={ }
 136    for x in values{...} do
 137       -- cat array-part
 138       for _, v in ipairs(x) do table.insert(y,v) end
 139       -- cat hash-part
 140       local lx, k = #x
 141       if lx>0 then k=next(x,lx) else k=next(x) end
 142       while k do y[k]=x[k]; k=next(x,k) end
 143    end
 144    return y
 145 end
 146
 147 function table.deep_copy(x)
 148    local tracker = { }
 149    local function aux (x)
 150       if type(x) == "table" then
 151          local y=tracker[x]
 152          if y then return y end
 153          y = { }; tracker[x] = y
 154          setmetatable (y, getmetatable (x))
 155          for k,v in pairs(x) do y[aux(k)] = aux(v) end
 156          return y
 157       else return x end
 158    end
 159    return aux(x)
 160 end
 161
 162 function table.override(dst, src)
 163    for k, v in pairs(src) do dst[k] = v end
 164    for i = #src+1, #dst   do dst[i] = nil end
 165    return dst
 166 end
 167
 168
 169 function table.range(a,b,c)
 170    if not b then assert(not(c)); b=a; a=1
 171    elseif not c then c = (b>=a) and 1 or -1 end
 172    local result = { }
 173    for i=a, b, c do table.insert(result, i) end
 174    return result
 175 end
 176
 177 -- FIXME: new_indent seems to be always nil?!
 178 -- FIXME: accumulator function should be configurable,
 179 -- so that print() doesn't need to bufferize the whole string
 180 -- before starting to print.
 181 function table.tostring(t, ...)
 182    local PRINT_HASH, HANDLE_TAG, FIX_INDENT, LINE_MAX, INITIAL_INDENT = true, true
 183    for _, x in ipairs {...} do
 184       if type(x) == "number" then
 185          if not LINE_MAX then LINE_MAX = x
 186          else INITIAL_INDENT = x end
 187       elseif x=="nohash" then PRINT_HASH = false
 188       elseif x=="notag"  then HANDLE_TAG = false
 189       else
 190          local n = string['match'](x, "^indent%s*(%d*)$")
 191          if n then FIX_INDENT = tonumber(n) or 3 end
 192       end
 193    end
 194    LINE_MAX       = LINE_MAX or math.huge
 195    INITIAL_INDENT = INITIAL_INDENT or 1
 196
 197    local current_offset =  0  -- indentation level
 198    local xlen_cache     = { } -- cached results for xlen()
 199    local acc_list       = { } -- Generated bits of string
 200    local function acc(...)    -- Accumulate a bit of string
 201       local x = table.concat{...}
 202       current_offset = current_offset + #x
 203       table.insert(acc_list, x)
 204    end
 205    local function valid_id(x)
 206       -- FIXME: we should also reject keywords; but the list of
 207       -- current keywords is not fixed in metalua...
 208       return type(x) == "string"
 209          and string['match'](x, "^[a-zA-Z_][a-zA-Z0-9_]*$")
 210    end
 211
 212    -- Compute the number of chars it would require to display the table
 213    -- on a single line. Helps to decide whether some carriage returns are
 214    -- required. Since the size of each sub-table is required many times,
 215    -- it's cached in [xlen_cache].
 216    local xlen_type = { }
 217    local function xlen(x, nested)
 218       nested = nested or { }
 219       if x==nil then return #"nil" end
 220       --if nested[x] then return #tostring(x) end -- already done in table
 221       local len = xlen_cache[x]
 222       if len then return len end
 223       local f = xlen_type[type(x)]
 224       if not f then return #tostring(x) end
 225       len = f (x, nested)
 226       xlen_cache[x] = len
 227       return len
 228    end
 229
 230    -- optim: no need to compute lengths if I'm not going to use them
 231    -- anyway.
 232    if LINE_MAX == math.huge then xlen = function() return 0 end end
 233
 234    xlen_type["nil"] = function () return 3 end
 235    function xlen_type.number  (x) return #tostring(x) end
 236    function xlen_type.boolean (x) return x and 4 or 5 end
 237    function xlen_type.string  (x) return #string.format("%q",x) end
 238    function xlen_type.table   (adt, nested)
 239
 240       -- Circular references detection
 241       if nested [adt] then return #tostring(adt) end
 242       nested [adt] = true
 243
 244       local has_tag  = HANDLE_TAG and valid_id(adt.tag)
 245       local alen     = #adt
 246       local has_arr  = alen>0
 247       local has_hash = false
 248       local x = 0
 249
 250       if PRINT_HASH then
 251          -- first pass: count hash-part
 252          for k, v in pairs(adt) do
 253             if k=="tag" and has_tag then
 254                -- this is the tag -> do nothing!
 255             elseif type(k)=="number" and k<=alen and math.fmod(k,1)==0 then
 256                -- array-part pair -> do nothing!
 257             else
 258                has_hash = true
 259                if valid_id(k) then x=x+#k
 260                else x = x + xlen (k, nested) + 2 end -- count surrounding brackets
 261                x = x + xlen (v, nested) + 5          -- count " = " and ", "
 262             end
 263          end
 264       end
 265
 266       for i = 1, alen do x = x + xlen (adt[i], nested) + 2 end -- count ", "
 267
 268       nested[adt] = false -- No more nested calls
 269
 270       if not (has_tag or has_arr or has_hash) then return 3 end
 271       if has_tag then x=x+#adt.tag+1 end
 272       if not (has_arr or has_hash) then return x end
 273       if not has_hash and alen==1 and type(adt[1])~="table" then
 274          return x-2 -- substract extraneous ", "
 275       end
 276       return x+2 -- count "{ " and " }", substract extraneous ", "
 277    end
 278
 279    -- Recursively print a (sub) table at given indentation level.
 280    -- [newline] indicates whether newlines should be inserted.
 281    local function rec (adt, nested, indent)
 282       if not FIX_INDENT then indent = current_offset end
 283       local function acc_newline()
 284          acc ("\n"); acc (string.rep (" ", indent))
 285          current_offset = indent
 286       end
 287       local x = { }
 288       x["nil"] = function() acc "nil" end
 289       function x.number()   acc (tostring (adt)) end
 290       --function x.string()   acc (string.format ("%q", adt)) end
 291       function x.string()   acc ((string.format ("%q", adt):gsub("\\\n", "\\n"))) end
 292       function x.boolean()  acc (adt and "true" or "false") end
 293       function x.table()
 294          if nested[adt] then acc(tostring(adt)); return end
 295          nested[adt]  = true
 296
 297
 298          local has_tag  = HANDLE_TAG and valid_id(adt.tag)
 299          local alen     = #adt
 300          local has_arr  = alen>0
 301          local has_hash = false
 302
 303          if has_tag then acc("`"); acc(adt.tag) end
 304
 305          -- First pass: handle hash-part
 306          if PRINT_HASH then
 307             for k, v in pairs(adt) do
 308                -- pass if the key belongs to the array-part or is the "tag" field
 309                if not (k=="tag" and HANDLE_TAG) and
 310                   not (type(k)=="number" and k<=alen and math.fmod(k,1)==0) then
 311
 312                   -- Is it the first time we parse a hash pair?
 313                   if not has_hash then
 314                      acc "{ "
 315                      if not FIX_INDENT then indent = current_offset end
 316                   else acc ", " end
 317
 318                   -- Determine whether a newline is required
 319                   local is_id, expected_len = valid_id(k)
 320                   if is_id then expected_len = #k + xlen (v, nested) + #" = , "
 321                   else expected_len = xlen (k, nested) +
 322                                       xlen (v, nested) + #"[] = , " end
 323                   if has_hash and expected_len + current_offset > LINE_MAX
 324                   then acc_newline() end
 325
 326                   -- Print the key
 327                   if is_id then acc(k); acc " = "
 328                   else  acc "["; rec (k, nested, indent+(FIX_INDENT or 0)); acc "] = " end
 329
 330                   -- Print the value
 331                   rec (v, nested, indent+(FIX_INDENT or 0))
 332                   has_hash = true
 333                end
 334             end
 335          end
 336
 337          -- Now we know whether there's a hash-part, an array-part, and a tag.
 338          -- Tag and hash-part are already printed if they're present.
 339          if not has_tag and not has_hash and not has_arr then acc "{ }";
 340          elseif has_tag and not has_hash and not has_arr then -- nothing, tag already in acc
 341          else
 342             assert (has_hash or has_arr)
 343             local no_brace = false
 344             if has_hash and has_arr then acc ", "
 345             elseif has_tag and not has_hash and alen==1 and type(adt[1])~="table" then
 346                -- No brace required; don't print "{", remember not to print "}"
 347                acc (" "); rec (adt[1], nested, indent+(FIX_INDENT or 0))
 348                no_brace = true
 349             elseif not has_hash then
 350                -- Braces required, but not opened by hash-part handler yet
 351                acc "{ "
 352                if not FIX_INDENT then indent = current_offset end
 353             end
 354
 355             -- 2nd pass: array-part
 356             if not no_brace and has_arr then
 357                rec (adt[1], nested, indent+(FIX_INDENT or 0))
 358                for i=2, alen do
 359                   acc ", ";
 360                   if   current_offset + xlen (adt[i], { }) > LINE_MAX
 361                   then acc_newline() end
 362                   rec (adt[i], nested, indent+(FIX_INDENT or 0))
 363                end
 364             end
 365             if not no_brace then acc " }" end
 366          end
 367          nested[adt] = false -- No more nested calls
 368       end
 369       local y = x[type(adt)]
 370       if y then y() else acc(tostring(adt)) end
 371    end
 372    --printf("INITIAL_INDENT = %i", INITIAL_INDENT)
 373    current_offset = INITIAL_INDENT or 0
 374    rec(t, { }, 0)
 375    return table.concat (acc_list)
 376 end
 377
 378 function table.print(...) return print(table.tostring(...)) end
 379
 380 return table