Create a gist now

Instantly share code, notes, and snippets.

@vote539 /ot.lua
Last active Apr 19, 2017

What would you like to do?
An implementation of operational transformation in Lua, designed for integration with Redis. See http://codrspace.com/vote539/operational-tranformation-in-redis/
-- 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
-- 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))
-- 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
-- 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) == "")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment