// 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
*/
/**
* This module implements the CRDT ORSet algorithm.
* @module
*/
import {convertValue} from '../object-to-microdata';
import type {RecipeRule} from '../recipes';
import {createRandomString} from '../system/crypto-helpers';
import {constructItemRuleFromListRule} from '../util/recipe-checks';
import {isListItemType, ruleHasItemType} from '../util/type-checks';
import {isObject, isString} from '../util/type-checks-basic';
import type {CRDTImplementation} from './CRDTImplementation';
/**
* The structure of one metadata list entry of this CRDT.
* uniqueId - a unique id generated when a new entry is added to the list
* value - the value added to the list
*/
interface MetaListEntry {
uniqueId: string;
value: unknown;
}
/**
* The structure of the metadata of this crdt.
*/
interface ORSetMetaData {
addList: MetaListEntry[];
removeList: MetaListEntry[];
}
/**
* Function that verifies that the metadata has the correct format. It checks the array
* types, not each element in the array.
*
* @param {any} data - The data to check for compatibility.
* @returns {boolean}
*/
function isORSetMetadataFastCheck(data: unknown): data is ORSetMetaData {
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. It checks the array types
* and every element in the array.
* @param {unknown} data - The data to check for compatibility.
* @returns {boolean}
*/
function isORSetMetadata(data: unknown): data is ORSetMetaData {
if (!isORSetMetadataFastCheck(data)) {
return false;
}
if (!data.addList.every(addEntry => isString(addEntry.uniqueId))) {
return false;
}
if (!data.removeList.every(removeEntry => isString(removeEntry.uniqueId))) {
return false;
}
return true;
}
/**
* Implementation of the Observed-Remove Set (OR-Set)
*
* See paper:
* A comprehensive study of Convergent and Commutative Replicated Data Types
* Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski
* p. 26, Section 3.3.5
* https://hal.inria.fr/inria-00555588/document
*/
export class ORSet implements CRDTImplementation {
generateRecipeRules(rule: RecipeRule, path: string): RecipeRule[] {
if (ruleHasItemType(rule) && !isListItemType(rule.itemtype)) {
throw new Error(
`generateRecipeRules: You cannot use the ORSet implementation if the data type' +
' is not a set: ${rule}`
);
}
return [
{
itemprop: 'addList',
itemtype: {
type: 'array',
item: {
type: 'object',
rules: [
{
itemprop: 'uniqueId',
itemtype: {type: 'string'}
},
{
itemprop: 'value',
inheritFrom: {rule: path, extract: 'CollectionItemType'}
}
]
}
}
},
{
itemprop: 'removeList',
itemtype: {
type: 'array',
item: {
type: 'object',
rules: [
{
itemprop: 'uniqueId',
itemtype: {type: 'string'}
},
{
itemprop: 'value',
inheritFrom: {rule: path, extract: 'CollectionItemType'}
}
]
}
}
}
];
}
async generateMetaData(
dataOld: unknown = new Set(),
dataNew: unknown,
metadataOld: unknown = {addList: [], removeList: []},
rule: RecipeRule
): Promise<ORSetMetaData> {
// #### STEP 1: Sanity checks and rule adaption ####
if (ruleHasItemType(rule) && !isListItemType(rule.itemtype)) {
throw new Error(
`generateMetaData: You cannot use the ORSet implementation if the data type is' +
' not a set: ${rule}`
);
}
if (!isORSetMetadata(metadataOld)) {
throw new Error(`Old medatata has invalid format: ${metadataOld}`);
}
if (!(dataOld instanceof Set) && dataOld !== undefined) {
throw new Error(`The ORSet needs dataOld to be of type Set or undefined: ${dataOld}`);
}
if (!(dataNew instanceof Set)) {
throw new Error(`The ORSet needs dataNew to be of type Set: ${dataNew}`);
}
const ruleNoList = constructItemRuleFromListRule(rule);
// #### STEP 2: Convert to 'string content' -> 'jsobject content' ####
// Leads to: [[string, content], ...]
const dataOldSerialized: Array<[string, unknown]> = [];
if (dataOld !== undefined) {
for (const elem of dataOld.values()) {
dataOldSerialized.push([convertValue(ruleNoList, elem), elem]);
}
}
const dataNewSerialized: Array<[string, unknown]> = [];
for (const elem of dataNew.values()) {
dataNewSerialized.push([convertValue(ruleNoList, elem), elem]);
}
// Leads to a map: string -> content
const dataOldMap = new Map(dataOldSerialized);
const dataNewMap = new Map(dataNewSerialized);
// #### STEP 3: Find elements that were added / removed and add this information ####
// Fill the output maps based on the calculated differences
const metadataNew: ORSetMetaData = {
addList: [...metadataOld.addList],
removeList: [...metadataOld.removeList]
};
// Add added elements to addList
const dataNewSerializedFiltered = dataNewSerialized.filter(
elem => !dataOldMap.has(elem[0])
);
const newAddListEntries = await Promise.all(
dataNewSerializedFiltered.map(async addedElement => {
return {
uniqueId: await createRandomString(),
value: addedElement[1]
};
})
);
metadataNew.addList = metadataNew.addList.concat(newAddListEntries);
const serializedDataToBeDeleted = dataOldSerialized.filter(
elem => !dataNewMap.has(elem[0])
);
serializedDataToBeDeleted.forEach(deletedElement => {
// Create removeList entry for each known uniqueId entry in the addList for the
// deleted value
const metaListEntriesToBeDeleted = metadataNew.addList.filter(
metaListEntry => convertValue(ruleNoList, metaListEntry.value) === deletedElement[0]
);
const removeListEntries = metaListEntriesToBeDeleted.map(removeUniqueId => {
return {
uniqueId: removeUniqueId.uniqueId,
value: deletedElement[1]
};
});
metadataNew.removeList = metadataNew.removeList.concat(removeListEntries);
});
return metadataNew;
}
async mergeMetaData(
objLatestVersion: unknown,
metadataLatestVersion: unknown,
objToMerge: unknown,
metadataToMerge: unknown,
rule: Readonly<RecipeRule>
): Promise<{metadata: ORSetMetaData; data: unknown}> {
// #### STEP 1: Sanity checks and rule adaption ####
if (ruleHasItemType(rule) && !isListItemType(rule.itemtype)) {
throw new Error(
`mergeMetaData: You cannot use the ORSet implementation if the data type is not' +
' a set: ${rule}`
);
}
// If data old is undefined it means, that we don't have any data in it, it is
// equivalent to an empty array.
if (objLatestVersion === undefined) {
// eslint-disable-next-line no-param-reassign
objLatestVersion = new Set();
if (metadataLatestVersion === undefined) {
// eslint-disable-next-line no-param-reassign
metadataLatestVersion = {
addList: [],
removeList: []
};
}
}
if (!isORSetMetadata(metadataLatestVersion)) {
throw new Error(`Old medatata has invalid format: ${metadataLatestVersion}`);
}
if (!isORSetMetadata(metadataToMerge)) {
throw new Error(`Merge metadata has invalid format: ${metadataToMerge}`);
}
if (!(objLatestVersion instanceof Set)) {
throw new Error(
`The ORSet needs objLatestVersion to be of type Set or undefined: ${objLatestVersion}`
);
}
if (!(objToMerge instanceof Set)) {
throw new Error(`The ORSet needs objToMerge to be of type Set: ${objToMerge}`);
}
// #### STEP 2: Calculate new metadata by merging the old ones ####
const mergedAddList = ORSet.mergeFilterList(
metadataLatestVersion.addList,
metadataToMerge.addList
);
const mergedRemoveList = ORSet.mergeFilterList(
metadataLatestVersion.removeList,
metadataToMerge.removeList
);
// #### STEP 3: Generate the new data object ####
const aliveElements = ORSet.computeAliveElements(mergedAddList, mergedRemoveList);
// #### STEP 4: return metadata and data ####
return {
metadata: {
addList: mergedAddList,
removeList: mergedRemoveList
},
data: new Set(aliveElements)
};
}
/**
* Merge and filter the duplicates based on unique ids.
* @param {MetaListEntry[]} list1
* @param {MetaListEntry[]} list2
* @returns {MetaListEntry[]}
* @private
*/
private static mergeFilterList(
list1: MetaListEntry[],
list2: MetaListEntry[]
): MetaListEntry[] {
const mergedList = [...list1, ...list2];
// filter duplicates based on unique id
return mergedList.filter((elem: MetaListEntry, index: number, self: MetaListEntry[]) => {
return (
index === self.findIndex(metaListEntry => metaListEntry.uniqueId === elem.uniqueId)
);
});
}
/**
* Calculate the elements of the list.
*
* @param {MetaListEntry[]} addList
* @param {MetaListEntry[]} removeList
* @returns {unknown[]}
* @private
*/
private static computeAliveElements(
addList: MetaListEntry[],
removeList: MetaListEntry[]
): unknown[] {
// This maps the hash to elements.
const map = new Map<string, MetaListEntry>();
// Fill the map with all added values.
for (const elem of addList) {
map.set(elem.uniqueId, {
uniqueId: elem.uniqueId,
value: elem.value
});
}
// Delete the removed elements
for (const removedElement of removeList) {
const latestAdd = map.get(removedElement.uniqueId);
if (latestAdd !== undefined) {
map.delete(removedElement.uniqueId);
}
}
return [...map.values()].map(e => e.value);
}
}