CODEWITHSUNDEEP
javascriptalgorithmobjectrecursion
user3711421
user3711421

Reputation: 1808

Filter nested object recursively

I have an object which looks like this:

const ROUTES = {
  ACCOUNT: {
    TO: '/account',
    RESTRICTIONS: {
      shouldBeLoggedIn: true,
    },
    ROUTES: {
      PROFILE: {
        TO: '/account/profile',
        RESTRICTIONS: {
          shouldBeLoggedIn: true,
        },
        ROUTES: {
          INFORMATION: {
            TO: '/account/profile/information',
            RESTRICTIONS: {
              shouldBeLoggedIn: true,
              permissions: ['EMAIL'],
            },
          },
          PASSWORD: {
            TO: '/account/profile/password',
            RESTRICTIONS: {
              shouldBeLoggedIn: true,
              permissions: ['EMAIL', 'ADMIN'],
            },
          },
        },
      },
      COLLECTIONS: {
        TO: '/account/collections',
        RESTRICTIONS: {
          shouldBeLoggedIn: true,
          permissions: ['ADMIN'],
        },
      },
      LIKES: {
        TO: '/account/likes',
        RESTRICTIONS: {
          shouldBeLoggedIn: true,
        },
      },
    },
  },
};

I want to create a function (getRoutes) which filters/reduces that object depending on the RESTRICTIONS passed in, all permissions must match.

function getRoutes(routes, restrictions){
   //...
}

const USER_RESTRICTIONS = {
    shouldBeLoggedIn: true,
    permissions: ['EMAIL'],
}

const allowedRoutes = getRoutes(ROUTES, USER_RESTRICTIONS)

allowedRoutes === {
  ACCOUNT: {
    TO: '/account',
    RESTRICTIONS: {
      shouldBeLoggedIn: true,
    },
    ROUTES: {
      PROFILE: {
        TO: '/account/profile',
        RESTRICTIONS: {
          shouldBeLoggedIn: true,
        },
        ROUTES: {
          INFORMATION: {
            TO: '/account/profile/information',
            RESTRICTIONS: {
              shouldBeLoggedIn: true,
              permissions: ['EMAIL'],
            },
          },
        },
      },
      LIKES: {
        TO: '/account/likes',
        RESTRICTIONS: {
          shouldBeLoggedIn: true,
        },
      },
    },
  },
} ? 'YAY' : 'NAY'

Upvotes: 0

Views: 107

Answers (3)

Scott Sauyet
Scott Sauyet

Reputation: 50797

My version is algorithmically no different from the one by user3297291. But the code design is a bit different.

I try to be more generic both in the object traversal and in the testing for matches. I hope that both would be reusable functions. The traversal takes a predicate and a property name for the children to recurse on (in your case 'ROUTES') and returns a function that filters the object supplied to it.

For the predicate, I pass the result of calling matchesRestrictions with something like your USER_RESTRICTIONS object. The thought is that there will likely be other restrictions possible. I assume that that if the value is a boolean, then the object must have the same boolean value for that key. If it is an array, then every item in it must appear in the array at that key. It's easy enough to add other types. This might be too generic, though; I really don't know what else might appear in USER_PERMMISSIONS or a RESTRICTIONS section.

This is the code I came up with:

const filterObj = (pred, children) => (obj) => 
  Object .fromEntries (
    Object .entries (obj)
      .filter ( ([k, v]) => pred (v))
      .map ( ([k, v]) => [
        k, 
        v [children]
          ? {
              ...v, 
              [children]: filterObj (pred, children) (v [children]) 
            }
          : v
        ]
      )
  )

const matchesRestrictions = (config) => ({RESTRICTIONS = {}}) =>
  Object .entries (RESTRICTIONS) .every (([key, val]) => 
    typeof val == 'boolean'
      ? config [key] === val
    : Array.isArray (val)
      ? val .every (v => (config [key] || []) .includes (v))
    : true // What else do you want to handle?                              
  )


const ROUTES = {ACCOUNT: {TO: "/account", RESTRICTIONS: {shouldBeLoggedIn: true}, ROUTES: {PROFILE: {TO: "/account/profile", RESTRICTIONS: {shouldBeLoggedIn: true}, ROUTES: {INFORMATION: {TO: "/account/profile/information", RESTRICTIONS: {shouldBeLoggedIn: true, permissions: ["EMAIL"]}}, PASSWORD: {TO: "/account/profile/password", RESTRICTIONS: {shouldBeLoggedIn: true, permissions: ["EMAIL", "ADMIN"]}}}}, COLLECTIONS: {TO: "/account/collections", RESTRICTIONS: {shouldBeLoggedIn: true, permissions: ["ADMIN"]}}, LIKES: {TO: "/account/likes", RESTRICTIONS: {shouldBeLoggedIn: true}}}}};
const USER_RESTRICTIONS = {shouldBeLoggedIn: true, permissions: ['EMAIL']}

