javascript - 如何构建运行和查找循环(​​冲突)的方法链

标签 javascript recursion graph-theory

我所拥有的：有一些json配置（描述性模板），以不同顺序存储的方法，其外观如下：

[   
  {
    "name" : "methodA", //methodA output arguments are methodB input arguments
    "inArgs" : "[arg1, arg2]",
    "returnArgs" : "[arg3, arg4]"
  },
  {
    "name" : "methodB", //methodB output arguments are methodZ input arguments
    "inArgs" : "[arg3, arg5]",
    "returnArgs" : "[arg6, arg7]"
  },
{
    "name" : "methodС",
    "inArgs" : "[arg1]",
    "returnArgs" : "[arg10]"
  },
    a bunch of other methods whose input arguments are not part of methodA or methodB
  .....
  {
    "name" : "methodZ",
    "inArgs" : "[arg6, arg11]",
    "returnArgs" : "[arg20]"
  }
]


我需要将这些方法按正确的顺序（链）运行，例如：


methodC //the output of this method is not used as an input argument to other methods

methodA //chain i need right order
methodB
methodZ


第二种情况

[   
  .....
  {
    "name" : "methodX", //methodX output arguments are methodY input arguments
    "inArgs" : «arg1, arg2, arg3]»,
    "returnArgs" : «[arg4, arg5, arg6]»
  },
  {
    "name" : "methodY", //methodY output arguments are methodX input arguments
    "inArgs" : «[arg4, arg5, arg7]»,
    "returnArgs" : «[arg8, arg9, arg10]»
  },
  ....
  {
    "name" : "methodZ", //methodZ output arguments are methodX input arguments( collision or cycle, so throw error )
    "inArgs" : «[arg8, arg11, arg12]»,
    "returnArgs" : «[arg3, arg13, arg14]»
  },
]


因为一个方法的输出自变量可以是另一种方法的输入自变量（也可以通过不确定嵌套的方法链），所以有必要捕获此类冲突，最好是在解析配置阶段。

有人可以为这种问题提供最佳解决方案的建议，到目前为止，只有图可以想到。

对不起我的英语不好。

最佳答案

（对不起，这是一个很长的答案。我希望它会有用。）

我喜欢的答案

我开始尝试使用您正在寻找的API解决此问题。我确实设法得到了一些合理的东西。但这不是我个人使用的东西。我重写了API并重构了实现多次，直到我想出自己想使用的东西。下面，我将讨论我的更多早期步骤（可能与您更相关），但是这是我如何使用我的版本的方法：

const def = {
  url: (server, path, query, fragment) => `${server}/${path || ''}${query || ''}${fragment ? `#${fragment}` : ''}`,
  query: (parameters) => parameters ? '?' + Object.entries(parameters).map(([k, v]) => `${k}=${v}`).join('&') : '',
  server: (schema, port, host) => `${schema}:/\/${host}${port && (String(port) != '80') ? `:${port}` : ''}`,  
  host: (domain, subdomain) => `${subdomain ? `${subdomain}.` : ''}${domain}`,
}

const vals = {
  schema: 'https',
  port: '80',
  domain: 'example.com',
  subdomain: 'test',
  path: 'path/to/resource',
  parameters: {foo: 42, bar: 'abc'},
  fragment: 'baz',
}


runFunctions (def) (vals)


这将产生如下输出：

{
  schema: "https",
  port: "80",
  domain: "example.com",
  subdomain: "test",
  path: "path/to/resource",
  parameters: {foo: 42, bar: "abc"},
  fragment: "baz",
  query: "?foo=42&bar=abc",
  host: "test.example.com",
  server: "https://test.example.com",
  url: "https://test.example.com/path/to/resource?foo=42&bar=abc#baz"
}


API设计

