javascript - 递归函数以简化javascript中的表达式

我正在编写一个使用递归简化给定表达式的函数。

例如，一个表达式

{AnyOf: ["scope1", "scope2", "scope*"]}

可以简化为

{AnyOf: ["scope*"]}

使用实用程序功能scopeCompare()首先对范围数组进行排序，然后使用normalizeScopeSet()从范围数组中删除任何存在的重复项或不需要的范围。

我已经写了一个函数，可以简化表达式到这个级别：

{AnyOf: ["scope1", "scope2", "scope*"]}

但是，如果我有这样的表达：

{AnyOf: ["scope1", {AllOf: ["scope2a", "scope2b, "scope2*", "scope3"]}]}

当前功能不起作用。上面的表达式可以简化为：

{AnyOf: ["scope1", {AllOf:["scope2*", "scope3"]}]}

这是我现在的功能：

const { normalizeScopeSet, scopeCompare } = require("./normalize");

exports.simplifyScopeExpression = scopeExpression => {
  if (isScope(scopeExpression)) {
    return scopeExpression;
  } else if (isAnyOf(scopeExpression)) {
    return scopeExpression;
  } else if (isAllOf(scopeExpression)) {
    return scopeExpression;
  }
};

const isScope = scopeExpression => {
  let exp = scopeExpression;
  if (typeof exp === "string") {
    return true;
  } else if (Object.keys(exp) === "AnyOf") {
    isAnyOf(scopeExpression);
  }
  else if(Object.keys(exp) === 'AllOf'){
    isAllOf(scopeExpression);
  }
};

const isAnyOf = scopeExpression => {
  let exp = scopeExpression;
  Object.keys(exp).forEach(item => {
    let expression = exp[item].sort(scopeCompare);
    exp[item] = normalizeScopeSet(expression);
  });
  return scopeExpression;
};

const isAllOf = scopeExpression => {
  let exp = scopeExpression;
  Object.keys(exp).forEach(item => {
    let expression = exp[item].sort(scopeCompare);
    exp[item] = normalizeScopeSet(expression);
  });
  return scopeExpression;
};

我想修改此函数，以便在传递如下所示的表达式时，可以得到预期的简化表达式。


{AllOf: [{AllOf: ["scope1", "scope2"]}, {AllOf: ["scope2", "scope3"]}]}应简化为{AllOf: ["scope1", "scope2", "scope3"]}。
{AllOf: [{AllOf: ["scope1", "scope2"]}, "scope2", "scope3"]}应简化为{AllOf: ["scope1", "scope2", "scope3"]}。
{AllOf: ["scope0", {AllOf: ["scope1", {AllOf: ["scope2", {AllOf: ["scope3, {AllOf: ["scope4", "scope5"]}]}]}]}]}应简化为{AllOf: ["scope0", "scope1", "scope2", "scope3", "scope4", "scope5"]}


笔记：

scopeCompare函数对范围进行排序，使得以*结尾的范围位于具有相同前缀的其他任何内容之前。例如，a *在a和ax之前。

normalizeScopeSet函数将规范作用域集。但是，它要求其输入已经使用scopeCompare进行了排序。

例如，要对范围数组进行排序：

let scope = {AnyOf: ["scope1", "scope2", "scope*"]}
Object.keys(scope).forEach(item => {
let expression = exp[item].sort(scopeCompare);
    exp[item] = normalizeScopeSet(expression);
})

这给出了输出

 {AnyOf: ["scope*"]}

最佳答案

那是一个有趣的挑战。我设法（但我想）以某种不同的方式使某些工作正常进行。尽管与您有些相似。

// compress an array of patterns and strings
// remove duplicates *AND* strings matching any patterns
// compress(["scope10", "scope11", "scope11", "scope1*", "scope2", "scope2*", "scope2a"])
// => ["scope1*", "scope2*"]
//
// TODO: patterns could be optimised as well!
const compress = xs =>
  Array.of(xs)
    .map(xs => xs.filter((x, i, xs) => xs.indexOf(x) === i))
    .map(xs =>
      xs.reduce(([l, r], x) =>
        x.endsWith('*')
          ? [ l.concat(x.slice(0, -1))
            , r
            ]
          : [ l
            , r.concat(x)
            ],
        [[], []]))
    .map(([l, r]) =>
      [ ...l.map(x => x + '*')
      , ...r.filter(x => !l.some(y => x.startsWith(y)))
      ])
    .pop();

// flatten expressions that belong to the same "namespace"
// flatten_expression("AllOf", ["scope1", {AllOf: ["scope2", "scope3"]}, {AnyOf: ["scope10*", "scope20*"]}])
//=> ["scope1", "scope2", "scope3", {AnyOf: ["scope10*", "scope20*"]}]
const flatten_expression = (key, exprs) =>
  exprs.flatMap(expr =>
    typeof expr === 'string' || expr[key] === undefined
      ? expr
      : flatten_expression(key, expr[key]));

// Given an array of expressions
// compress all strings and simplify the rest
// reduce_expression(["scope1", "scope1*", {AnyOf: ["scope22", "scope2*", "scope3"]}])
// => ["scope1*", {AnyOf: ["scope2*", "scope3"]}]
const reduce_expression = xs =>
  Array.of(xs)
    .map(xs =>
      xs.reduce(([l, r], x) =>
        typeof x === 'string'
          ? [ l.concat(x)
            , r
            ]
          : [ l
            , r.concat(x)
            ],
        [[], []]))
    .map(([l, r]) =>
      [ ...compress(l)
      , ...r.map(simplify_expression)
      ])
    .pop();

// Simplify an entire object of expressions
const simplify_expression = o =>
  Array.of(o)
    .map(xs => Object.entries(xs))
    .map(xs => xs.map(([k, v]) => [k, flatten_expression(k, v)]))
    .map(xs => xs.map(([k, v]) => [k, reduce_expression(v)]))
    .map(xs => Object.fromEntries(xs))
    .pop();

console.log(
  simplify_expression({AnyOf: ["scope1", "scope2", "scope*"]})
)

console.log(
  simplify_expression({AnyOf: ["scope1", {AllOf: ["scope2a", "scope2b", "scope2*", "scope3"]}]})
)

console.log(
  simplify_expression({AllOf: [{AllOf: ["scope1", "scope2"]}, {AllOf: ["scope2", "scope3"]}]})
)

console.log(
  simplify_expression({AllOf: [{AllOf: ["scope1", "scope2"]}, "scope2", "scope3"]})
)

console.log(
  simplify_expression({AllOf: ["scope0", {AllOf: ["scope1", {AllOf: ["scope2", {AllOf: ["scope3", {AllOf: ["scope4", "scope5"]}]}]}]}]})
)