console .log (
  filterObj (matchesRestrictions (USER_RESTRICTIONS), 'ROUTES') (ROUTES)
)

I don't know how generic filterObj ended up being. But I did test it with another object and a different path to the children:

const obj = {x: {foo: 1, val: 20, kids: {a: {foo: 2, val: 15, kids: {b: {foo: 3, val: 8}, c: {foo: 4, val: 17}, d: {foo: 5, val: 12}}}, e: {foo: 6, val: 5, kids: {f: {foo: 7, val: 23}, g: {foo: 8, val: 17}}}, h: {foo: 9, val: 11, kids: {i: {foo: 10, val: 3}, j: {foo: 11, val: 7}}}}}, y: {foo: 12, val: 8}, z: {foo: 13, val: 25, kids: {k: {foo: 14, val: 18, kids: {l: {foo: 5, val: 3}, m: {foo: 11, val: 7}}}}}}

const pred = ({val}) => val > 10

filterObj ( pred, 'kids') (obj)

getting this result:

{x: {foo: 1, kids: {a: {foo: 2, kids: {c: {foo: 4, val: 17}, d: {foo: 5, val: 12}}, val: 15}, h: {foo: 9, kids: {}, val: 11}}, val: 20}, z: {foo: 13, kids: {k: {foo: 14, kids: {}, val: 18}}, val: 25}}

so it's at least somewhat reusable.

Upvotes: 0

user3711421
user3711421

Reputation: 1808

I "solved" it like this:

export const checkLoggedIn = (shouldBeLoggedIn, isAuthenticated) => {
  if (!shouldBeLoggedIn) {
    return true;
  }

  return isAuthenticated;
};

function isRouteAllowed(route, restrictions) {
  const routeShouldBeLoggedIn = route.RESTRICTIONS.shouldBeLoggedIn;

  const passedLoggedInCheck = checkLoggedIn(
    routeShouldBeLoggedIn,
    restrictions.get('shouldBeLoggedIn')
  );

  if (!passedLoggedInCheck) {
    return false;
  } else {
    const routePermissions = route.RESTRICTIONS.permissions;

    if (!routePermissions) {
      return true;
    } else {
      const passedPermissions = routePermissions.every((permission) => {
        const restrictPermissions = restrictions.get('permissions');
        return (
          restrictPermissions &&
          restrictPermissions.find &&
          restrictPermissions.find(
            (userPermission) => userPermission === permission
          )
        );
      });

      return passedLoggedInCheck && passedPermissions;
    }
  }
}

function forEachRoute(
  routes,
  restrictions,
  routesToDelete = [],
  parentPath = []
) {
  const routeSize = Object.keys(routes).length - 1;

  Object.entries(routes).forEach(([key, route], index) => {
    const childRoutes = route.ROUTES;

    if (childRoutes) {
      parentPath.push(key);
      parentPath.push('ROUTES');
      forEachRoute(childRoutes, restrictions, routesToDelete, parentPath);
    } else {
      const allowed = isRouteAllowed(route, restrictions);
      if (!allowed) {
        const toAdd = [...parentPath, key];
        routesToDelete.push(toAdd);
      }
    }

    if (routeSize === index) {
      // new parent
      parentPath.pop();
      parentPath.pop();
    }
  });
}

const deletePropertyByPath = (object, path) => {
  let currentObject = object;
  let parts = path.split('.');
  const last = parts.pop();
  for (const part of parts) {
    currentObject = currentObject[part];
    if (!currentObject) {
      return;
    }
  }
  delete currentObject[last];
};

export function removeRestrictedRoutes(routes, restrictions) {
  let routesToDelete = [];

  forEachRoute(routes, restrictions, routesToDelete);

  let allowedRoutes = routes;

  routesToDelete.forEach((path) => {
    deletePropertyByPath(allowedRoutes, path.join('.'));
  });

  return allowedRoutes;
}

To be used like:

const USER_RESTRICTIONS = {
    shouldBeLoggedIn: true,
    permissions: ['EMAIL'],
}

const allowedRoutes = getRoutes(ROUTES, USER_RESTRICTIONS)

Not the most performant solution but it worked. @user3297291 solution seems much better so will refactor to that, just have to make it a bit more readable. I thought a solution with .reduce() would have been the best one, but maybe not possible.

Upvotes: 0

user3297291
user3297291

Reputation: 23382

First, without thinking about the recursive stuff, make sure you have your rule logic well defined.

I attempted to write a validation function using your required API, but don't think it's very readable. You might want to refactor it later. (Tip: write some unit tests!)

