-
-
Save DaZombieKiller/1b5690842b8138a4024c55760e2d253f to your computer and use it in GitHub Desktop.
Lua Non-recursive Deep-copy
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| --[[ deepcopy.lua | |
| Changes in this fork | |
| ==================== | |
| - Added support for table.unpack (Lua 5.2+) | |
| Deep-copy function for Lua - v0.2 | |
| ============================== | |
| - Does not overflow the stack. | |
| - Maintains cyclic-references | |
| - Copies metatables | |
| - Maintains common upvalues between copied functions (for Lua 5.2 only) | |
| TODO | |
| ---- | |
| - Document usage (properly) and provide examples | |
| - Implement handling of LuaJIT FFI ctypes | |
| - Provide option to only set metatables, not copy (as if they were | |
| immutable) | |
| - Find a way to replicate `debug.upvalueid` and `debug.upvaluejoin` in | |
| Lua 5.1 | |
| - Copy function environments in Lua 5.1 and LuaJIT | |
| (Lua 5.2's _ENV is actually a good idea!) | |
| - Handle C functions | |
| Usage | |
| ----- | |
| copy = table.deecopy(orig) | |
| copy = table.deecopy(orig, params, customcopyfunc_list) | |
| `params` is a table of parameters to inform the copy functions how to | |
| copy the data. The default ones available are: | |
| - `value_ignore` (`table`/`nil`): any keys in this table will not be | |
| copied (value should be `true`). (default: `nil`) | |
| - `value_translate` (`table`/`nil`): any keys in this table will result | |
| in the associated value, rather than a copy. (default: `nil`) | |
| (Note: this can be useful for global tables: {[math] = math, ..}) | |
| - `metatable_immutable` (`boolean`): assume metatables are immutable and | |
| do not copy them (only set). (default: `false`) | |
| - `function_immutable` (`boolean`): do not copy function values; instead | |
| use the original value. (default: `false`) | |
| - `function_env` (`table`/`nil`): Set the enviroment of functions to | |
| this value (via fourth arg of `loadstring`). (default: `nil`) | |
| this value. (default: `nil`) | |
| - `function_upvalue_isolate` (`boolean`): do not join common upvalues of | |
| copied functions (only applicable for Lua 5.2 and LuaJIT). (default: | |
| `false`) | |
| - `function_upvalue_dontcopy` (`boolean`): do not copy upvalue values | |
| (does not stop joining). (default: `false`) | |
| `customcopyfunc_list` is a table of typenames to copy functions. | |
| For example, a simple solution for userdata: | |
| { ["userdata"] = function(stack, orig, copy, state, arg1, arg2) | |
| if state == nil then | |
| copy = orig | |
| local orig_uservalue = debug.getuservalue(orig) | |
| if orig_uservalue ~= nil then | |
| stack:recurse(orig_uservalue) | |
| return copy, 'uservalue' | |
| end | |
| return copy, true | |
| elseif state == 'uservalue' then | |
| local copy_uservalue = arg2 | |
| if copy_uservalue ~= nil then | |
| debug.setuservalue(copy, copy_uservalue) | |
| end | |
| return copy, true | |
| end | |
| end } | |
| Any parameters passed to the `params` are available in `stack`. | |
| You can use custom paramter names, but keep in mind that numeric keys and | |
| string keys prefixed with a single underscore are reserved. | |
| License | |
| ------- | |
| Copyright (C) 2012 Declan White | |
| Permission is hereby granted, free of charge, to any person obtaining a | |
| copy of this software and associated documentation files (the "Software"), | |
| to deal in the Software without restriction, including without limitation | |
| the rights to use, copy, modify, merge, publish, distribute, sublicense, | |
| and/or sell copies of the Software, and to permit persons to whom the | |
| Software is furnished to do so, subject to the following conditions: | |
| The above copyright notice and this permission notice shall be included in | |
| all copies or substantial portions of the Software. | |
| THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
| IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
| FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
| THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
| LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
| FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER | |
| DEALINGS IN THE SOFTWARE. | |
| ]] | |
| do | |
| local type = rawtype or type | |
| local rawget = rawget | |
| local rawset = rawset | |
| local next = rawnext or next | |
| local getmetatable = debug and debug.getmetatable or getmetatable | |
| local setmetatable = debug and debug.setmetatable or setmetatable | |
| local debug_getupvalue = debug and debug.getupvalue or nil | |
| local debug_setupvalue = debug and debug.setupvalue or nil | |
| local debug_upvalueid = debug and debug.upvalueid or nil | |
| local debug_upvaluejoin = debug and debug.upvaluejoin or nil | |
| local table = table | |
| local unpack = unpack or table.unpack | |
| table.deepcopy_copyfunc_list = { | |
| --["type"] = function(stack, orig, copy, state, temp1, temp2, temp..., tempN) | |
| -- | |
| -- -- When complete: | |
| -- state = true | |
| -- | |
| -- -- Store temporary variables between iterations using these: | |
| -- -- (Note: you MUST NOT call these AFTER recurse) | |
| -- stack:_push(tempN+1, tempN+2, tempN+..., tempN+M) | |
| -- stack:_pop(K) | |
| -- -- K is the number to pop. | |
| -- -- If you wanted to pop two from the last state and push four new ones: | |
| -- stack:_pop(2) | |
| -- stack:_push('t', 'e', 's', 't') | |
| -- | |
| -- -- To copy a child value: | |
| -- -- (Note: any calls to push or pop MUST be BEFORE a call to this) | |
| -- state:recurse(childvalue_orig) | |
| -- -- This will leave two temp variables on the stack for the next iteration | |
| -- -- .., childvalue_orig, childvalue_copy | |
| -- -- which are available via the varargs (temp...) | |
| -- -- (Note: the copy may be nil if it was not copied (because caller | |
| -- -- specified it not to be)). | |
| -- -- You can only call this once per iteration. | |
| -- | |
| -- -- Return like this: | |
| -- -- (Temp variables are not part of the return list due to optimisation.) | |
| -- return copy, state | |
| -- | |
| --end, | |
| _plainolddata = function(stack, orig, copy, state) | |
| return orig, true | |
| end, | |
| ["table"] = function(stack, orig, copy, state, arg1, arg2, arg3, arg4) | |
| local orig_prevkey, grabkey = nil, false | |
| if state == nil then -- 'init' | |
| -- Initial state, check for metatable, or get first key | |
| -- orig, copy:nil, state | |
| copy = stack[orig] | |
| if copy ~= nil then -- Check if already copied | |
| return copy, true | |
| else | |
| copy = {} -- Would be nice if you could preallocate sizes! | |
| stack[orig] = copy | |
| local orig_meta = getmetatable(orig) | |
| if orig_meta ~= nil then -- This table has a metatable, copy it | |
| if not stack.metatable_immutable then | |
| stack:_recurse(orig_meta) | |
| return copy, 'metatable' | |
| else | |
| setmetatable(copy, orig_meta) | |
| end | |
| end | |
| end | |
| -- No metatable, go straight to copying key-value pairs | |
| orig_prevkey = nil -- grab first key | |
| grabkey = true --goto grabkey | |
| elseif state == 'metatable' then | |
| -- Metatable has been copied, set it and get first key | |
| -- orig, copy:{}, state, metaorig, metacopy | |
| local copy_meta = arg2--select(2, ...) | |
| stack:_pop(2) | |
| if copy_meta ~= nil then | |
| setmetatable(copy, copy_meta) | |
| end | |
| -- Now start copying key-value pairs | |
| orig_prevkey = nil -- grab first key | |
| grabkey = true --goto grabkey | |
| elseif state == 'key' then | |
| -- Key has been copied, now copy value | |
| -- orig, copy:{}, state, keyorig, keycopy | |
| local orig_key = arg1--select(1, ...) | |
| local copy_key = arg2--select(2, ...) | |
| if copy_key ~= nil then | |
| -- leave keyorig and keycopy on the stack | |
| local orig_value = rawget(orig, orig_key) | |
| stack:_recurse(orig_value) | |
| return copy, 'value' | |
| else -- key not copied? move onto next | |
| stack:_pop(2) -- pop keyorig, keycopy | |
| orig_prevkey = orig_key | |
| grabkey = true--goto grabkey | |
| end | |
| elseif state == 'value' then | |
| -- Value has been copied, set it and get next key | |
| -- orig, copy:{}, state, keyorig, keycopy, valueorig, valuecopy | |
| local orig_key = arg1--select(1, ...) | |
| local copy_key = arg2--select(2, ...) | |
| --local orig_value = arg3--select(3, ...) | |
| local copy_value = arg4--select(4, ...) | |
| stack:_pop(4) | |
| if copy_value ~= nil then | |
| rawset(copy, copy_key, copy_value) | |
| end | |
| -- Grab next key to copy | |
| orig_prevkey = orig_key | |
| grabkey = true --goto grabkey | |
| end | |
| --return | |
| --::grabkey:: | |
| if grabkey then | |
| local orig_key, orig_value = next(orig, orig_prevkey) | |
| if orig_key ~= nil then | |
| stack:_recurse(orig_key) -- Copy key | |
| return copy, 'key' | |
| else | |
| return copy, true -- Key is nil, copying of table is complete | |
| end | |
| end | |
| return | |
| end, | |
| ["function"] = function(stack, orig, copy, state, arg1, arg2, arg3) | |
| local grabupvalue, grabupvalue_idx = false, nil | |
| if state == nil then | |
| -- .., orig, copy, state | |
| copy = stack[orig] | |
| if copy ~= nil then | |
| return copy, true | |
| elseif stack.function_immutable then | |
| copy = orig | |
| return copy, true | |
| else | |
| copy = loadstring(string.dump(orig), nil, nil, stack.function_env) | |
| stack[orig] = copy | |
| if debug_getupvalue ~= nil and debug_setupvalue ~= nil then | |
| grabupvalue = true | |
| grabupvalue_idx = 1 | |
| else | |
| -- No way to get/set upvalues! | |
| return copy, true | |
| end | |
| end | |
| elseif this_state == 'upvalue' then | |
| -- .., orig, copy, state, uvidx, uvvalueorig, uvvaluecopy | |
| local orig_upvalue_idx = arg1 | |
| --local orig_upvalue_value = arg2 | |
| local copy_upvalue_value = arg3 | |
| stack:_pop(3) | |
| debug_setupvalue(copy, orig_upvalue_idx, copy_upvalue_value) | |
| grabupvalue_idx = orig_upvalue_idx+1 | |
| stack:_push(grabupvalue_idx) | |
| grabupvalue = true | |
| end | |
| if grabupvalue then | |
| -- .., orig, copy, retto, state, uvidx | |
| local upvalue_idx_curr = grabupvalue_idx | |
| for upvalue_idx = upvalue_idx_curr, math.huge do | |
| local upvalue_name, upvalue_value_orig = debug_getupvalue(orig, upvalue_idx) | |
| if upvalue_name ~= nil then | |
| local upvalue_handled = false | |
| if not stack.function_upvalue_isolate and debug_upvalueid ~= nil and debug_upvaluejoin ~= nil then | |
| local upvalue_uid = debug.upvalueid(orig, upvalue_idx) | |
| -- Attempting to store an upvalueid of a function as a child of root is UB! | |
| local other_orig = stack[upvalue_uid] | |
| if other_orig ~= nil then | |
| for other_upvalue_idx = 1, math.huge do | |
| if upvalue_uid == debug_upvalueid(other_orig, other_upvalue_idx) then | |
| local other_copy = stack[other_orig] | |
| debug_upvaluejoin( | |
| copy, upvalue_idx, | |
| other_copy, other_upvalue_idx | |
| ) | |
| break | |
| end | |
| end | |
| upvalue_handled = true | |
| else | |
| stack[upvalue_uid] = orig | |
| end | |
| end | |
| if not stack.function_upvalue_dontcopy and not upvalue_handled and upvalue_value_orig ~= nil then | |
| stack:_recurse(upvalue_value_orig) | |
| return copy, 'upvalue' | |
| end | |
| else | |
| stack:_pop(1) -- pop uvidx | |
| return copy, true | |
| end | |
| end | |
| end | |
| end, | |
| ["userdata"] = nil, | |
| ["lightuserdata"] = nil, | |
| ["thread"] = nil, | |
| } | |
| table.deepcopy_copyfunc_list["number" ] = table.deepcopy_copyfunc_list._plainolddata | |
| table.deepcopy_copyfunc_list["string" ] = table.deepcopy_copyfunc_list._plainolddata | |
| table.deepcopy_copyfunc_list["boolean"] = table.deepcopy_copyfunc_list._plainolddata | |
| -- `nil` should never be encounted... but just in case: | |
| table.deepcopy_copyfunc_list["nil" ] = table.deepcopy_copyfunc_list._plainolddata | |
| do | |
| local ORIG, COPY, RETTO, STATE, SIZE = 0, 1, 2, 3, 4 | |
| function table.deepcopy_push(...) | |
| local arg_list_len = select('#', ...) | |
| local stack_offset = stack._top+1 | |
| for arg_i = 1, arg_list_len do | |
| stack[stack_offset+arg_i] = select(arg_i, ...) | |
| end | |
| stack._top = stack_top+arg_list_len | |
| end | |
| function table.deepcopy_pop(stack, count) | |
| stack._top = stack._top-count | |
| end | |
| function table.deepcopy_recurse(stack, orig) | |
| local retto = stack._ptr | |
| local stack_top = stack._top | |
| local stack_ptr = stack_top+1 | |
| stack._top = stack_top+SIZE | |
| stack._ptr = stack_ptr | |
| stack[stack_ptr+ORIG ] = orig | |
| stack[stack_ptr+COPY ] = nil | |
| stack[stack_ptr+RETTO] = retto | |
| stack[stack_ptr+STATE] = nil | |
| end | |
| function table.deepcopy(root, params, customcopyfunc_list) | |
| local stack = params or {} | |
| --orig,copy,retto,state,[temp...,] partorig,partcopy,partretoo,partstate | |
| stack[1+ORIG ] = root stack[1+COPY ] = nil | |
| stack[1+RETTO] = nil stack[1+STATE] = nil | |
| stack._ptr = 1 stack._top = 4 | |
| stack._push = table.deepcopy_push stack._pop = table.deepcopy_pop | |
| stack._recurse = table.deepcopy_recurse | |
| --[[local stack_dbg do -- debug | |
| stack_dbg = stack | |
| stack = setmetatable({}, { | |
| __index = stack_dbg, | |
| __newindex = function(t, k, v) | |
| stack_dbg[k] = v | |
| if tonumber(k) then | |
| local stack = stack_dbg | |
| local line_stack, line_label, line_stptr = "", "", "" | |
| for stack_i = 1, math.max(stack._top, stack._ptr) do | |
| local s_stack = ( | |
| (type(stack[stack_i]) == 'table' or type(stack[stack_i]) == 'function') | |
| and string.gsub(tostring(stack[stack_i]), "^.-(%x%x%x%x%x%x%x%x)$", "<%1>") | |
| or tostring(stack[stack_i]) | |
| ), type(stack[stack_i]) | |
| local s_label = ""--dbg_label_dict[stack_i] or "?!?" | |
| local s_stptr = (stack_i == stack._ptr and "*" or "")..(stack_i == k and "^" or "") | |
| local maxlen = math.max(#s_stack, #s_label, #s_stptr)+1 | |
| line_stack = line_stack..s_stack..string.rep(" ", maxlen-#s_stack) | |
| --line_label = line_label..s_label..string.rep(" ", maxlen-#s_label) | |
| line_stptr = line_stptr..s_stptr..string.rep(" ", maxlen-#s_stptr) | |
| end | |
| io.stdout:write( | |
| line_stack | |
| --.. "\n"..line_label | |
| .. "\n"..line_stptr | |
| .. "" | |
| ) | |
| io.read() | |
| elseif false then | |
| io.stdout:write(("stack.%s = %s"):format( | |
| k, | |
| ( | |
| (type(v) == 'table' or type(v) == 'function') | |
| and string.gsub(tostring(v), "^.-(%x%x%x%x%x%x%x%x)$", "<%1>") | |
| or tostring(v) | |
| ) | |
| )) | |
| io.read() | |
| end | |
| end, | |
| }) | |
| end]] | |
| local copyfunc_list = table.deepcopy_copyfunc_list | |
| repeat | |
| local stack_ptr = stack._ptr | |
| local this_orig = stack[stack_ptr+ORIG] | |
| local this_copy, this_state | |
| stack[0] = stack[0] | |
| if stack.value_ignore and stack.value_ignore[this_orig] then | |
| this_copy = nil | |
| this_state = true --goto valuefound | |
| else | |
| if stack.value_translate then | |
| this_copy = stack.value_translate[this_orig] | |
| if this_copy ~= nil then | |
| this_state = true --goto valuefound | |
| end | |
| end | |
| if not this_state then | |
| local this_orig_type = type(this_orig) | |
| local copyfunc = ( | |
| customcopyfunc_list and customcopyfunc_list[this_orig_type] | |
| or copyfunc_list[this_orig_type] | |
| or error(("cannot copy type %q"):format(this_orig_type), 2) | |
| ) | |
| this_copy, this_state = copyfunc( | |
| stack, | |
| this_orig, | |
| stack[stack_ptr+COPY], | |
| unpack(stack--[[_dbg]], stack_ptr+STATE, stack._top) | |
| ) | |
| end | |
| end | |
| stack[stack_ptr+COPY] = this_copy | |
| --::valuefound:: | |
| if this_state == true then | |
| local retto = stack[stack_ptr+RETTO] | |
| stack._top = stack_ptr+1 -- pop retto, state, temp... | |
| -- Leave orig and copy on stack for parent object | |
| stack_ptr = retto -- return to parent's stack frame | |
| stack._ptr = stack_ptr | |
| else | |
| stack[stack_ptr+STATE] = this_state | |
| end | |
| until stack_ptr == nil | |
| return stack[1+COPY] | |
| end | |
| end | |
| end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function main(...) | |
| -- cyclic table | |
| local v | |
| do | |
| v = { | |
| 'a', | |
| cactus = { | |
| 6, | |
| abc = { 22 }, | |
| }, | |
| 'c' | |
| } | |
| v.cactus.abc.q = v | |
| end | |
| --[[setfenv(table.deepcopy, | |
| setmetatable({}, { | |
| __index = function(t,k ) error(("_G[%q]!" ):format(tostring(k) ), 2) end, | |
| __newindex = function(t,k,v) error(("_G[%q] = %q!"):format(tostring(k),tostring(v)), 2) end, | |
| }) | |
| )]] | |
| local nv = table.deepcopy(v) | |
| print(stringify(nv)) | |
| -- common upvalue | |
| do | |
| local uv = nil | |
| v = { | |
| set = function(v) uv = v return uv end, | |
| get = function() return uv end, | |
| cactus = { | |
| a = function() uv = 22 end | |
| } | |
| } | |
| end | |
| nv = table.deepcopy(v) | |
| print(stringify(nv)) | |
| print("v.set("..tostring(v.set(5))..")") | |
| print("nv.set("..tostring(nv.set(6))..")") | |
| print("v.get() == "..tostring(v.get())) | |
| print("nv.get() == "..tostring(nv.get())) | |
| print("v a!") v.cactus.a() | |
| print("v.get() == "..tostring(v.get())) | |
| print("nv.get() == "..tostring(nv.get())) | |
| print("nv a!") nv.cactus.a() | |
| print("v.get() == "..tostring(v.get())) | |
| print("nv.get() == "..tostring(nv.get())) | |
| end | |
| require"stringify" | |
| main(...) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| _stringify = function(stack, this, spacing_h, spacing_v, space_n, parsed) | |
| local this_type = type(this) | |
| if this_type == "string" then | |
| stack[#stack+1] = ( | |
| spacing_v ~= "\n" and string.gsub(string.format("%q", this), "\\\n", "\\n") | |
| or string.format("%q", this) | |
| ) | |
| elseif this_type == "boolean" then | |
| stack[#stack+1] = this and "true" or "false" | |
| elseif this_type == "number" then | |
| stack[#stack+1] = tostring(this) | |
| elseif this_type == "function" then | |
| local info = debug.getinfo(this, "S") | |
| stack[#stack+1] = "function" | |
| stack[#stack+1] = ":(" | |
| if not info or info.what == "C" then | |
| stack[#stack+1] = "[C]" | |
| else | |
| --[[local param_list = debug.getparams(this) | |
| for param_i = 1, #param_list do | |
| stack[#stack+1] = param_list[param_i] | |
| end]] | |
| end | |
| stack[#stack+1] = ")" | |
| elseif this_type == "table" then | |
| if parsed[this] then | |
| stack[#stack+1] = "<"..tostring(this)..">" | |
| else | |
| parsed[this] = true | |
| stack[#stack+1] = "{"..spacing_v | |
| for key,val in pairs(this) do | |
| stack[#stack+1] = string.rep(spacing_h, space_n).."[" | |
| _stringify(stack, key, spacing_h, spacing_v, space_n+1, parsed) | |
| stack[#stack+1] = "] = " | |
| _stringify(stack, val, spacing_h, spacing_v, space_n+1, parsed) | |
| stack[#stack+1] = ","..spacing_v | |
| end | |
| stack[#stack+1] = string.rep(spacing_h, space_n-1).."}" | |
| end | |
| elseif this_type == "nil" then | |
| stack[#stack+1] = "nil" | |
| else | |
| stack[#stack+1] = this_type.."<"..tostring(this)..">" | |
| end | |
| end | |
| stringify = function(this, docol, spacing_h, spacing_v, preindent) | |
| local stack = {} | |
| _stringify( | |
| stack, | |
| this, | |
| spacing_h or " ", spacing_v or "\n", | |
| (tonumber(preindent) or 0)+1, | |
| {} | |
| ) | |
| return table.concat(stack) | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment