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

General idea:

1. Each your pattern can be transformed into regex using:

new RegExp('^' + pattern
  .replace(/[./]/g, '\\$&') // escape chars (list isn't full)
  .replace(/\*/g, '(.*)')   // replace asterisk with '(.*)' - any char(s)
+ '$')                      // match only full pattern

2. If one pattern match another one - you don't need both, because pattern with * include second one:

  if (pattern1.include('*') && pattern1.test(pattern2)) {
    // delete pattern2
  }

Simple realization can be found below (still need to optimize a bit).

Full code:

// Your initial array
const patterns = [
  '*.*.complete',
  '*.*.read',
  '*.*.update',
  '*.order.cancel',
  'accounting.*.delete',
  'accounting.*.update',
  'accounting.*.void',
  'accounting.account.*',
  'admin.user.read',
  'admin.user.update',
  'admin.format.delete',
]

// Build a new one with regexes
const withRegexes = patterns.map(pattern => {
  // Create a regex if pattern contain asterisk
  const regexp = pattern.includes('*') ? new RegExp('^' + pattern
    .replace(/[./]/g, '\\$&')
    .replace(/\*/g, '(.*)') 
  + '$') : null;
  return { pattern, regexp }; 
});

// Array of indexes of elements where it's pattern already matched by another pattern
let duplicateIndexes = [];
for (let i = 0; i < withRegexes.length - 1; i++) {
  for (let j = i + 1; j < withRegexes.length; j++) {
    if (withRegexes[i].regexp 
    && withRegexes[i].regexp.test(withRegexes[j].pattern)) {
      duplicateIndexes.push(j);
    }
  }
}

// Get unique indexes to delete in desc order
duplicateIndexes = [ ...new Set(duplicateIndexes) ].sort((a, b) => b - a);

// Clear up initial array
for (let index of duplicateIndexes) {
  patterns.splice(index, 1);
}

// New one 
console.log(patterns);