Como converter essa estrutura de árvore em um JS MemberExpression estrutura de árvore?

Question 1

Eu descobri uma forma de representar a expressão a.b[c.d][e].f[g[h[i.j]]] usando meu próprio formato de árvore. Que expressão, representado como uma árvore, se parece com isto:

{
  "form": "nest",
  "link": [
    {
      "form": "site",
      "name": "a"
    },
    {
      "form": "site",
      "name": "b"
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "c"
        },
        {
          "form": "site",
          "name": "d"
        }
      ]
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "e"
        }
      ]
    },
    {
      "form": "site",
      "name": "f"
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "g"
        },
        {
          "form": "nest",
          "link": [
            {
              "form": "site",
              "name": "h"
            },
            {
              "form": "nest",
              "link": [
                {
                  "form": "site",
                  "name": "i"
                },
                {
                  "form": "site",
                  "name": "j"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Agora, essa mesma expressão de seqüência de caracteres também é representado por este JS AST estrutura de árvore para o MemberExpression:

{
  "type": "MemberExpression",
  "object": {
    "type": "MemberExpression",
    "object": {
      "type": "MemberExpression",
      "object": {
        "type": "MemberExpression",
        "object": {
          "type": "MemberExpression",
          "object": {
            "type": "Identifier",
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "name": "b"
          },
          "computed": false
        },
        "property": {
          "type": "MemberExpression",
          "object": {
            "type": "Identifier",
            "name": "c"
          },
          "property": {
            "type": "Identifier",
            "name": "d"
          },
          "computed": false
        },
        "computed": true
      },
      "property": {
        "type": "Identifier",
        "name": "e"
      },
      "computed": true
    },
    "property": {
      "type": "Identifier",
      "name": "f"
    },
    "computed": false
  },
  "property": {
    "type": "MemberExpression",
    "object": {
      "type": "Identifier",
      "name": "g"
    },
    "property": {
      "type": "MemberExpression",
      "object": {
        "type": "Identifier",
        "name": "h"
      },
      "property": {
        "type": "MemberExpression",
        "object": {
          "type": "Identifier",
          "name": "i"
        },
        "property": {
          "type": "Identifier",
          "name": "j"
        },
        "computed": false
      },
      "computed": true
    },
    "computed": true
  },
  "computed": true
}

Então, essas duas estruturas de árvore representam a mesma expressão de seqüência de caracteres a.b[c.d][e].f[g[h[i.j]]]. Você vai notar no primeiro "ninho" estrutura", existem dois tipos de objectos, sítios e ninhos. Um site é apenas um nome, enquanto um ninho significa um "calculado" propriedade em JS AST terminologia. Assim é como um ninho parent[this_is_a_nest[and_another_nest]], enquanto parent.site1.site2.

Como transformar a primeira estrutura de árvore para o segundo?

O que eu até agora não é chegar lá, é bastante confuso.

console.log(JSON.stringify(transform(getNest()), null, 2))

function transform(nest) {
  let i = 0
  let stack = []
  while (i < nest.link.length) {
    let object = nest.link[i++]
    let property = nest.link[i]
    let member = {
      type: 'MemberExpression'
    }
    stack.push(member)

    if (object.form === 'nest') {
      member.object = transform(object)
    } else {
      member.object = {
        type: 'Identifier',
        name: object.name
      }
    }

    if (property) {
      if (property.form === 'nest') {
        member.property = transform(property)
        member.computed = true
      } else {
        member.property = {
          type: 'Identifier',
          name: property.name
        }
      }
    }
  }

  let object = stack.pop()
  while (stack.length) {
    let nextObject = stack.pop()
    nextObject.object = object
    object = nextObject
  }

  return object
}


function getNest() {
  return {
    "form": "nest",
    "link": [
      {
        "form": "site",
        "name": "a"
      },
      {
        "form": "site",
        "name": "b"
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "c"
          },
          {
            "form": "site",
            "name": "d"
          }
        ]
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "e"
          }
        ]
      },
      {
        "form": "site",
        "name": "f"
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "g"
          },
          {
            "form": "nest",
            "link": [
              {
                "form": "site",
                "name": "h"
              },
              {
                "form": "nest",
                "link": [
                  {
                    "form": "site",
                    "name": "i"
                  },
                  {
                    "form": "site",
                    "name": "j"
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
}

Realmente não sei como simplificar o problema para baixo em uma forma de resolvê-lo ainda.

Eu não sei se isso é de qualquer tipo de ajuda (acornjs parser para MemberExpression).

Question 2

Isso deve fazê-lo:

function transform(treeNode) {
  if (treeNode.form == "site") {
    return {
      "type": "Identifier",
      "name": treeNode.name,
    };
  } else if (treeNode.form == "nest") {
    const [base, ...props] = treeNode.link;
    console.assert(base.form == "site");
    return props.reduce((lhs, rhs) => {
      if (rhs.form == "nest") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns MemberExpression or (if singleton) Identifier
          "computed": true,
        };
      } else if (rhs.form == "site") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns Identifier
          "computed": false,
        };
      }
    }, transform(base));
  }
}

É claro que você pode simplificar o redutor para apenas

props.reduce((lhs, rhs) => ({
  "type": "MemberExpression",
  "object": lhs,
  "property": transform(rhs),
  "computed": rhs.form == "nest",
}), transform(base));

Question 3

Um curto solução recursiva:

function mem_tree(objs){
    var o = null;
    for (var obj of objs){
       if (obj.form === 'site'){
          o = (o === null) ? {type:"Identifier", name:obj.name} : {type: "MemberExpression", object:o, property:{type:"Identifier", name:obj.name}, computed:false}
       }
       else{
          var r = mem_tree(obj.link);
          o = (o === null) ? {object:r} : {type: "MemberExpression", object:o, property:r, computed:true}
       }
    }
    return o;
}
var d = {'form': 'nest', 'link': [{'form': 'site', 'name': 'a'}, {'form': 'site', 'name': 'b'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'c'}, {'form': 'site', 'name': 'd'}]}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'e'}]}, {'form': 'site', 'name': 'f'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'g'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'h'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'i'}, {'form': 'site', 'name': 'j'}]}]}]}]}
var result = mem_tree(d.link)