我在此版本中看到的主要优点是API感觉很干净。配置对象仅将名称映射到函数，而提供给结果函数的数据对象仅将名称映射到那些函数所需的初始参数。结果是该数据对象的增强版本。初始调用返回一个可重用的函数。一切都非常简单。

实作

我如何编写此代码的一些历史已嵌入到设计中。它可能可以使用良好的重构。几个辅助功能可能不是必需的。但目前它包括：


四个简单的助手功能：


isEmpty报告数组是否为空
removeIndex的作用就像一个不变的splice，返回不带第n个索引的数组的副本
props将属性名称数组映射到给定对象中的值
error只是将字符串包装在错误中并引发

少一些的辅助功能：


parseArgs从函数中检索参数名称。它基于https://stackoverflow.com/a/9924463。 （奇怪的是，我尝试的第一个https://stackoverflow.com/a/31194949在我的测试REPL中运行良好，但在StackOverflow片段中却失败了。）

四个主要功能：


preprocess将我们的描述对象转换为看起来像问题中描述的结构的配置对象（具有name和inArgs属性，但没有returnArgs的属性。）
makeGraph转换将配置对象转换为邻接图（具有name字符串和predecessors字符串数组的对象数组。）
sortGraph在邻接图上执行拓扑排序。它是从我在https://stackoverflow.com/a/54408852/处写的一个书借来的，但是如果图形是循环的，则可以抛出错误。
process接受配置对象和排序的图并生成一元函数。该函数接受一个上下文对象，并将这些函数按顺序应用于该对象的属性，从而为该对象添加一个新值，该值以函数名命名。这将调用makeGraph，然后在结果上调用sortGraph。

最后是一个小的包装函数：


runFunctions接受描述对象，在其上调用preprocess以创建配置对象，然后将其传递给process并返回结果函数。



我敢肯定，有一个合理的重构可以消除对中间配置对象的需要和/或将图形的创建和排序结合在一起的对象。留给读者练习！

完整的例子



// helpers
const isEmpty = arr =>
  arr .length == 0
const removeIndex = (n, arr) =>
  arr .slice (0, n) .concat (arr .slice (n + 1) )
const props = (names) => (obj) => 
  names .map (name => obj [name] )
const error = (msg) => {
  throw new Error (msg)
}
// retrieves parameter named from a function (https://stackoverflow.com/a/9924463)
const parseArgs = (func) => {
  var fnStr = func.toString().replace( /((\/\/.*$)|(\/\*[\s\S]*?\*\/))/mg, '');
  var result = fnStr.slice(fnStr.indexOf('(')+1, fnStr.indexOf(')')).match(/([^\s,]+)/g);
  if(result === null)
     result = [];
  return result;
}


// chooses an appropriate order for our digraph, throwing error on circular
const sortGraph = (
  graph,
  sorted = [],
  idx = graph .findIndex (node => isEmpty (node.predecessors) ),
  nodeName = (graph [idx] || {}) .name
) => isEmpty (graph)
  ? sorted
  : idx < 0
    ? error ('function definitions contains cycle')
    : sortGraph (
      removeIndex (idx, graph) .map (({name, predecessors}) => ({
        name,
        predecessors: predecessors .filter (n => n !== nodeName)
      }), graph),
      sorted .concat (nodeName)
    )

// turns a config into an adjacensy graph
const makeGraph = config =>
  Object .entries (config) .map (([name, {inArgs}]) => ({
    name,
    predecessors: inArgs .filter (name => name in config)
  }) )


// turns a config object into a function that will run its
// functions in an appropriate order
const process = (config, order = sortGraph (makeGraph (config) )) =>
  (vals) =>
    order .reduce
      ( (obj, name) => ({
        ...obj, 
        [name]: config [name] .fn .apply (obj, props (config [name] .inArgs) (obj) )
      })
      , vals
      )

// converts simpler configuration into complete version
const preprocess = (def) => 
  Object .entries (def) .reduce
    ( (obj, [name, fn]) => ( { ...obj, [name]: {fn, inArgs: parseArgs(fn)}      })
    , {}
    )


