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