DeepCopy.lua

local addonName,addonTable = ...
local DA = LibStub("AceAddon-3.0"):GetAddon("Skillet")
--[[ 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 = DA.deepcopy(orig)
		copy = DA.deepcopy(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
	DA.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,
	}
	DA.deepcopy_copyfunc_list["number" ] = DA.deepcopy_copyfunc_list._plainolddata
	DA.deepcopy_copyfunc_list["string" ] = DA.deepcopy_copyfunc_list._plainolddata
	DA.deepcopy_copyfunc_list["boolean"] = DA.deepcopy_copyfunc_list._plainolddata
	-- `nil` should never be encounted... but just in case:
	DA.deepcopy_copyfunc_list["nil"    ] = DA.deepcopy_copyfunc_list._plainolddata
	
	do
		local ORIG, COPY, RETTO, STATE, SIZE = 0, 1, 2, 3, 4
		function DA.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 DA.deepcopy_pop(stack, count)
			stack._top = stack._top-count
		end
		function DA.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 DA.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 = DA.deepcopy_push stack._pop = DA.deepcopy_pop
			stack._recurse = DA.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 = DA.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