1

What I have: there is some json config (descriptive template), methods stored in diffrent order, its look like:

[   
  {
    "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]"
  }
]

I need to put these methods in the right order(chain) to run, like:


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

methodA //chain i need right order
methodB
methodZ

second case

[   
  .....
  {
    "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]»
  },
]

Because the output arguments of one method can be the input arguments of another method (also through a chain of methods of indefinite nesting), it is necessary to catch such collisions, preferably at the stage of parsing the config.

Can someone advise the optimal solution to such a problem, so far only graphs come to mind.

Sorry for my English.

  • Have you tried anything so far? Please share what you've done and where you're stuck. – Scott Sauyet Aug 19 '19 at 18:57
  • If you need to solve dependency, you will have to make it into a graph. I would love to help, but the question is too hard to understand. – Akxe Aug 19 '19 at 19:00
  • I think this would be more clear if you didn't name your arguments as `inArg2`, `outArg5`, etc, but just as `arg2`, `arg5`, etc, since the same value can be used as an output of one function and an input of another. – Scott Sauyet Aug 19 '19 at 19:41
  • I also think `"inArgs" : "[inArg1, inArg2]"` is much more difficult to work with than `"inArgs" : ["inArg1", "inArg2"]`. If that input format is essential, I would still suggest preprocessing to turn it into something more useful. – Scott Sauyet Aug 19 '19 at 19:42
  • JS does not have mutliple returns. A function will return a single value. Do you expect that everything returns an array of results you can then destructure, or should your configuration also allow `"returnArgs" : "outArg42"`. If the latter, then my previous comment may not matter. – Scott Sauyet Aug 19 '19 at 19:50
  • Your naming suggests that `methodA` and friends are methods on some object, but your suggested implementation calls them as plain functions. If they are plain functions, then you will need also to include a reference to them in your configuration. – Scott Sauyet Aug 19 '19 at 19:54
  • Thanks for the comment. you're right, your option is easier to understand by other participants. The main thing here is that the methods have input and output arguments, the format does not matter yet since I need an algorithm of actions – Ruslan private Aug 19 '19 at 19:59
  • "JS does not have mutliple returns. A function will return a single value." i am return array of values – Ruslan private Aug 19 '19 at 20:00
  • But is every function required to return an array of values, wrapping single responses in an array, or do some return an array and others return a single value? – Scott Sauyet Aug 19 '19 at 20:11
  • How to solve this problem at the parsing stage? I need an algorithm that parses this config, if there are cycles then it will just throw an error. If there are no errors, then I need to get the list of methods in the right order: first come the methods, the output arguments of which are not input arguments of other methods, let's call them singles. Next come the methods the very chain of methods: Order to run: methodC //single
    methodA //chain
    methodB
    methodZ
    – Ruslan private Aug 19 '19 at 20:22
  • I changed the conditions of the task and removed unnecessary confusing things. I apologize to the community for the poorly composed question. – Ruslan private Aug 19 '19 at 20:49
  • This was not a poorly composed question. It sometimes take a little back and forth to understand someone's requirements. What it missing, though, is some description of your own efforts. What have you tried so far? – Scott Sauyet Aug 19 '19 at 23:06

2 Answers2

1

(Sorry, this is a very long answer. I hope it's useful.)

An answer I like

I started trying to solve this using the API you were looking for. I did manage to get something reasonably close. But it wasn't something I would personally use. I rewrote the API and refactored the implementation several times until I came up with something I would like to use. Below I will discuss more of my early steps (which may be more relevant to you) but here is how I would use my version:

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) 

This would generate an output like the following:

