An implementation of operational transformation in Lua, designed for integration with Redis. See https://blog.sffc.xyz/post/182052412225/operational-tranformation-in-redis

ot.lua

-- Copyright (c) 2016, Shane Carr (ISC License)
-- 
-- Permission to use, copy, modify, and/or distribute this software for any
-- purpose with or without fee is hereby granted, provided that the above
-- copyright notice and this permission notice appear in all copies.
-- 
-- THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

-- This code is based on the JavaScript implementation ot.js:
-- https://github.com/Operational-Transformation/ot.js/

-- For a tutorial on using this code, see my blog post:
-- http://codrspace.com/vote539/operational-tranformation-in-redis/

-- Lua has poor support for UTF-8, so we need to have custom functions.
-- These are based on those originally written by Cosmin Apreutesei:
-- https://github.com/luapower/utf8
-- Use the prefix "lutf8" in case at some point in the future Redis adds a "utf8" library.
function lutf8_next(s, i)
	if not i then
		if #s == 0 then return nil end
		return 1, true --fake flag (doesn't matter since this flag is not to be taken as full validation)
	end
	if i > #s then return end
	local c = s:byte(i)
	if c >= 0x00 and c <= 0x7F then
		i = i + 1
	elseif c >= 0xC2 and c <= 0xDF then
		i = i + 2
	elseif c >= 0xE0 and c <= 0xEF then
		i = i + 3
	elseif c >= 0xF0 and c <= 0xF4 then
		i = i + 4
	else --invalid; treat as 1-byte character
		return i + 1, false
	end
	if i > #s then return end
	return i, true
end

-- Iterator over byte indices in the string.
function lutf8_byte_indices(s, previ)
	return lutf8_next, s, previ
end

-- Returns the number of UTF-8 characters in the string, like string.len.
function lutf8_len(s)
	local len = 0
	for _ in lutf8_byte_indices(s) do
		len = len + 1
	end
	return len
end

-- Performs a substring operation, like string.sub.
function lutf8_sub(s, start_ci, end_ci)
	local ci = 0
	local start_i = 1
	local end_i = s:len()
	for i in lutf8_byte_indices(s) do
		ci = ci + 1
		if ci == start_ci then
			start_i = i
		end
		if ci == end_ci+1 then
			end_i = i-1
			break
		end
	end
	return string.sub(s, start_i, end_i)
end

-- OT: Remove redundant ops from an operations table
function condense(ops)
	local i = 2

	while ops[i] ~= nil do
		-- insert/insert
		if type(ops[i]) == "string" and type(ops[i-1]) == "string" then
			ops[i-1] = ops[i-1] .. ops[i]
			table.remove(ops, i)

		-- delete/insert
		-- The order of these operations does not matter with
		-- respect to the "apply" function, but for consistency
		-- we always put "insert" first.
		elseif type(ops[i]) == "string" and ops[i-1]<0 then
			local tmp = ops[i]
			ops[i] = ops[i-1]
			ops[i-1] = tmp

			-- go backwards in case the new insert can be condensed
			i = i-1

		-- other/insert (do nothing)
		elseif type(ops[i]) == "string" or type(ops[i-1]) == "string" then
			i = i+1

		-- delete/delete
		elseif ops[i]<0 and ops[i-1]<0 then
			ops[i-1] = ops[i-1] + ops[i]
			table.remove(ops, i)

		-- retain/retain
		elseif ops[i]>0 and ops[i-1]>0 then
			ops[i-1] = ops[i-1] + ops[i]
			table.remove(ops, i)

		-- something else that we can't condense
		else
			i = i+1

		end

		if i<2 then
			i = 2
		end
	end
end

-- OT: Transform takes two operations A and B that happened
-- concurrently and produces two operations A' and B'
-- such that apply(apply(S,A),B') == apply(apply(S,B),A')
-- This function is the heart of OT.
function transform(ops1, ops2)
	local ops1p = {}
	local ops2p = {}
	local i1 = 1
	local i2 = 1
	local op1 = ops1[i1]
	local op2 = ops2[i2]
	local minl = 0

	while op1 ~= nil or op2 ~= nil do
		-- insert by player 1
		-- break tie by prefering player 1
		if type(op1) == "string" then
			table.insert(ops1p, op1) -- insert
			table.insert(ops2p, lutf8_len(op1)) -- retain
			i1 = i1+1; op1 = ops1[i1]

		-- insert by player 2
		elseif type(op2) == "string" then
			table.insert(ops1p, lutf8_len(op2)) -- retain
			table.insert(ops2p, op2) -- insert
			i2 = i2+1; op2 = ops2[i2]

		-- retain/retain
		elseif op1>0 and op2>0 then
			if op1>op2 then
				minl = op2
				op1 = op1 - op2
				i2 = i2+1; op2 = ops2[i2]
			elseif op1 == op2 then
				minl = op2
				i1 = i1+1; op1 = ops1[i1]
				i2 = i2+1; op2 = ops2[i2]
			else
				minl = op1
				op2 = op2 - op1
				i1 = i1+1; op1 = ops1[i1]
			end
			table.insert(ops1p, minl) -- retain
			table.insert(ops2p, minl) -- retain

		-- delete/delete
		elseif op1<0 and op2<0 then
			if op1 < op2 then
				op1 = op1 - op2
				i2 = i2+1; op2 = ops2[i2]
			elseif op1 == op2 then
				i1 = i1+1; op1 = ops1[i1]
				i2 = i2+1; op2 = ops2[i2]
			else
				op2 = op2 - op1
				i1 = i1+1; op1 = ops1[i1]
			end

		-- delete/retain
		elseif op1<0 and op2>0 then
			if -op1 > op2 then
				minl = op2
				op1 = op1 + op2
				i2 = i2+1; op2 = ops2[i2]
			elseif -op1 == op2 then
				minl = op2
				i1 = i1+1; op1 = ops1[i1]
				i2 = i2+1; op2 = ops2[i2]
			else
				minl = -op1
				op2 = op2 + op1
				i1 = i1+1; op1 = ops1[i1]
			end
			table.insert(ops1p, -minl) -- delete

		-- retain/delete
		elseif op1>0 and op2<0 then
			if op1 > -op2 then
				minl = -op2
				op1 = op1 + op2
				i2 = i2+1; op2 = ops2[i2]
			elseif op1 == -op2 then
				minl = op1
				i1 = i1+1; op1 = ops1[i1]
				i2 = i2+1; op2 = ops2[i2]
			else
				minl = op1
				op2 = op2 + op1
				i1 = i1+1; op1 = ops1[i1]
			end
			table.insert(ops2p, -minl) -- delete

		-- noop
		elseif op1==0 then
			i1 = i1+1; op1 = ops1[i1]
		elseif op2==0 then
			i2 = i2+1; op2 = ops2[i2]

		-- unknown
		else
			error()
		end
	end

	condense(ops1p)
	condense(ops2p)
	return ops1p, ops2p
end

-- OT: Apply an operation to a text
function apply(str, ops)
	local j = 1
	local res = ""

	for i,op in pairs(ops) do

		-- insert
		if type(op)=="string" then
			res = res .. op

		-- delete
		elseif op<0 then
			j = j - op

		-- retain
		else
			res = res .. lutf8_sub(str, j, j+op-1)
			j = j + op
		end
	end

	return res
end

ot_apply.lua

-- Perform operations on server.
-- Read arguments
local rev = tonumber(ARGV[1])
local message = cjson.decode(ARGV[2])
local op_expiretime = tonumber(ARGV[3])
local doc_expiretime = tonumber(ARGV[4])
local ops_key = KEYS[1]
local doc_key = KEYS[2]
local sub_key = KEYS[3]
local cnt_key = KEYS[4]

-- Load concurrent operations.  The operations store is truncated according
-- to the call to "EXPIRE" later in this file, so we need to compute the index
-- into the operations store relative to the current length of the store.  If
-- that index is out of range of the list, then some of the concurrent
-- operations required for transforming the new operation have been expired
-- out of the cache, and we need to raise an error.
local nrev = redis.call("GET", cnt_key)
if not nrev then nrev = 0 end
local nstore = redis.call("LLEN", ops_key)
if not nstore then nstore = 0 end
local idx = nstore-nrev+rev
if idx < 0 then error("Operation history is too shallow") end
local concurrent = redis.call("LRANGE", ops_key, idx, -1)

-- Transform the new operation against all the concurrent operations
if concurrent then
	for i,cops in pairs(concurrent) do
		message.ops = transform(message.ops, cjson.decode(cops))
	end
end

-- Save the operation
redis.call("RPUSH", ops_key, cjson.encode(message.ops))
redis.call("INCR", cnt_key)

-- Load and apply to the document
local doc = redis.call("GET", doc_key)
if type(doc)=="boolean" then doc="" end
doc = apply(doc, message.ops)
redis.call("SET", doc_key, doc)

-- Touch the operation keys' expire value
redis.call("EXPIRE", ops_key, op_expiretime)
redis.call("EXPIRE", doc_key, doc_expiretime)
redis.call("EXPIRE", cnt_key, doc_expiretime)

-- Publish to the subscribe channel
redis.call("PUBLISH", sub_key, cjson.encode(message))

ot_set.lua

-- Set an OT document to the specified value using transformations.
-- Read arguments
local content = ARGV[1]
local message = cjson.decode(ARGV[2])
local op_expiretime = tonumber(ARGV[3])
local doc_expiretime = tonumber(ARGV[4])
local overwrite = ARGV[5]
local ops_key = KEYS[1]
local doc_key = KEYS[2]
local sub_key = KEYS[3]
local cnt_key = KEYS[4]

-- Load the document's current content from Redis
local old_content = redis.call("GET", doc_key)

if type(old_content)=="boolean" then
	-- Document doesn't exist.  Make an operation to set its content.
	message.ops = {content}

elseif old_content==content then
	-- Document exists and is already set to the desired value.  Exit.
	return 0

elseif overwrite=="overwrite" then
	-- Transform the old document into the new one.  The naive approach would
	-- be something like the following:
	message.ops = {-string.len(old_content), content}
	-- TODO: Figure out the best way to do this

else
	-- No action necessary
	return 0

end

-- Update Redis
redis.call("SET", doc_key, content)
redis.call("INCR", cnt_key)
redis.call("RPUSH", ops_key, cjson.encode(message.ops))
redis.call("PUBLISH", sub_key, cjson.encode(message))

-- Touch the operation keys' expire value
redis.call("EXPIRE", ops_key, op_expiretime)
redis.call("EXPIRE", doc_key, doc_expiretime)
redis.call("EXPIRE", cnt_key, doc_expiretime)

return 1

ot_test.lua

-- Tests for the OT implementation.

require "ot"

function table_equals(a,b)
	i = 1
	while a[i] ~= nil do
		if a[i] ~= b[i] then return false end
		i = i+1
	end
	if a[i]~=nil or b[i]~=nil then return false end
	return true
end

-- Test a few condense operations
ops = {5, "hello", -3, 6}
condense(ops)
assert(table_equals(ops, {5, "hello", -3, 6}))

ops = {5, -3, "hello", 6}
condense(ops)
assert(table_equals(ops, {5, "hello", -3, 6}))

ops = {2, 3, "he", -2, "llo", -1, 4, 2}
condense(ops)
assert(table_equals(ops, {5, "hello", -3, 6}))

-- Test some apply operations
str = apply("hello world", {6, "earth", -5})
assert(str == "hello earth")

ops1 = {6, "world", -5} -- lorem world
ops2 = {"hello", -5, 6} -- hello ipsum
str = apply(apply("lorem ipsum", ops1), ops2)
assert(str == "hello world")

-- Test a transform operation
str = "lorem ipsum"
ops1 = {6, "world", -5} -- lorem world
ops2 = {"hello", -5, 6} -- hello ipsum
ops1p, ops2p = transform(ops1, ops2) -- hello world
str1 = apply(apply(str, ops1), ops2p)
str2 = apply(apply(str, ops2), ops1p)
assert(str1 == str2)

-- Test some UTF-8 commands
str = "abçd"
assert(lutf8_len(str) == 4)
assert(lutf8_sub(str, 2, 3) == "bç")