I have a client application consuming data from an external API based on a configuration during startup.
Since calculating the necessary data is not easy for me, I tried to fake the implementation and calculate it locally for now.
There are many WorkItems linked to each other and the configuration only knows about the relations to consider.
Some explanations:
Workitem
A workitem has a unique id and a type
e.g.
{
id: 1,
type: "person"
}
so you know that Workitem 1 is of type person
Linkrole
A linkrole is a composite key of three keys
e.g.
{
parentWorkItemType: "person",
childWorkItemType: "house",
name: "owns",
}
which represents Person owns House
Links
The backend knows about the relations, a link between workitems might look like
{
/* each link is unique */
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "house",
name: "owns",
},
parentId: 1,
childId: 2
}
so you know that Person 1 owns House 2
Fake prerequisites:
Fake backend
I created some fake data for my calculations. The file backend.js represents the backend / database
// backend.js
export const workItems = [{
id: 1,
type: "car"
}, {
id: 2,
type: "car"
}, {
id: 3,
type: "bird"
}, {
id: 4,
type: "bird"
}, {
id: 5,
type: "bird"
}, {
id: 6,
type: "invalid"
}, {
id: 7,
type: "house"
}, {
id: 8,
type: "house"
}, {
id: 9,
type: "house",
}, {
id: 10,
type: "person",
}];
export const workItemLinks = [{
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
},
parentId: 1,
childId: 3
}, {
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
},
parentId: 1,
childId: 4
}, {
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
},
parentId: 3,
childId: 7
}, {
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
},
parentId: 3,
childId: 8
}, {
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "car",
name: "owns",
},
parentId: 10,
childId: 1
}, {
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "car",
name: "references",
},
parentId: 1,
childId: 2
}];
Fake API
I created some methods inside the file api.js to fake an API asking the backend for data.
Important sidenote: These methods just help me to find the data I need. I can add more "helpers" if needed (In the real world I can ask to add more API endpoints) so everything can be queried. Please feel free to modify the "Fake API".
// api.js
import { workItems, workItemLinks } from "./backend.js";
export function getWorkItemsByType(workItemType) {
return workItems.filter(workItem => workItem.type === workItemType);
}
export function getWorkItemsByIds(workItemIds) {
return workItems.filter(workItem => workItemIds.some(workItemId => workItemId === workItem.id));
}
export function getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideIds, leftSideIsParentSide) {
return workItemLinks.filter(workItemLink => {
// Pseudo equality check
if (workItemLink.linkRole.parentWorkItemType === linkRole.parentWorkItemType &&
workItemLink.linkRole.childWorkItemType === linkRole.childWorkItemType &&
workItemLink.linkRole.name === linkRole.name) {
const leftSideIdInLink = leftSideIsParentSide ? workItemLink.parentId : workItemLink.childId;
// Return this link if it matches with the left side id ( you're looking for the right side id )
return leftSideIds.some(leftSideId => leftSideId === leftSideIdInLink);
}
return false;
});
}
Fake configuration
I created definitions inside configuration.js to start the calculations based on those
// configuration.js
export const definitions = [
{ // fetch linked birds from every root car
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "bird",
name: "isChildOf",
}
},
{ // !! Root Element !! Fetch work items based on type
workItemType: "car",
isRootWorkItem: true
},
{ // fetch linked houses from every bird ( car - bird - house )
linkRole: {
parentWorkItemType: "bird",
childWorkItemType: "house",
name: "with",
}
},
{ // fetch every person from every car ( person - car )
linkRole: {
parentWorkItemType: "person",
childWorkItemType: "car",
name: "owns",
}
},
{ // Self reference, fetch linked cars from every root car
linkRole: {
parentWorkItemType: "car",
childWorkItemType: "car",
name: "references",
}
},
];
Problem to solve:
I am looking for a performant way to fetch every related link and workitem from the backend based on the chain of relations starting with each root item.
Expected output based on the configuration:
export const workItems = [{
id: 1,
type: "car"
}, {
id: 2,
type: "car"
}, {
id: 3,
type: "bird"
}, {
id: 4,
type: "bird"
}, /* no car is linked to bird 5, no links for invalid 6 */ {
id: 7,
type: "house"
}, {
id: 8,
type: "house"
}, /* no bird is linked to house 9 */ {
id: 10,
type: "person",
}];
/* based on the configuration every workItemLink from the backend got fetched */
My first implementation approach:
import { inspect } from "util";
import { getWorkItemsByType, getWorkItemsByIds, getWorkItemLinksByLinkRoleAndLeftSideIds } from "./api.js";
import { definitions } from "./configuration.js";
// Find the root definition
const { workItemType: rootWorkItemType } = definitions.find(definition => definition.isRootWorkItem);
// Fetch all the root workitems and initialize the store holding unique workitems
const workItems = getWorkItemsByType(rootWorkItemType); // will hold car 1 and car 2
const initialWorkItemIds = workItems.map(workItem => workItem.id);
const workItemIdsToLoad = []; // try to read all missing ids from fetched links and fetch all the workitems at once later on
const workItemLinks = []; // global store for links
const definitionsToTraverse = definitions.filter(definition => definition.linkRole !== undefined); // do not consider the root definition
run(initialWorkItemIds, rootWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);
const missingWorkItemIdsToLoad = workItemIdsToLoad.filter(workItemIdToLoad => !rootWorkItemIds.some(rootWorkItemId => rootWorkItemId === workItemIdToLoad)); // filter out all the existing root item ids
const workItemsToAdd = getWorkItemsByIds(missingWorkItemIdsToLoad); // fetch all the missing workitems at once
workItems.push(...workItemsToAdd); // add them to the global store
console.log(inspect({
workItems,
workItemLinks
}, false, null, true))
function run(leftSideWorkItemIds, leftSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks) {
/*
consider all the defitions from "definitionsToTraverse" directly related to "leftSideWorkItemType"
remove them from "definitionsToTraverse" to prevent endless loops
loop backwards so splice won't struggle with the indices
*/
for (let definitionIndex = definitionsToTraverse.length - 1; definitionIndex >= 0; definitionIndex--) {
const currentDefinition = definitionsToTraverse[definitionIndex];
const { linkRole } = currentDefinition;
const { parentWorkItemType, childWorkItemType } = linkRole;
const leftSideWorkItemTypeIsParent = parentWorkItemType === leftSideWorkItemType;
const leftSideWorkItemTypeIsChild = childWorkItemType === leftSideWorkItemType;
// Check the direct relation
if (leftSideWorkItemTypeIsParent || leftSideWorkItemTypeIsChild) {
// Remove the inspected definition
definitionsToTraverse.splice(definitionIndex, 1);
const relatedWorkItemLinks = getWorkItemLinksByLinkRoleAndLeftSideIds(linkRole, leftSideWorkItemIds, leftSideWorkItemTypeIsParent);
// store all the right side workitem IDs for the next run
const rightSideWorkItemIds = [];
for (let relatedWorkItemLinkIndex = 0; relatedWorkItemLinkIndex < relatedWorkItemLinks.length; relatedWorkItemLinkIndex++) {
const relatedWorkItemLink = relatedWorkItemLinks[relatedWorkItemLinkIndex];
// Process the link if not processed yet
if (!workItemLinks.some(workItemLink => /* !!! pseudo equality check !!! */
workItemLink.linkRole.parentWorkItemType === relatedWorkItemLink.linkRole.parentWorkItemType &&
workItemLink.linkRole.childWorkItemType === relatedWorkItemLink.linkRole.childWorkItemType &&
workItemLink.linkRole.name === relatedWorkItemLink.linkRole.name &&
workItemLink.parentId === relatedWorkItemLink.parentId &&
workItemLink.childId === relatedWorkItemLink.childId)) {
// Push the link to the store
workItemLinks.push(relatedWorkItemLink);
// Get the right side id from the link
const rightSideWorkItemId = leftSideWorkItemTypeIsParent ? relatedWorkItemLink.childId : relatedWorkItemLink.parentId;
rightSideWorkItemIds.push(rightSideWorkItemId);
// Push the id to the store if it doesn't exist
if (!workItemIdsToLoad.some(workItemIdToLoad => workItemIdToLoad === rightSideWorkItemId)) {
workItemIdsToLoad.push(rightSideWorkItemId);
}
}
}
// Find the opposite workitem type of the current definition
const rightSideWorkItemType = leftSideWorkItemTypeIsParent ? childWorkItemType : parentWorkItemType;
// Run again but use this definition as the previous one
run(rightSideWorkItemIds, rightSideWorkItemType, definitionsToTraverse, workItemIdsToLoad, workItemLinks);
}
}
}
The problem is that my approach crashes because the backwards loop even runs if definitionsToTraverse is empty. And I'm mutating the arrays from the parameters directly, I think I shouldn't do that.
So any help would be appreciated a lot!