{
  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 Design

The main advantage I see in this version is that the API feels quite clean. The configuration object just maps names to functions and the data object supplied to the resulting function simply maps names to the initial parameters needed by those functions. The result is an enhanced version of that data object. The initial call returns a reusable function. It's all very simple.

Implementation

Some of the history of how I wrote this is embedded in the design. It probably could use a good refactoring; several of the helper functions are probably not necessary. But for now it consists of:

  • four trivial helper functions:

    • isEmpty reports whether an array is empty
    • removeIndex acts like an immutable splice, returning a copy of an array without its nth index
    • props maps an array of property names to their values in a given object
    • error simply wraps a string in an error and throws it
  • one less trivial helper function:

  • four main functions:

    • preprocess converts our description object into a configuration object that looks something like the structure described in the question (with name and inArgs properties, although without returnArgs ones.)
    • makeGraph converts converts a configuration object into an adjacency graph (an array of objects with a name string and a predecessors array of strings.)
    • sortGraph performs a topological sort on an adjacency graph. It's borrowed from one I wrote at https://stackoverflow.com/a/54408852/, but enhanced with the ability to throw an error if the graph is cyclic.
    • process accepts the configuration object and the sorted graph and generates a unary function. That function takes a context object and applies the functions in order to the properties of that object, adding a new value to the object keyed to the function name. This calls makeGraph and then sortGraph on the result.
  • and, finally, a small wrapper function:

    • runFunctions accepts a description object, calls preprocess on it to create the configuration object, passing that to process and returns the resulting function.

I'm sure there's a reasonable refactoring that removes the need for the intermediate configuration object and/or one that combines the creation and sorting of the graph. That's left as an exercise for the reader!

Complete example

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

Differences from requested design

The API in the question was different: the configuration object looked more like:

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

and even after some cleanup, would look like this:

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

This is more flexible than my solution, as it allows multiple returns from a single function, wrapped in an array. But without some uncomfortable gymnastics in the implementation, it would also require multiple returns from each function. Moreover it would require that however you supplied your functions to this, you would have to match the function separately with the name, you would have to ensure that the argument names and order exactly matched the inArgs parameter, and you would have to wrap the more common scalar returns in an array. That might look something like this:

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

My Initial Approach

Adding a second configuration parameter and keeping them in sync makes for a much less ergonomic API in my opinion. But it can be done, and it was how I first approached the problem.

This version needed several fewer helper functions. There is no need for preprocess or parseArgs. props was only added to simplify the refactored version above. I haven't checked whether it would help with this one.

Note that process is substantially more complicated here and makeGraph is somewhat more complicated. That's because handling the multiple return arguments adds a fair bit of work. Overall, this version is a few lines shorter than the version above. That's often the trade-off when you create a more comfortable API. But the individual functions are less complex.

Implementation

You can expand this snippet to see a complete example:

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

Intermediate Work

I wouldn't even attempt to show all the stages my code went through between the initial and final versions, but there was an interesting waypoint in the API, in which I used a configuration object like this:

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

There is something to be said for that version: it avoids the need to parse the function in order to to get the parameters. The variety of fragile answers to How to get function parameter names/values dynamically? demonstrate that this is a non-trivial problem. And it should be quite familiar to users of Angular's dependency injection.

But in the end, this is just too much cleaner:

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

And hence I prefer my final version.

Conclusions

This is a non-trivial problem.

The implementation is not particularly difficult in any of these versions. But breaking it down into the useful pieces is challenging. And determining a useful API when we're afforded the flexibility to choose whatever seems right can take a lot of thought, a lot of discussion, and a lot of playing around.

Different developers will make different choices, often for important reasons, but to me sacrificing the likely rare facility to have multiple returns from a single function was entirely worth it to achieve a substantially simpler configuration object. In fact, it's difficult to imagine a simpler configuration.

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103
  • Wow, you awsome. Very good and detailed answer, I thank you. I have drawn some good points for myself from this material and will try to implement them in my task. – Ruslan private Aug 21 '19 at 14:38
  • 1
    Scott, good on you for taking this broad question on. I started with an evaluator-based approach but scrapped it when i encountered too many under-specified behaviours. It looks like your persistence paid off :) – Mulan Aug 22 '19 at 14:15
0

An easier, but not-that-bulletproof (you cannot detect cycles) solution would be to wrap every value into a Promise: When a function generates certain outputs, resolve the Promise, then use Promise.all on the inputs. That way, the promises will automatically determine the right order:

const context = { /* [var: string]: { resolve(v: T), value: Promise<T> */ };

function getVar(name) {
 if(context[name]) return context[name].value;
 const cont = context[name] = { };
 return cont.value = new Promise(res => cont.resolve = res);
}

function setVar(name, value) {
 getVar(name); // Make sure prop is initialized, don't await!
 context[name].resolve(value);
}

async function run(fn, argNames, resultNames) {
   const args = await Promise.all(argNames.map(getVar));
   const results = fn(...args);
   for(let i = 0; i < results.length; i++)
     setVar(resultNames[i], results[i]);
}
Jonas Wilms
  • 132,000
  • 20
  • 149
  • 151