Question 4

Eu só resolvi isso um pouco depois @Bergi a resposta antes que eu vi ele, tão animado!

function transform(nest) {
  let i = 0
  let stack = [{
    type: 'Identifier',
    name: nest.link[i++].name
  }]
  while (i < nest.link.length) {
    const object = stack.shift()
    const node = nest.link[i++]
    if (node.form === 'nest') {
      const property = transform(node)
      stack.push({
        object: object,
        property,
        computed: true
      })
    } else {
      let property = {
        type: 'Identifier',
        name: node.name
      }
      stack.push({
        object: object,
        property: property,
        computed: false
      })
    }
  }

  return stack.shift()
}

A saída é:

{
  "object": {
    "object": {
      "object": {
        "object": {
          "object": {
            "type": "Identifier",
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "name": "b"
          },
          "computed": false
        },
        "property": {
          "object": {
            "type": "Identifier",
            "name": "c"
          },
          "property": {
            "type": "Identifier",
            "name": "d"
          },
          "computed": false
        },
        "computed": true
      },
      "property": {
        "type": "Identifier",
        "name": "e"
      },
      "computed": true
    },
    "property": {
      "type": "Identifier",
      "name": "f"
    },
    "computed": false
  },
  "property": {
    "object": {
      "type": "Identifier",
      "name": "g"
    },
    "property": {
      "object": {
        "type": "Identifier",
        "name": "h"
      },
      "property": {
        "object": {
          "type": "Identifier",
          "name": "i"
        },
        "property": {
          "type": "Identifier",
          "name": "j"
        },
        "computed": false
      },
      "computed": true
    },
    "computed": true
  },
  "computed": true
}

Bergi · Answer 1 · 2021-11-23T13:35:06

Isso deve fazê-lo:

function transform(treeNode) {
  if (treeNode.form == "site") {
    return {
      "type": "Identifier",
      "name": treeNode.name,
    };
  } else if (treeNode.form == "nest") {
    const [base, ...props] = treeNode.link;
    console.assert(base.form == "site");
    return props.reduce((lhs, rhs) => {
      if (rhs.form == "nest") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns MemberExpression or (if singleton) Identifier
          "computed": true,
        };
      } else if (rhs.form == "site") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns Identifier
          "computed": false,
        };
      }
    }, transform(base));
  }
}