// main function
const runFunctions = (def) => 
  process (preprocess (def) )


// input definition
const def = {
  url: (server, path, query, fragment) => `${server}/${path || ''}${query || ''}${fragment ? `#${fragment}` : ''}`,
  query: (parameters) => parameters ? '?' + Object.entries(parameters).map(([k, v]) => `${k}=${v}`).join('&') : '',
  server: (schema, port, host) => `${schema}:/\/${host}${port && (String(port) != '80') ? `:${port}` : ''}`,  
  host: (domain, subdomain) => `${subdomain ? `${subdomain}.` : ''}${domain}`,
}

// initial input object
const vals = {
  schema: 'https',
  port: '80',
  domain: 'example.com',
  subdomain: 'test',
  path: 'path/to/resource',
  parameters: {foo: 42, bar: 'abc'},
  fragment: 'baz',
}


console .log (
  runFunctions (def) (vals)
)





与要求的设计不同

问题中的API是不同的：配置对象看起来更像：

[{
  name: 'makeUrl',
  inArgs: '[domain, subdomain]',
  returnArgs: '[host]',
}, /* ... */]


甚至经过一些清理后，看起来还是这样：

[{
  name: 'makeHost',
  inArgs: ['domain', 'subdomain'],
  returnArgs: ['host'],
}, /* ... */]


这比我的解决方案更灵活，因为它允许将单个函数包装在数组中以多个形式返回。但是在实现过程中如果没有一些不适的体操技巧，则每个函数还需要多次返回。此外，这将要求无论您提供了什么函数，都必须将函数与名称分别匹配，必须确保参数名称和顺序与inArgs参数完全匹配，并且必须包装数组中更常见的标量返回。可能看起来像这样：

const fns = {
  makeHost: (domain, subdomain) => [`${subdomain ? `${subdomain}.` : ''}${domain}`],
  /* ... */
}


我的初步方法

在我看来，添加第二个配置参数并使它们保持同步可使人机工程学API少得多。但这是可以做到的，而这正是我首先解决这个问题的方式。

此版本需要更少的帮助程序功能。不需要preprocess或parseArgs。添加props只是为了简化上面的重构版本。我还没有检查它是否会帮助这一点。

注意，这里process实质上要复杂得多，而makeGraph则要稍微复杂一些。这是因为处理多个返回参数会增加很多工作。总体而言，此版本比上述版本短几行。创建更舒适的API时通常要权衡取舍。但是各个功能并不复杂。

实作

您可以扩展此代码片段以查看完整的示例：



// helpers
const isEmpty = arr =>
  arr .length == 0
const removeIndex = (n, arr) =>
  arr .slice (0, n) .concat (arr .slice (n + 1))
const error = (msg) => {
  throw new Error (msg)
}

// chooses an appropriate order for our digraph, throwing error on circular
const sortGraph = (
  graph,
  sorted = [],
  idx = graph .findIndex (node => isEmpty (node.predecessors) ),
  nodeName = (graph [idx] || {}) .name
) => isEmpty (graph)
  ? sorted
  : idx < 0
    ? error ('contains cycle')
    : sortGraph (
      removeIndex (idx, graph) .map (({name, predecessors}) => ({
        name,
        predecessors: predecessors .filter (n => n !== nodeName)
      }), graph),
      sorted .concat (nodeName)
    )

// turns a config into an adjacensy graph
const makeGraph = config =>
  config .map (({name, inArgs}) => ({
    name,
    predecessors: inArgs .flatMap (
      input => config
        .filter ( ({returnArgs}) => returnArgs .includes (input) )
        .map ( ({name}) => name )
    )
  }) )

