// noinspection RedundantIfStatementJS
/**
* @author Maximilian Kallert <max@refinio.net>
* @author Eduard Reimer <eduard@refinio.net>
* @copyright REFINIO GmbH 2020
* @license CC-BY-NC-SA-2.5; portions MIT License
* @version 1.0.0
*/
import {convertValue} from '../object-to-microdata';
/**
* This module implements the CRDT ORRegister algorithm.
* @module
*/
import type {RecipeRule} from '../recipes';
import {createRandomString} from '../system/crypto-helpers';
import {isInteger, isObject, isString} from '../util/type-checks-basic';
import type {CRDTImplementation} from './CRDTImplementation';
/**
* The structure of one metadata list entry of this CRDT.
* timestamp - timestamp of the moment when the respective value was created
* uniqueId - a unique id generated when a new entry is added to the list
* value - the value added to the list
*/
interface AddListEntry {
timestamp: number;
uniqueId: string;
value: unknown;
}
interface RemoveListEntry {
uniqueId: string;
}
/**
* The structure of the metadata of this crdt.
*/
interface ORRegisterMetaData {
addList: AddListEntry[];
removeList: RemoveListEntry[];
}
/**
* Function that verifies that the metadata has the correct format by checking just the array types.
*
* @param {unknown} data - The data to check for compatibility.
* @returns {boolean}
*/
function isORRegisterMetadataFastCheck(data: unknown): data is ORRegisterMetaData {
if (!isObject(data)) {
return false;
}
if (!data || !Array.isArray(data.addList) || !Array.isArray(data.removeList)) {
return false;
}
return true;
}
/**
* Function that verifies that the metadata has the correct format by checking the array types
* and each array element type.
*
* @param {unknown} data - The data to check for compatibility.
* @returns {boolean}
*/
function isORRegisterMetadata(data: unknown): data is ORRegisterMetaData {
if (!isORRegisterMetadataFastCheck(data)) {
return false;
}
if (
!data.addList.every(
addEntry => isString(addEntry.uniqueId) && isInteger(addEntry.timestamp)
)
) {
return false;
}
if (!data.removeList.every(removeEntry => isString(removeEntry.uniqueId))) {
return false;
}
return true;
}
/**
* Implementation of the Observed-Remove Register (OR-Register)
*
* The OR-Register is based on the OR-Set.
*/
export class ORRegister implements CRDTImplementation {
generateRecipeRules(_rule: RecipeRule, path: string): RecipeRule[] {
return [
{
itemprop: 'addList',
itemtype: {
type: 'array',
item: {
type: 'object',
rules: [
{
itemprop: 'uniqueId',
itemtype: {type: 'string'}
},
{
itemprop: 'timestamp',
itemtype: {type: 'number'}
},
{
itemprop: 'value',
inheritFrom: {rule: path, extract: 'CollectionItemType'}
}
]
}
}
},
{
itemprop: 'removeList',
itemtype: {
type: 'array',
item: {
type: 'object',
rules: [
{
itemprop: 'uniqueId',
itemtype: {type: 'string'}
}
]
}
}
}
];
}
async generateMetaData(
dataOld: unknown,
dataNew: unknown,
metadataOld: unknown,
rule: Readonly<RecipeRule>
): Promise<ORRegisterMetaData> {
if (metadataOld === undefined || dataOld === undefined) {
return {
addList: [
{uniqueId: await createRandomString(), timestamp: Date.now(), value: dataNew}
],
removeList: []
};
}
if (!isORRegisterMetadata(metadataOld)) {
throw new Error(`Old metadata has invalid format: ${metadataOld}`);
}
// Check if data has changed, if not then do nothing
const serializedOld = convertValue(rule, dataOld);
const serializedNew = convertValue(rule, dataNew);
if (serializedOld === serializedNew) {
return metadataOld;
}
// Update remove list: Add all elements of the old addList to the remove list.
const removeList = [
...new Set([
...metadataOld.removeList.map(entry => entry.uniqueId),
...metadataOld.addList.map(entry => entry.uniqueId)
])
].map(entry => ({uniqueId: entry}));
// Update add list: Push a new element to the add list
const addList = metadataOld.addList.concat({
uniqueId: await createRandomString(),
timestamp: Date.now(),
value: dataNew
});
return {addList, removeList};
}
async mergeMetaData(
objLatestVersion: unknown,
metadataLatestVersion: unknown,
objToMerge: unknown,
metadataToMerge: unknown,
rule: Readonly<RecipeRule>
): Promise<{metadata: ORRegisterMetaData; data: unknown}> {
if (metadataLatestVersion === undefined) {
// eslint-disable-next-line no-param-reassign
metadataLatestVersion = {addList: [], removeList: []};
}
if (!isORRegisterMetadata(metadataLatestVersion)) {
throw new Error(`Old medatata has invalid format: ${metadataLatestVersion}`);
}
if (!isORRegisterMetadata(metadataToMerge)) {
throw new Error(`Merge metadata has invalid format: ${metadataToMerge}`);
}
// If the latest version is non-existent, then just use the version that shall be merged
if (objLatestVersion === undefined) {
return {
data: objToMerge,
metadata: metadataToMerge
};
}
const mergedMetadataAddList = ORRegister.mergeAndDeduplicateLists(
metadataLatestVersion.addList,
metadataToMerge.addList
);
const mergedMetadataRemoveList = ORRegister.mergeAndDeduplicateLists(
metadataLatestVersion.removeList,
metadataToMerge.removeList
);
const derivedValue = ORRegister.caculateValueFromMetadata(
{
addList: mergedMetadataAddList,
removeList: mergedMetadataRemoveList
},
rule
);
return {
metadata: {
addList: mergedMetadataAddList,
removeList: mergedMetadataRemoveList
},
data: derivedValue
};
}
/**
* Merge and filter the duplicates based on unique ids.
*
* Note that the duplicate check only happens between the two lists. If list1 already has
* duplicates the output list will also have those duplicates.
*
* @param {AddListEntry[]} list1
* @param {AddListEntry[]} list2
* @returns {AddListEntry[]}
* @private
*/
private static mergeAndDeduplicateLists<T extends AddListEntry | RemoveListEntry>(
list1: T[],
list2: T[]
): T[] {
const mergedList = [...list1];
for (const entry2 of list2) {
if (list1.findIndex(entry1 => entry1.uniqueId === entry2.uniqueId) === -1) {
mergedList.push(entry2);
}
}
return mergedList;
}
/**
* Calculate the value based on metadata.
*
* @param {ORRegisterMetaData} metaData
* @param {RecipeRule} rule
* @returns {AddListEntry}
* @private
*/
private static caculateValueFromMetadata(
metaData: ORRegisterMetaData,
rule: RecipeRule
): unknown {
const removeListIds = new Set(metaData.removeList.map(entry => entry.uniqueId));
const activeElements = metaData.addList.filter(entry => !removeListIds.has(entry.uniqueId));
if (activeElements.length === 0) {
throw new Error(
'The metadata has no elements left. At least one element is mandatory.'
);
}
let maxElement = activeElements[0];
for (const activeElement of activeElements.slice(1)) {
if (activeElement.timestamp > maxElement.timestamp) {
maxElement = activeElement;
continue;
} else if (activeElement.timestamp < maxElement.timestamp) {
continue;
}
if (activeElement.uniqueId > maxElement.uniqueId) {
maxElement = activeElement;
continue;
} else if (activeElement.uniqueId < maxElement.uniqueId) {
continue;
}
const serializedNew = convertValue(rule, activeElement.value);
const serializedMin = convertValue(rule, maxElement.value);
if (serializedNew > serializedMin) {
maxElement = activeElement;
}
}
return maxElement.value;
}
}