如何获取，解决和验证传递性/循环依赖性

问题描述 投票：2回答：1

我需要一些自定义方法来解析可能具有传递性的变量，并验证循环/无法解析的字段。例如

var v1 = 'asd';
var v2 = '@@{v1}@@';
var v3 = '@@{v2}@@';
var v4 = '@@{v3}@@';
var v5 = '@@{v4}@@';
var v6 = '@@{v5}@@_@@{v3}@@';

var a1 = '@@{v1}@@_@@{a3}@@';
var a2 = '@@{a1}@@';
var a3 = '@@{a2}@@';

var x1 = 'asd';
var x2 = '@@{x1}@@';
var x3 = '@@{x1}@@_@@{x2}@@';

var p1 = '@@{v4}@@_@@{xyz}@@';
var p2 = '@@{xyz}@@';

const getVariableNames = str => {
    str += '';
    const variables = str.match(/(@@{[^}{)(\]\[\-+*\/]+?}@@)+?/g);
    return variables && variables.length ? variables.map(i => i.substring(3, i.length - 3)) : false;
};

const isCyclic = (myMap, node, target, [...visited] = []) => {
    if (myMap[node]) {
        if (node === target) {
            return true;
        }
        if (visited.includes(node) || !myMap[node].dep.usedIns) {
            return false;
        }
        visited.push(node);
        return myMap[node].dep.usedIns.some(n => isCyclic(myMap, n, target, visited));
    }
};

var allVars = [{ name: 'v1', val: v1 }, { name: 'v2', val: v2 },
    { name: 'v3', val: v3 }, { name: 'v4', val: v4 }, { name: 'v5', val: v5 }, { name: 'v6', val: v6 },
    { name: 'a1', val: a1 }, { name: 'a2', val: a2 }, { name: 'a3', val: a3 }, { name: 'x1', val: x1 },
    { name: 'x2', val: x2 }, { name: 'x3', val: x3 }];

function getValueMap(arr) {
    // need to get implemented
    var nodeAVL = [];
    const varNamesMap = arr.reduce((a, b) => {
        a[b.name] = { ...b, v: getVariableNames(b.val), dependsOn: [], usedIn: [], cyclic: [], unresolved: [] };
        return a;
    }, {});
    return varNamesMap;
}

var retVar = getValueMap(allVars);

console.log(retVar);
// should console
/* {
    v1: { val: 'asd', dependsOn: [], usedIn: ['v2', 'v3', 'v4', 'v5', 'v6', 'p1'], cyclic: [], unresolved: [] },
    v2: { val: 'asd', dependsOn: ['v1'], usedIn: ['v3', 'v4', 'v5', 'v6'], cyclic: [], unresolved: [] },
    v3: { val: 'asd', dependsOn: ['v2'], usedIn: ['v4', 'v5', 'v6'], cyclic: [], unresolved: [] },
    v4: { val: 'asd', dependsOn: ['v3'], usedIn: ['v5', 'v6'], cyclic: [], unresolved: [] },
    v5: { val: 'asd', dependsOn: ['v4'], usedIn: ['v6'], cyclic: [], unresolved: [] },
    v6: { val: 'asd_asd', dependsOn: ['v5', 'v3'], usedIn: [], cyclic: [], unresolved: [] },

    a1: { val: '', dependsOn: ['v1'], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },
    a2: { val: '', dependsOn: [], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },
    a3: { val: '', dependsOn: [], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },

    x1: { val: 'asd', dependsOn: [], usedIn: [], cyclic: [], unresolved: [] },
    x2: { val: 'asd', dependsOn: ['x1'], usedIn: ['x3'], cyclic: [], unresolved: [] },
    x3: { val: 'asd_asd', dependsOn: ['x1', 'x2'], usedIn: [], cyclic: [], unresolved: [] },

    p1: { val: '', dependsOn: ['v4'], usedIn: [], cyclic: [], unresolved: ['xyz'] },
    p2: { val: '', dependsOn: [], usedIn: [], cyclic: [], unresolved: ['xyz'] },
};*/

