如何排除大量 glob 字符串中的冗余模式

Question

我已经研究这个算法好几天了，不知道如何找到最 suitable/easy/optimized 的解决方案。

这里我有一大串字符串如下

[
*.*.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

所有值都是一些通配符模式（实际上，它们是我系统的权限）

我想做的是删除冗余模式，例如：admin.json_api.read 是多余的，因为 *.*.read

有人可以给我任何 suggestion/approach 吗？

Answer 1

总体思路：

您的每个模式都可以使用以下方法转换为正则表达式：

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

如果一个模式与另一个模式相匹配 - 你不需要两者都需要，因为 * 的模式包括第二个：

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

下面是简单的实现（还需要优化一下）

完整代码：

// 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);

Answer 2

以下方法也考虑了不同的 glob 段长度。

因此，在第一步中，glob-array 被简化为一个或多个 segment-length 更好检查的特定数组 glob-items。

这样的项目具有例如其实际 glob-value.

的正则表达式特定模式

在最后的任务中，每个 segment-length 特定数组被单独清理成一个非冗余 glob-value 数组。

后者通过 1st 对每个数组按每个项目的 glob-value 降序排序（确保从更通用的 glob 值）和 2nd 通过拒绝其 glob-value 已经被更通用的 glob-value.

并且这种检测的基础是 glob-value 特定的正则表达式，其中星号通配符转换为具有相同含义的正则表达式模式......因此 '*.' 的任何 glob 值等于/[^.]+\./ 的正则表达式和任何终止 '.*' 等于 /\.[^.]+/.

的正则表达式

由于清理任务是通过 flatMap 完成的，最终结果又是一个平面阵列...

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; }

如何排除大量 glob 字符串中的冗余模式

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

javascript

regex

arrays

sanitization

glob