É claro que você pode simplificar o redutor para apenas

props.reduce((lhs, rhs) => ({
  "type": "MemberExpression",
  "object": lhs,
  "property": transform(rhs),
  "computed": rhs.form == "nest",
}), transform(base));

De jeito nenhum! Você simplificado que até sua nua essência! Na verdade, eu acho que eu só tenho isso também, vou postar a minha resposta bem :D
Então, qual foi a sua técnica, como é que você descobrir isso, tão elegantemente? Eu teria que dizer que este foi bastante complicado. Basicamente, como posso aprender a ser mais como o que você fez :)
@LancePollard Pensamento funcional e tentando recursão ajuda. Estava claro para mim que ele tinha para ser uma pura função, não usando uma pilha e loop (embora, na verdade, eu nem totalmente ler o código de sua tentativa). E há duas direções transversal: uma para baixo, uma propriedade de cadeia, o outro no aninhadas expressões. Dada a cadeia é linear, o que seria uma simples dobra sobre a matriz para gerar o aninhados MemberExpression lista vinculada, para o assentamento a recursividade é necessário. Em seguida, foi apenas uma questão de se reduzir a esquerda ou para a direita e, como caso especial, a começar

Ajax1234 · Answer 2 · 2021-11-24T05:25:09

Um curto solução recursiva:

function mem_tree(objs){
    var o = null;
    for (var obj of objs){
       if (obj.form === 'site'){
          o = (o === null) ? {type:"Identifier", name:obj.name} : {type: "MemberExpression", object:o, property:{type:"Identifier", name:obj.name}, computed:false}
       }
       else{
          var r = mem_tree(obj.link);
          o = (o === null) ? {object:r} : {type: "MemberExpression", object:o, property:r, computed:true}
       }
    }
    return o;
}
var d = {'form': 'nest', 'link': [{'form': 'site', 'name': 'a'}, {'form': 'site', 'name': 'b'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'c'}, {'form': 'site', 'name': 'd'}]}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'e'}]}, {'form': 'site', 'name': 'f'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'g'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'h'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'i'}, {'form': 'site', 'name': 'j'}]}]}]}]}
var result = mem_tree(d.link)

Lance Pollard · Answer 3 · 2021-11-23T13:45:28

Eu só resolvi isso um pouco depois @Bergi a resposta antes que eu vi ele, tão animado!

function transform(nest) {
  let i = 0
  let stack = [{
    type: 'Identifier',
    name: nest.link[i++].name
  }]
  while (i < nest.link.length) {
    const object = stack.shift()
    const node = nest.link[i++]
    if (node.form === 'nest') {
      const property = transform(node)
      stack.push({
        object: object,
        property,
        computed: true
      })
    } else {
      let property = {
        type: 'Identifier',
        name: node.name
      }
      stack.push({
        object: object,
        property: property,
        computed: false
      })
    }
  }

  return stack.shift()
}

A saída é:

{
  "object": {
    "object": {
      "object": {
        "object": {
          "object": {
            "type": "Identifier",
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "name": "b"
          },
          "computed": false
        },
        "property": {
          "object": {
            "type": "Identifier",
            "name": "c"
          },
          "property": {
            "type": "Identifier",
            "name": "d"
          },
          "computed": false
        },
        "computed": true
      },
      "property": {
        "type": "Identifier",
        "name": "e"
      },
      "computed": true
    },
    "property": {
      "type": "Identifier",
      "name": "f"
    },
    "computed": false
  },
  "property": {
    "object": {
      "type": "Identifier",
      "name": "g"
    },
    "property": {
      "object": {
        "type": "Identifier",
        "name": "h"
      },
      "property": {
        "object": {
          "type": "Identifier",
          "name": "i"
        },
        "property": {
          "type": "Identifier",
          "name": "j"
        },
        "computed": false
      },
      "computed": true
    },
    "computed": true
  },
  "computed": true
}

Como converter essa estrutura de árvore em um JS MemberExpression estrutura de árvore?

Pergunta

Melhor resposta

Em outros idiomas

Esta página está em outros idiomas

Popular nesta categoria

Perguntas populares nesta categoria