The example below takes a rule configuration object and a node from your tree. It returns a boolean indicating whether the node matches the requirements.

const includedIn = xs => x => xs.includes(x);

// RuleSet -> Path -> bool
const isAllowed = ({ shouldBeLoggedIn = false, permissions = [] }) => 
  ({ RESTRICTIONS }) => (
    (shouldBeLoggedIn ? RESTRICTIONS.shouldBeLoggedIn : true) &&
    RESTRICTIONS.permissions.every(includedIn(permissions))
  );

console.log(
  [ 
    { RESTRICTIONS: { shouldBeLoggedIn: true, permissions: [ ] } },
    { RESTRICTIONS: { shouldBeLoggedIn: true, permissions: [ 'EMAIL' ] } },
    { RESTRICTIONS: { shouldBeLoggedIn: true, permissions: [ 'EMAIL', 'ADMIN' ] } }
  ].map(
    isAllowed({ shouldBeLoggedIn: true, permissions: [ 'EMAIL'] })
  )
)

With this piece of code sorted, you can start thinking about how to traverse the tree. What you're basically defining is how to loop over each path and when to return.

If we just want to log, it's a matter of (1) checking ROUTES, and (2) looping over the entries inside the v.ROUTES object.

const traverse = obj => {
  Object
    .entries(obj)
    .forEach(
      ([k, v]) => {
        console.log(v.TO);
        if (v.ROUTES) traverse(v.ROUTES)         
      }
    )
};

traverse(getRoutes());

function getRoutes() { 
  return {
    ACCOUNT: {
      TO: '/account',
      RESTRICTIONS: {
        shouldBeLoggedIn: true,
      },
      ROUTES: {
        PROFILE: {
          TO: '/account/profile',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
          },
          ROUTES: {
            INFORMATION: {
              TO: '/account/profile/information',
              RESTRICTIONS: {
                shouldBeLoggedIn: true,
                permissions: ['EMAIL'],
              },
            },
            PASSWORD: {
              TO: '/account/profile/password',
              RESTRICTIONS: {
                shouldBeLoggedIn: true,
                permissions: ['EMAIL', 'ADMIN'],
              },
            },
          },
        },
        COLLECTIONS: {
          TO: '/account/collections',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
            permissions: ['ADMIN'],
          },
        },
        LIKES: {
          TO: '/account/likes',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
          },
        },
      },
    },
  };
};

Then comes the hardest part: creating a new tree structure.

I chose to take two steps:

  • First, we filter out the values that don't pass validation,
  • Secondly, we check if we need to worry about any child routes.

If there are child routes, we create a new path object that has a filtered ROUTES value.

const traverse = (obj, pred) => Object
  .fromEntries(
    Object
      .entries(obj)
      .filter(
        ([k, v]) => pred(v) // Get rid of the paths that don't match restrictions
      )
      .map(
        ([k, v]) => [
          k, v.ROUTES
            // If there are child paths, filter those as well (i.e. recurse)
            ? Object.assign({}, v, { ROUTES: traverse(v.ROUTES, pred) })
            : v
          ]
      )
  );


const includedIn = xs => x => xs.includes(x);
const isAllowed = ({ shouldBeLoggedIn = false, permissions = [] }) => 
  ({ RESTRICTIONS }) => (
    (shouldBeLoggedIn ? RESTRICTIONS.shouldBeLoggedIn : true) &&
    (RESTRICTIONS.permissions || []).every(includedIn(permissions))
  );
  
console.log(
  traverse(
    getRoutes(),
    isAllowed({ shouldBeLoggedIn: true, permissions: [ 'EMAIL'] })
  )
)

function getRoutes() { 
  return {
    ACCOUNT: {
      TO: '/account',
      RESTRICTIONS: {
        shouldBeLoggedIn: true,
      },
      ROUTES: {
        PROFILE: {
          TO: '/account/profile',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
          },
          ROUTES: {
            INFORMATION: {
              TO: '/account/profile/information',
              RESTRICTIONS: {
                shouldBeLoggedIn: true,
                permissions: ['EMAIL'],
              },
            },
            PASSWORD: {
              TO: '/account/profile/password',
              RESTRICTIONS: {
                shouldBeLoggedIn: true,
                permissions: ['EMAIL', 'ADMIN'],
              },
            },
          },
        },
        COLLECTIONS: {
          TO: '/account/collections',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
            permissions: ['ADMIN'],
          },
        },
        LIKES: {
          TO: '/account/likes',
          RESTRICTIONS: {
            shouldBeLoggedIn: true,
          },
        },
      },
    },
  };
};

I hope this example can get you started and enables you write your own/polished version. Let me know if I missed any requirements.

Upvotes: 2

Related Questions