我的预期输出是

{
    v1: { val: 'asd', dependsOn: [], usedIn: ['v2', 'v3', 'v4', 'v5', 'v6', 'p1'], cyclic: [], unresolved: [] },
    v2: { val: 'asd', dependsOn: ['v1'], usedIn: ['v3', 'v4', 'v5', 'v6'], cyclic: [], unresolved: [] },
    v3: { val: 'asd', dependsOn: ['v2'], usedIn: ['v4', 'v5', 'v6'], cyclic: [], unresolved: [] },
    v4: { val: 'asd', dependsOn: ['v3'], usedIn: ['v5', 'v6'], cyclic: [], unresolved: [] },
    v5: { val: 'asd', dependsOn: ['v4'], usedIn: ['v6'], cyclic: [], unresolved: [] },
    v6: { val: 'asd_asd', dependsOn: ['v5', 'v3'], usedIn: [], cyclic: [], unresolved: [] },

    a1: { val: '', dependsOn: ['v1'], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },
    a2: { val: '', dependsOn: [], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },
    a3: { val: '', dependsOn: [], usedIn: [], cyclic: ['a1', 'a2', 'a3'], unresolved: [] },

    x1: { val: 'asd', dependsOn: [], usedIn: [], cyclic: [], unresolved: [] },
    x2: { val: 'asd', dependsOn: ['x1'], usedIn: ['x3'], cyclic: [], unresolved: [] },
    x3: { val: 'asd_asd', dependsOn: ['x1', 'x2'], usedIn: [], cyclic: [], unresolved: [] },

    p1: { val: '', dependsOn: ['v4'], usedIn: [], cyclic: [], unresolved: ['xyz'] },
    p2: { val: '', dependsOn: [], usedIn: [], cyclic: [], unresolved: ['xyz'] },
}
javascript graph transitive-dependency cyclic-dependency
1个回答
1
投票

这几乎可以输出您的预期输出：

const v1 = 'asd';
const v2 = '@@{v1}@@';
const v3 = '@@{v2}@@';
const v4 = '@@{v3}@@';
const v5 = '@@{v4}@@';
const v6 = '@@{v5}@@_@@{v3}@@';

const a1 = '@@{v1}@@_@@{a3}@@';
const a2 = '@@{a1}@@';
const a3 = '@@{a2}@@';

const x1 = 'asd';
const x2 = '@@{x1}@@';
const x3 = '@@{x1}@@_@@{x2}@@';

const p1 = '@@{v4}@@_@@{xyz}@@';
const p2 = '@@{xyz}@@';

const getVariableNames = (str) => {
    str += '';
    const variables = str.match(/(@@{[^}{)(\][\-+*/]+?}@@)+?/g);
    return variables && variables.length ? variables.map(i => i.substring(3, i.length - 3)) : false;
};

const getVal = (str, arr) => arr.filter(v => v.name === str)[0].val;

const isCyclic = (varName, arr, visited = [varName]) => {
    const varNames = getVariableNames(getVal(varName, arr));
    if (!varNames) return false;
    if (varNames.some(n => getVariableNames(getVal(n, arr)) && getVariableNames(getVal(n, arr)).some(v => visited.includes(v)))) return true;
    return varNames.some(n => isCyclic(n, arr, visited));
};

const isUnresolved = (varName, arr) => !arr.filter(v => v.name === varName).length;

const resolve = (str, arr) => {
    const varNames = getVariableNames(str);
    if (varNames) varNames.forEach(n => str = str.replace(`@@{${n}}@@`, resolve(getVal(n, arr), arr)));
    return str;
};

