src/lib/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 --[[
 107 function table.iall (f, ...)
 108    local result = true
 109    local function g(...) return not f(...) end
 110    table.iforeach(g, ...)
 111    return result
 112 end
 113
 114 function table.iany (f, ...)
 115    local function g(...) return not f(...) end
 116    return table.iall(g, ...)
 117 end
 118 ]]
 119
 120 function table.inverse (t)
 121    local i = { }
 122    for a, b in pairs(t) do i[b]=a end
 123    return i
 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 function table.tostring(t, ...)
 178    local PRINT_HASH, LINE_MAX, INITIAL_INDENT = true
 179    for _, x in ipairs {...} do
 180       if type(x) == "number" then
 181          if not LINE_MAX then LINE_MAX = x
 182          else INITIAL_INDENT = x end
 183       elseif x=="nohash" then PRINT_HASH = false
 184       end
 185    end
 186    LINE_MAX       = LINE_MAX or math.huge
 187    INITIAL_INDENT = INITIAL_INDENT or 1
 188
 189
 190    local current_offset =  0  -- indentation level
 191    local xlen_cache     = { } -- cached results for xlen()
 192    local acc_list       = { } -- Generated bits of string
 193    local function acc(...)    -- Accumulate a bit of string
 194       local x = table.concat{...}
 195       current_offset = current_offset + #x
 196       table.insert(acc_list, x)
 197    end
 198    local function valid_id(x)
 199       -- FIXME: we should also reject keywords.
 200       return type(x) == "string" and x:strmatch "[a-zA-Z_][a-zA-Z0-9_]*"
 201    end
 202
 203    -- Compute the number of chars it would require to display the table
 204    -- as a single line. Helps to decide whether some carriage returns are
 205    -- required. Since the size of each sub-table is required many times,
 206    -- it's cached in [xlen_cache].
 207    local xlen_type = { }
 208    local function xlen(x, tracker, nested)
 209       tracker = tracker or { }
 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, tracker, 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, tracker, nested)
 231
 232       -- Circular references detection
 233       if nested[adt] then return #tostring(adt) end
 234       tracker = table.shallow_copy(tracker)
 235       tracker [adt]  = true
 236       nested[adt] = true
 237
 238       local has_tag  = valid_id(adt.tag)
 239       local alen     = #adt
 240       local has_arr  = alen>0
 241       local has_hash = false
 242       local x = 0
 243
 244       if PRINT_HASH then
 245          -- first pass: count hash-part
 246          for k, v in pairs(adt) do
 247             if k=="tag" and has_tag then
 248                -- this is the tag -> do nothing!
 249             elseif type(k)=="number" and k<=alen and math.fmod(k,1)==0 then
 250                -- array-part pair -> do nothing!
 251             else
 252                has_hash = true
 253                if valid_id(k) then x=x+#k
 254                else x = x + xlen (k, tracker, nested) + 2 end -- count surrounding barckets
 255                x = x + xlen (v, tracker, nested) + 5          -- count " = " and ", "
 256             end
 257          end
 258       end
 259
 260       for i = 1, alen do x = x + xlen (adt[i], tracker, nested) + 2 end -- count ", "
 261
 262       nested[adt] = false -- No more nested calls
 263
 264       if not (has_tag or has_arr or has_hash) then return 3 end
 265       if has_tag then x=x+#adt.tag+1 end
 266       if not (has_arr or has_hash) then return x end
 267       if not has_hash and alen==1 and type(adt[1])~="table" then
 268          return x-2 -- substract extraneous ", "
 269       end
 270       return x+2 -- count "{ " and " }", substract extraneous ", "
 271    end
 272
 273    -- Recursively print a (sub) table at given indentation level.
 274    -- [newline] indicates whether newlines should be inserted.
 275    local function rec (adt, indent, tracker, nested)
 276       local function acc_newline()
 277          acc ("\n"); acc (string.rep (" ", indent))
 278          current_offset = indent
 279       end
 280       local x = { }
 281       x["nil"] = function() acc "nil" end
 282       function x.number()   acc (tostring (adt)) end
 283       function x.string()   acc (string.format ("%q", adt)) 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          tracker[adt] = true
 288          nested[adt]  = true
 289
 290
 291          local has_tag  = valid_id(adt.tag)
 292          local alen     = #adt
 293          local has_arr  = alen>0
 294          local has_hash = false
 295          local new_indent
 296          if has_tag then acc("`"); acc(adt.tag) end
 297
 298          -- First pass: handle hash-part
 299          if PRINT_HASH then
 300             for k, v in pairs(adt) do
 301                if k=="tag" and has_tag then -- this is the tag -> do nothing!
 302                elseif type(k)=="number" and k<=alen and math.fmod(k,1)==0 then
 303                   -- nothing: this an array-part pair, parsed later
 304                else  -- hash-part pair
 305
 306                   -- Is it the first time we parse a hash pair?
 307                   if not has_hash then acc "{ "; indent = current_offset
 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, tracker, nested) + #" = , "
 313                   else expected_len = xlen (k, tracker, nested) +
 314                                       xlen (v, tracker, 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, current_offset, tracker, nested); acc "] = " end
 321
 322                   -- Print the value
 323                   rec (v, current_offset, tracker, nested)
 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 -- has_hash or has_arr
 334             local no_brace = false
 335             if has_hash and has_arr then acc ", "
 336             elseif has_tag and not has_hash and alen==1 and type(adt[1])~="table" then
 337                -- No brace required; don't print "{", remember not to print "}"
 338                acc (" "); rec (adt[1], new_indent, tracker, nested)
 339                no_brace = true
 340             elseif not has_hash then
 341                -- Braces required, but not opened by hash-part handler yet
 342                acc "{ "; indent = current_offset
 343             end
 344
 345             -- 2nd pass: array-part
 346             if not no_brace and has_arr then
 347                rec (adt[1], new_indent, tracker, nested)
 348                for i=2, alen do
 349                   acc ", ";
 350                   if   current_offset + xlen (adt[i], { }) > LINE_MAX
 351                   then acc_newline() end
 352                   rec (adt[i], new_indent, tracker, nested)
 353                end
 354             end
 355             if not no_brace then acc " }" end
 356          end
 357          nested[adt] = false -- No more nested calls
 358       end
 359       local y = x[type(adt)]
 360       if y then y() else acc(tostring(adt)) end
 361    end
 362    --printf("INITIAL_INDENT = %i", INITIAL_INDENT)
 363    rec(t, INITIAL_INDENT, { }, { })
 364    return table.concat (acc_list)
 365 end
 366
 367 function table.print(...) return print(table.tostring(...)) end
 368
 369 return table