How to exclude redundant patterns among a large array of glob string

Question

I have been working on this algorithm for days, and no idea how to figure out the most suitable/easy/optimized solution.

Here I have a large array of string as the followings

[
*.*.complete
*.*.read
*.*.update
*.order.cancel
accounting.*.delete
accounting.*.update
accounting.*.void
accounting.account.*
admin.user.read
admin.user.update
admin.format.delete
...
]

// the array may be in random order

all the values are in some wildcard patterns (in fact, they are the permissions for my system)

what i want to do is to remove redundant patterns, for example: admin.json_api.read is redundant due to *.*.read

can someone give me any suggestion/approach?

Answer 1

The following approach takes different glob segment length's into account as well.

Thus in a first step the glob-array is reduced into one or more segment-length specific arrays of better inspectable glob-items.

Such an item features e.g. a regex specific pattern of its actual glob-value.

Within a final tasks each segment-length specific array gets sanitized separately into an array of non redundant glob-values.

The latter gets achieved by 1st sorting each array descending by each item's glob-value (which assures a sorting from the more to the less generic glob values) and 2nd by rejecting each item where its glob-value gets covered already by a more generic glob-value.

And the base of such a detection is the glob-value specific regex where the asterisk wild card translates into a regex pattern with the same meaning ... thus any glob value of '*.' equals a regex of /[^.]+\./ and any terminating '.*' equals a regex of /\.[^.]+/.

Since the sanitizing task is done via flatMap, the end result is a flat array again ...

function createGlobInspectionItem(glob) {
  const segments = glob.split('.');
  return {
    value: glob,
    pattern: glob
      .replace((/\*\./g), '[^.]+.')
      .replace((/\.\*$/), '.[^.]+')
      .replace((/(?<!\^)\./g), '\\.'),
    segmentCount: segments.length,
  };
}
function collectGlobInspectionItems({ index, result }, glob) {
  const globItem = createGlobInspectionItem(glob);
  const groupKey = globItem.segmentCount;

  let groupList = index[groupKey];
  if (!groupList) {

    groupList = index[groupKey] = [];
    result.push(groupList);
  }
  groupList.push(globItem);

  return { index, result };
}

function createSanitizedGlobList(globItemList) {
  const result = [];
  let globItem;

  globItemList.sort(({ value: aValue }, { value: bValue }) =>
    (aValue > bValue && -1) || (aValue < bValue && 1) || 0
  );
  while (globItem = globItemList.pop()) {

    globItemList = globItemList.filter(({ value }) =>
      !RegExp(globItem.pattern).test(value)
    );
    result.push(globItem);
  }
  return result.map(({ value }) => value);
}
const sampleData = [

  // 3 segments

  '*.*.complete',
  '*.*.read',
  '*.*.update',
  '*.order.cancel',
  'accounting.*.delete',
  'accounting.*.update',
  'accounting.*.void',
  'accounting.account.user',
  'accounting.account.*',
  'accounting.account.admin',
  'admin.user.read',
  'admin.user.update',
  'admin.format.delete',

  // 2 segments

  '*.read',
  '*.update',
  'user.read',
  'user.update',
  'format.delete',
  'format.account',
];

console.log(
  '... intermediata inspection result grouped by section length ...',
  sampleData
    .reduce(collectGlobInspectionItems, { index: {}, result: [] })
    .result
);
console.log(
  '... final sanitized and flattened glob array ...',
  sampleData
    .reduce(collectGlobInspectionItems, { index: {}, result: [] })
    .result
    .flatMap(createSanitizedGlobList)
);

.as-console-wrapper { min-height: 100%!important; top: 0; }