const usedIn = (varName, map, arr) => {
    const result = [];
    Object.entries(map)
        .filter(([, value]) => value.dependsOn.includes(varName))
        .forEach(([name, value]) => {
            const varNames = getVariableNames(value.val);
            if (varNames && !value.unresolved.length) result.push(...usedIn(name, map, arr));
            else result.push(name);
        });
    return result;
};

const getValueMap = (arr) => {
    const varNamesMap = arr.reduce((acc, curr) => {
        let val = '';
        const dependsOn = [];
        const cyclic = [];
        const unresolved = [];

        const varNames = getVariableNames(curr.val);
        if (varNames) {
            varNames.forEach(varName => {
                if (isUnresolved(varName, arr) || isCyclic(varName, arr)) {
                    if (isUnresolved(varName, arr)) unresolved.push(varName);
                    else if (isCyclic(varName, arr)) cyclic.push(varName);
                    val = '';
                } else dependsOn.push(varName);
            });
        }

        if (!cyclic.length && !unresolved.length) val = resolve(curr.val, arr);

        acc[curr.name] = { val, dependsOn, usedIn: [], cyclic, unresolved };
        return acc;
    }, {});

    Object.keys(varNamesMap).forEach(name => varNamesMap[name].usedIn.push(...usedIn(name, varNamesMap, arr)));

    return varNamesMap;
};

const allVars = [
    { name: 'v1', val: v1 }, { name: 'v2', val: v2 }, { name: 'v3', val: v3 },
    { name: 'v4', val: v4 }, { name: 'v5', val: v5 }, { name: 'v6', val: v6 },
    { name: 'a1', val: a1 }, { name: 'a2', val: a2 }, { name: 'a3', val: a3 },
    { name: 'x1', val: x1 }, { name: 'x2', val: x2 }, { name: 'x3', val: x3 },
    { name: 'p1', val: p1 }, { name: 'p2', val: p2 }
];

console.log(getValueMap(allVars));

此输出：

{
  v1: { val: 'asd', dependsOn: [], usedIn: ['v2', 'a1'], cyclic: [], unresolved: [] },
  v2: { val: 'asd', dependsOn: ['v1'], usedIn: ['v3'], cyclic: [], unresolved: [] },
  v3: { val: 'asd', dependsOn: ['v2'], usedIn: ['v4', 'v6'], cyclic: [], unresolved: [] },
  v4: { val: 'asd', dependsOn: ['v3'], usedIn: ['v5', 'p1'], cyclic: [], unresolved: [] },
  v5: { val: 'asd', dependsOn: ['v4'], usedIn: ['v6'], cyclic: [], unresolved: [] },
  v6: { val: 'asd_asd', dependsOn: ['v5', 'v3'], usedIn: [], cyclic: [], unresolved: [] },

  a1: { val: '', dependsOn: ['v1'], usedIn: [], cyclic: ['a3'], unresolved: [] },
  a2: { val: '', dependsOn: [], usedIn: [], cyclic: ['a1'], unresolved: [] },
  a3: { val: '', dependsOn: [], usedIn: [], cyclic: ['a2'], unresolved: [] },

  x1: { val: 'asd', dependsOn: [], usedIn: ['x2', 'x3'], cyclic: [], unresolved: [] },
  x2: { val: 'asd', dependsOn: ['x1'], usedIn: ['x3'], cyclic: [], unresolved: [] },
  x3: { val: 'asd_asd', dependsOn: ['x1', 'x2'], usedIn: [], cyclic: [], unresolved: [] },

  p1: { val: '', dependsOn: ['v4'], usedIn: [], cyclic: [], unresolved: ['xyz'] },
  p2: { val: '', dependsOn: [], usedIn: [], cyclic: [], unresolved: ['xyz'] }
}

唯一的区别是：

  • [usedIn仅具有直接使用该变量的变量（例如v3.usedIn是[v4, v6]而不是[v4, v5, v6]）]
  • [cyclic仅具有直接使用的循环变量（例如a2.cyclic是[a1]而不是[a1, a2, a3]）]
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.