// main function
const process = (config) => (fns, order = sortGraph (makeGraph (config) )) =>
  (vals) =>
    order .reduce
      ( (obj, name) => {
          const {inArgs, returnArgs} = config .find
            ( node => node .name == name
            )
          const args = inArgs .map (key => obj [key])
          const res = fns [name] .apply (obj, args)
          return returnArgs .reduce
            ( (o, k, i) => ({...o, [k]: res [i]})
            , obj
            )
        }
      , vals
      )


const config = [
  {name: 'host', inArgs: ['domain', 'subdomain'], returnArgs: ['host']},
  {name: 'server', inArgs: ['schema', 'port', 'host'], returnArgs: ['server']},
  {name: 'query', inArgs: ['parameters'], returnArgs: ['query']},
  {name: 'url', inArgs: ['server', 'path', 'query', 'fragment'], returnArgs: ['url']}
]

const fns = {
  host: (domain, subdomain) => [`${subdomain ? `${subdomain}.` : ''}${domain}`],
  server: (schema, port, host) => 
    [`${schema}:/\/${host}${port && (String(port) != '80') ? `:${port}` : ''}`],
  query: (parameters) => [parameters ? '?' + Object.entries(parameters).map(([k, v]) => `${k}=${v}`).join('&') : ''],
  url: (server, path, query, fragment) => [`${server}/${path || ''}${query || ''}${fragment ? `#${fragment}` : ''}`]
}

const vals = {
  schema: 'https',
  port: '80',
  domain: 'example.com',
  subdomain: 'test',
  path: 'my/path',
  parameters: {foo: 42, bar: 'abc'},
  fragment: 'baz',
}


console .log (
  process (config) (fns) (vals)
)





中级工作

我什至不会尝试显示代码在初始版本和最终版本之间经历的所有阶段，但是API中有一个有趣的航路点，在其中我使用了如下配置对象：

const config = {
  host: {
    inArgs: ['domain', 'subdomain'], 
    fn: (domain, subdomain) => `${subdomain ? `${subdomain}.` : ''}${domain}`,
  },
  /* ... */
}


对于该版本，要说些什么：它避免为了获得参数而解析函数的需要。 How to get function parameter names/values dynamically?的各种脆弱答案表明，这是一个不平凡的问题。 Angular依赖注入的用户应该非常熟悉。

但是最后，这太干净了：

const config = {
  host: fn: (domain, subdomain) => `${subdomain ? `${subdomain}.` : ''}${domain}`,
  /* ... */
}


因此，我更喜欢最终版本。

结论

这是一个不平凡的问题。

在任何这些版本中，实现都不是特别困难。但是将其分解成有用的部分是具有挑战性的。当我们有足够的灵活性来选择合适的东西时，确定一个有用的API可能需要大量的思考，大量的讨论和大量的尝试。

通常，由于重要的原因，不同的开发人员会做出不同的选择，但是对我来说，牺牲可能稀有的功能来从单个函数中获得多个回报对于实现实质上简单的配置对象完全是值得的。实际上，很难想象有一个更简单的配置。

关于javascript - 如何构建运行和查找循环(​​冲突)的方法链，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57562279/

上一篇：javascript - 当没有传入参数时，knex.js 方法 `table.increments()` 会做什么？

下一篇：javascript - w 和 h 必须是数字

相关文章：

algorithm - 使用 DFS 打印至少两条路径可访问的所有节点

python - 与 Python 相比，具有动态分配的结构数组在 C 中运行非常慢

c - 快速确定递归函数返回的最终值

c - 我想输出 1 3 4 5 7 9 但我几乎卡在这里

algorithm - 寻找最小瓶颈路径的线性时间算法

javascript - 修改函数参数

haskell - 有没有办法在这个算法中不使用显式递归？

基于最终排序索引的具有多个键的 JavaScript 复杂排序

javascript - 创建一个 JavaScript 查找，将用户输入与大量项目列表进行比较

javascript - 如何获取可拖动标记经纬度信息

©2024 IT工具网  联系我们