Skip to content

Instantly share code, notes, and snippets.

@Deco

Deco/deepcopy.lua

Created October 31, 2012 05:38
Show Gist options
  • Save Deco/3985043 to your computer and use it in GitHub Desktop.
Save Deco/3985043 to your computer and use it in GitHub Desktop.
Download ZIP
Lua Non-recursive Deep-copy
Raw
deepcopy.lua
--[[ deepcopy.lua
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 unpack = unpack
local table = table
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
Raw
deepcopy_test.lua
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(...)
Raw
stringify.lua
_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
@LoganDark
Copy link

"table.deecopy"

@Vovkiv
Copy link

Vovkiv commented Oct 27, 2021

♂deep♂ copy

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment