View on GitHub

Notepal

Jupiter System - Collaborative Editing - Applied to Sticky Notes

Download this project as a .zip file Download this project as a tar.gz file

Operations

For our demo, the following operations have been implemented for our Jupiter System:

sAdd

sDel

sDrag

cIns /!\ Deprecated, use sIns

cDel /!\ Deprecated, use sDel

sIns

sDel

Transformation Rules

In order to solve conflict, the function xform applies some modifications for both operations, depending of which couple it is. You will find here the transformations we chose to solve logically the conflicts without any loss of information.

Local cIns VS Incoming cIns

xform( cIns(p, c, id), cIns(p', c', id') ) :-
    if (id != id') then return {cIns(p, c, id), cIns(p', c', id')} // no collision
    if (p >= p') then return {cIns(p+1,c), cIns(p',c')} // we arbitrarily decide to place the char from the server first. 
    if (p < p') then return {cIns(p,c), cIns(p'+1,c')}

Local cDel VS Incoming cDel

xform( cDel(p, id), cDel(p', id') ) :-
    if (id != id') then return {cDel(p, id), cDel(p', id')} // no collision
    if (p > p') then return {cDel(p-1), cDel(p')}
    if (p < p') then return {cDel(p), cDel(p'-1)}
    if (p = p') then return {no-op, no-op}

Local cDel VS Incoming cIns

xform( cDel(p, id), cIns(p', c', id') ) :-
    if (id != id') then return {cDel(p, id), cIns(p', c', id')} // no collision
    if (p >= p') then return {cDel(p+1), cIns(p',c')}
    if (p < p') then return {cDel(p), cIns(p'-1,c')}

Local cIns VS Incoming cDel

xform( cIns(p, c, id), cDel(p', id') ) :-
    if (id != id') then return {cIns(p, c, id), cDel(p', id')} // no collision
    if (p > p') then return {cIns(p,c), cDel(p'+1)}
    if (p =< p') then return {cIns(p-1,c), cDel(p')}

Local sIns VS Incoming sIns

xform( sIns(p, str, id), sIns(p', str', id') ) :-
    if (id != id') then return {sIns(p, str, id), sIns(p', str', id')} // no collision
    if (p >= p') then return {sIns(p+|str|,str), sIns(p',str')} // we arbitrarily decide to place the char from the server first. 
    if (p < p') then return {sIns(p,str), sIns(p'+|str|,str')}

Local sDel VS Incoming sDel

xform( sDel(p, s, id), sDel(p', s', id') ) :-
    if (id != id') then return {sDel(p, s, id), sDel(p', s', id')} // no collision

    posEndLoc = p + s,
    posEndInc = p' + s';
    if (p' >= posEndLoc) then return {sDel(p, s, id), sDel(p'-s, s', id')}
    else if (p >= posEndInc) then return {sDel(p-s', s, id), sDel(p'-s, s', id')}
    else if (p' >= p)

        if (posEndInc <= posEndLoc) // Everything incoMsg was supposed to delete as already been by localMesg.

            s = s-s';
            if (s == 0) then return {no-op, no-op}
            else return {sDel(p, s, id), no-op}

        else    // Par of what incoMsg was supposed to delete as already been by localMesg.
            return {sDel(p, s - (posEndLoc - p'), id), sDel(p, posEndInc - posEndLoc, id')}

    else // if (p' < p)

        if (posEndLoc <= posEndInc)

            s' = s'-s;
            if (s == 0) then return {no-op, no-op}
            else return {no-op, sDel(p', s', id')}

        else
            return {sDel(p', posEndInc - posEndLoc, id), sDel(p', s' - (posEndInc - p), id')}

Local sDel VS Incoming sIns

xform( sDel(p, s, id), sIns(p', str', id') ) :-
    if (id != id') then return {sDel(p, s, id), sIns(p', str', id')} // no collision
    if (p >= p') then return {cDel(p+1), sIns(p',str')}
    if (p < p') then return {cDel(p), sIns(p'-1,str')}

    posEndLoc = p + s,
    posEndInc = p' + s';
    if (p' <= p) then return {sDel(p+s', s, id), sIns(p', str', id')}
    else if (p' >= posEndLoc) then return {sDel(p, s, id), sIns(p'-s', str', id')}
    else // The insertion is done inside the deleted text. So we still insert there, and cut the delete operation in two parts, for each side of the insertion.
        // We add a sDel operation to delete the right side.
        generatePseudoOperation(sDel(posEndInc, s - (p' - p), id'))
        // ... and we use the current local sDel to delete the left side:
        then return {sDel(p, p'-p, id), sIns(p, str', id')}

Local sIns VS Incoming sDel

xform( sIns(p, str, id), sDel(p', s', id') ) :-
    {opInc, opLoc} = xform( sDel(p', s', id'), sIns(p, str, id) )
    return {opLoc, opInc}

Local nDel VS Incoming txtOp=(cDel | cIns | sDel | sIns)

xform( nDel(id), txtOp(..., id') ) :-
    if (id != id') then return {nDel(id), txtOp(..., id')} // no collision
    // We don't apply the deletion of the note:
    return {no-op, txtOp(...)}

Local txtOp=(cDel | cIns | sDel | sIns) VS Incoming nDel

xform( txtOp(..., id), nDel(id') ) :-
    if (id != id') then return {txtOp(..., id), nDel(id')} // no collision
    // We cancel the deletion of the note:
    return {txtOp(..., id), no-op}

Local nDel VS Incoming nDel

xform( nDel(id), nDel(id') ) :-
    if (id != id') then return {nDel(id), nDel(id')} // no collision
    // Nothing else to do...
    return {no-op, no-op}

Local nDel VS Incoming nAdd

xform( nDel(id), nAdd(..., id') ) :-
    if (id != id') then return {nDel(id), nAdd(..., id')} // no collision
    // Since the note must have been added to be deleted, we keep it deleted:
    return {nDel(id), no-op}

Local nDel VS Incoming nDrag

xform( nDel(id), nDrag(x', y', id') ) :-
    if (id != id') then return {nDel(id), nDrag(x', y', id')} // no collision
    // We cancel the deletion of the note:
    return {no-op, nDrag(x', y', id')}

Local nAdd VS Incoming txtOp=(cDel | cIns | sDel | sIns)

xform( nAdd(..., id), txtOp(..., id') ) :-
    if (id != id') then return {nAdd(..., id), txtOp(..., id')} // no collision
    // The note must be already created to edit its content...
    return {no-op, txtOp(...)}

Local txtOp=(cDel | cIns | sDel | sIns) VS Incoming nAdd

xform( txtOp(..., id), nAdd(..., id') ) :-
    if (id != id') then return {txtOp(..., id), nAdd(..., id')} // no collision
    // The note must be already created to edit its content...
    return {txtOp(..., id), no-op}

Local nAdd VS Incoming nDel

xform( nAdd(..., id), nDel(id') ) :-
    if (id != id') then return {nAdd(..., id), nDel(id')} // no collision
    // The note must be already created to delete it...
    return {no-op, no-op}

Local nAdd VS Incoming nAdd

xform( nAdd(..., id), nAdd(..., id') ) :-
    if (id != id') then return {nAdd(..., id), nAdd(..., id')} // no collision
    // Nothing else to do...
    return {no-op, no-op}

Local nAdd VS Incoming nDrag

xform( nAdd(..., id), nDrag(x', y', id') ) :-
    if (id != id') then return {nAdd(..., id), nDrag(x', y', id')} // no collision
    // The note must be already created to edit its position...
    return {no-op, nDrag(x', y', id')}

Local nDrag VS Incoming txtOp=(cDel | cIns | sDel | sIns)

xform( nDrag(x', y', id), txtOp(..., id') ) :-
    return {nDrag(x', y', id), txtOp(..., id')} // no collision

Local txtOp=(cDel | cIns | sDel | sIns) VS Incoming nDrag

xform( txtOp(..., id), nDrag(x', y', id') ) :-
    return {txtOp(..., id), nDrag(x', y', id')} // no collision

Local nDrag VS Incoming nDel

xform( nDrag(x', y', id), nDel(id') ) :-
    if (id != id') then return {nDrag(x', y', id), nDel(id')} // no collision
        // We cancel the deletion of the note:
    return {nDrag(x', y', id), no-op}

Local nDrag VS Incoming nAdd

xform( nDrag(x', y', id), nAdd(..., id') ) :-
    if (id != id') then return {nDrag(x', y', id), nAdd(..., id')} // no collision
    // The note must be already created to edit its position...
    return {nDrag(x', y', id), no-op}

Local nDrag VS Incoming nDrag

xform( nDrag(x', y', id), nDrag(x', y', id') ) :-
    // TO DO