Created
October 31, 2012 05:38
-
-
Save Deco/3985043 to your computer and use it in GitHub Desktop.
Lua Non-recursive Deep-copy
This file contains hidden or 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 | |
| Deep-copy function for Lua 5.2 - v0.1 | |
| ============================== | |
| - Does not overflow the stack. | |
| - Maintains cyclic-references | |
| - Copies metatables | |
| - Maintains common upvalues between copied functions | |
| TODO | |
| ---- | |
| - Clean up | |
| - Fix for Lua 5.1 and LuaJIT | |
| - Provide option for custom type handling | |
| - Provide option to only set metatables, not copy (as if they were immutable) | |
| 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. | |
| ]] | |
| function copy(root, dbg, env) | |
| local ORIG, COPY, RETTO, STATE, PART_SIZE = 0, 1, 2, 3, 4 | |
| local stack_ptr, stack_top, stack = 1, 4, { | |
| --orig,copy,retto,state, | |
| -- LOOP(key,keycopy,retto,keystate, | |
| -- LOOP(keykey,keykeycopy,retto,keykeystate, ..), | |
| -- value,valuecopy,retto,valuestate, | |
| -- LOOP(..) | |
| -- ) | |
| root, nil, -1, nil | |
| } | |
| local copy_dict = stack--[[{ | |
| --[orig] = copy, | |
| }]] | |
| local dbg_label_dict, dbg_pause, dbg_its = {"root", "copy", "ret", "state"}, true, 900 | |
| dbg = dbg and function(op, ...) | |
| local opidx_dict = {} | |
| if op == 'set' then | |
| local arg_list = {...} | |
| for arg_i = 1, #arg_list, 2 do | |
| local idx, label = arg_list[arg_i+0], arg_list[arg_i+1] | |
| dbg_label_dict[idx] = label | |
| opidx_dict[idx] = true | |
| end | |
| end | |
| 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 "")..(opidx_dict[stack_i] 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 | |
| .. (dbg_pause and "" or "\n") | |
| ) | |
| local maxlen = math.max(#line_stack, #line_label, #line_stptr) | |
| if dbg_pause then io.stdout:write(string.rep(" ",70-maxlen), dbg_its) io.read() end | |
| end or function() end | |
| while stack_ptr > 0 and dbg_its > 0 do | |
| dbg() | |
| --local stack_top_last = stack_top | |
| local this_orig = stack[stack_ptr+ORIG] | |
| local this_copy = stack[stack_ptr+COPY] | |
| local this_state = stack[stack_ptr+STATE] | |
| local this_orig_type = type(this_orig) | |
| local this_done = false | |
| if this_orig_type == 'table' then | |
| local grabkey, key_orig, value_orig = false, nil, nil | |
| if this_state == nil then | |
| -- .., orig, copy, retto, state | |
| this_copy = copy_dict[this_orig] | |
| if this_copy ~= nil then | |
| stack[stack_ptr+COPY] = this_copy dbg('set', stack_ptr+COPY, "copy") | |
| stack[stack_ptr+STATE] = 'done' dbg('set', stack_ptr+STATE, "state") | |
| else | |
| this_copy = {} stack[stack_ptr+COPY] = this_copy dbg('set', stack_ptr+COPY, "copy") | |
| copy_dict[this_orig] = this_copy | |
| local this_orig_meta = debug.getmetatable(this_orig) | |
| if this_orig_meta ~= nil then | |
| stack[stack_ptr+STATE] = 'metatable' dbg('set', stack_ptr+STATE, "state") | |
| local retto = stack_ptr | |
| stack_top = stack_top+PART_SIZE | |
| stack_ptr = stack_top-PART_SIZE+1 | |
| stack[stack_ptr+ORIG ] = this_orig_meta | |
| stack[stack_ptr+COPY ] = nil | |
| stack[stack_ptr+RETTO] = retto | |
| stack[stack_ptr+STATE] = nil | |
| dbg('set', stack_ptr+ORIG , "meta" | |
| , stack_ptr+COPY , "copy" | |
| , stack_ptr+RETTO, "ret" | |
| , stack_ptr+STATE, "state" | |
| ) | |
| else | |
| grabkey = true | |
| end | |
| end | |
| elseif this_state == 'metatable' then | |
| -- .., orig, copy, retto, state, metaorig, metacopy | |
| --local this_orig_meta = stack[stack_ptr+PART_SIZE+2*0+ORIG] | |
| local this_copy_meta = stack[stack_ptr+PART_SIZE+2*0+COPY] | |
| stack_top = stack_top-2 -- pop metaorig, metacopy | |
| debug.setmetatable(this_copy, this_copy_meta) | |
| grabkey = true | |
| elseif this_state == 'key' then | |
| -- .., orig, copy, retto, state, keyorig, keycopy | |
| key_orig = stack[stack_ptr+PART_SIZE+ORIG] | |
| if key_orig == nil then | |
| -- done | |
| stack_top = stack_top-2 -- pop keyorig, keycopy | |
| stack[stack_ptr+STATE] = 'done' dbg('set', stack_ptr+3, "state") | |
| else | |
| value_orig = this_orig[key_orig] | |
| stack[stack_ptr+STATE] = 'value' dbg('set', stack_ptr+STATE, "state") | |
| local retto = stack_ptr | |
| stack_top = stack_top+PART_SIZE | |
| stack_ptr = stack_top-PART_SIZE+1 | |
| stack[stack_ptr+ORIG ] = value_orig | |
| stack[stack_ptr+COPY ] = nil | |
| stack[stack_ptr+RETTO] = retto | |
| stack[stack_ptr+STATE] = nil | |
| dbg('set', stack_ptr+ORIG , "value" | |
| , stack_ptr+COPY , "copy" | |
| , stack_ptr+RETTO, "ret" | |
| , stack_ptr+STATE, "state" | |
| ) | |
| end | |
| elseif this_state == 'value' then | |
| -- .., orig, copy, retto, state, keyorig, keycopy, valueorig, valuecopy | |
| key_orig = stack[stack_ptr+PART_SIZE+2*0+ORIG] | |
| --value_orig = stack[stack_ptr+PART_SIZE+2*1+ORIG] | |
| local key_copy = stack[stack_ptr+PART_SIZE+2*0+COPY] | |
| local value_copy = stack[stack_ptr+PART_SIZE+2*1+COPY] | |
| this_copy[key_copy] = value_copy | |
| stack_top = stack_top-4 | |
| grabkey = true -- next! | |
| end | |
| if grabkey then | |
| local key_orig, value_orig = next(this_orig, key_orig) | |
| if key_orig ~= nil then | |
| stack[stack_ptr+STATE] = 'key' dbg('set', stack_ptr+STATE, "state") | |
| local retto = stack_ptr | |
| stack_top = stack_top+PART_SIZE | |
| stack_ptr = stack_top-PART_SIZE+1 | |
| stack[stack_ptr+ORIG ] = key_orig | |
| stack[stack_ptr+COPY ] = nil | |
| stack[stack_ptr+RETTO] = retto | |
| stack[stack_ptr+STATE] = nil | |
| dbg('set', stack_ptr+ORIG , "key" | |
| , stack_ptr+COPY , "copy" | |
| , stack_ptr+RETTO, "ret" | |
| , stack_ptr+STATE, "state" | |
| ) | |
| else | |
| stack[stack_ptr+STATE] = 'done' dbg('set', stack_ptr+STATE, "state") | |
| end | |
| end | |
| elseif this_orig_type == 'function' then | |
| local grabupvalue = false | |
| if this_state == nil then | |
| -- .., orig, copy, retto, state | |
| this_copy = copy_dict[this_orig] | |
| if this_copy ~= nil then | |
| stack[stack_ptr+COPY] = this_copy dbg('set', stack_ptr+COPY, "copy") | |
| stack[stack_ptr+STATE] = 'done' dbg('set', stack_ptr+STATE, "state") | |
| else | |
| this_copy = loadstring(string.dump(this_orig), nil, nil, env) | |
| stack[stack_ptr+COPY] = this_copy dbg('set', stack_ptr+COPY, "copy") | |
| copy_dict[this_orig] = this_copy | |
| stack_top = stack_top+1 | |
| stack[stack_ptr+PART_SIZE+0] = 1 | |
| grabupvalue = true | |
| end | |
| elseif this_state == 'upvalue' then | |
| -- .., orig, copy, retto, state, uvidx, uvvalueorig, uvvaluecopy | |
| local upvalue_idx = stack[stack_ptr+PART_SIZE+0] | |
| --local upvalue_value_orig = stack[stack_ptr+PART_SIZE+1+ORIG] | |
| local upvalue_value_copy = stack[stack_ptr+PART_SIZE+1+ORIG] | |
| stack_top = stack_top-2 -- pop uvvalueorig, uvvaluecopy | |
| debug.setupvalue(this_copy, upvalue_idx, upvalue_value_copy) | |
| stack[stack_ptr+PART_SIZE] = upvalue_idx+1 | |
| grabupvalue = true | |
| end | |
| if grabupvalue then | |
| -- .., orig, copy, retto, state, uvidx | |
| local upvalue_idx_curr = stack[stack_ptr+PART_SIZE+0] | |
| for upvalue_idx = upvalue_idx_curr, math.huge do | |
| local upvalue_name, upvalue_value_orig = debug.getupvalue(this_orig, upvalue_idx) | |
| if upvalue_name ~= nil then | |
| local upvalue_uid = debug.upvalueid(this_orig, upvalue_idx) | |
| -- Attempting to store an upvalueid of a function under root is UB! | |
| local other_orig = copy_dict[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 = copy_dict[other_orig] | |
| debug.upvaluejoin( | |
| this_copy, upvalue_idx, | |
| other_copy, other_upvalue_idx | |
| ) | |
| break | |
| end | |
| end | |
| else | |
| copy_dict[upvalue_uid] = this_orig | |
| if upvalue_value_orig ~= nil then | |
| stack[stack_ptr+STATE] = 'upvalue' dbg('set', stack_ptr+STATE, "state") | |
| local retto = stack_ptr | |
| stack_top = stack_top+PART_SIZE | |
| stack_ptr = stack_top-PART_SIZE+1 | |
| stack[stack_ptr+ORIG ] = upvalue_value_orig | |
| stack[stack_ptr+COPY ] = nil | |
| stack[stack_ptr+RETTO] = retto | |
| stack[stack_ptr+STATE] = nil | |
| dbg('set', stack_ptr+ORIG , "uv" | |
| , stack_ptr+COPY , "copy" | |
| , stack_ptr+RETTO, "ret" | |
| , stack_ptr+STATE, "state" | |
| ) | |
| break | |
| end | |
| end | |
| else | |
| stack_top = stack_top-1 -- pop uvidx | |
| stack[stack_ptr+STATE] = 'done' dbg('set', stack_ptr+3, "state") | |
| break | |
| end | |
| end | |
| end | |
| elseif ( | |
| this_orig_type == 'number' | |
| or this_orig_type == 'string' | |
| or this_orig_type == 'boolean' | |
| or this_orig_type == 'function' | |
| ) then | |
| else error('NYI:'..this_orig_type) end | |
| if stack[stack_ptr+STATE] == 'done' then | |
| -- .., orig, copy, retto, state | |
| local retto = stack[stack_ptr+RETTO] | |
| stack_top = stack_top-2 -- pop retto, state | |
| -- .., orig, copy | |
| stack_ptr = retto | |
| --for stack_i = stack_top, stack_top_last do | |
| -- stack[stack_i] = nil | |
| --end | |
| end | |
| dbg_its = dbg_its-1 | |
| end | |
| return stack[1+COPY] | |
| end |
This file contains hidden or 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(...) | |
| local v | |
| 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 | |
| local nv = copy(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 | |
| _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 | |
| main(...) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
"table.deecopy"