Recursion detected

[petrkrejci1]

Hello, to extend this following answer with a question:
2.
At the moment, recurrent connections are forbidden, as this leads to hangup when processing nodes.
Probably, in the future the question with cyclic execution of the nodes will be solved

_Originally posted by @Ni55aN in #116 (comment)

...You wrote that recurrent connections are forbidden, but when I actually try to connect nodes in recursion it does not stop me. I am able to make recurrent connections, only thing I am getting is console log message saying following: "{message: "Recursion detected", data: Array(3)}".

Is there a way how to stop user from drawing the connection that creating recursive loop?

Thank you so much in advance and especially thank you for great Rete :-).

[Ni55aN]

You wrote that recurrent connections are forbidden, but when I actually try to connect nodes in recursion it does not stop me.

Forbidden for processing, but not for visualization

There is implementation based on imported data (toJSON()) https://github.com/retejs/rete/blob/master/src/engine/index.js#L49

by the same principle, a plugin can define recursion by the list of nodes in the editor

[petrkrejci1]

by the same principle, a plugin can define recursion by the list of nodes in the editor

I see, so the question is from where is it the best to call this detectRecursions() function. I am thinking about calling it from (or maybe actually copy pasting it to) the picker.js located in rete-connection-plugin. Do you thing it is the good idea or would you rather suggest calling it from different place?

My aim is to stop user from being able to make a recursive connection in editor.

Thank you once again for your help. Cheers

[Ni55aN]

Do you thing it is the good idea or would you rather suggest calling it from different place?

Core of the framewok is event based, so it'll be reasonable to subscribe on connectioncreated event and detect recursion. I'm working on it now

[Ni55aN]

Fast solution, but not performant:

   engine.detectRecursions(editor.toJSON().nodes);

[Ni55aN]

This is not the best option, but quite working. It can be improved by subscribing to the connectioncreate event and returning false if the connection (not yet added) can lead to recursion (but it can be more difficult to implement

https://codepen.io/Ni55aN/pen/pGYrgp

const RecursionPlugin = {
      extractInputNodes(node) {
        return node.getConnections().filter(c => c.input.node === node).map(c => c.output.node);
      },
      detect(editor) {
        // console.log(window.engine.detectRecursions(editor.toJSON().nodes));
        const nodesArr = [...editor.nodes];
        const findSelf = (node, inputNodes) => {
            if (inputNodes.some(n => n === node))
                return node;
            
            for (var i = 0; i < inputNodes.length; i++) {
                if (findSelf(node, this.extractInputNodes(inputNodes[i])))
                    return node;
            }

            return null;
        }

        return nodesArr.map(node => {
            return findSelf(node, this.extractInputNodes(node))
        }).filter(r => r !== null);
    }

}

  editor.on('connectioncreated', (c) => {
    const recurrectNodes = RecursionPlugin.detect(editor);
    
    if(recurrectNodes.length > 0) {
      editor.removeConnection(c);
      alert('Connection removed due to recursion')
    }
  });

[petrkrejci1]

Fast solution, but not performant:

   engine.detectRecursions(editor.toJSON().nodes);

This definitely works! The only problem I encountered is when I hit redo (Ctrl+Y) after trying to create recursive connection. It tries to recreate this recursive connection which is not appropriate behaviour I would say. But that is another thing, it would be probable good idea to not saving / removing this step from history stack.

[Ni55aN]

I think the ideal solution is detect recursion before adding a new connection (on connectioncreate)

[petrkrejci1]

This is not the best option, but quite working. It can be improved by subscribing to the connectioncreate event and returning false if the connection (not yet added) can lead to recursion (but it can be more difficult to implement

https://codepen.io/Ni55aN/pen/pGYrgp

Just tried and yes, it is working as well. Probable good idea to add this with async function and await engine.abort() though.

One last thing I found annoying is when I am trying to create recursive connection while there is already another existing connection on the nodes's input (not the recursive one), it shows me an alert, but also remove the existing connection which is not necessary. So I agree with this statement for sure: #255 (comment)

[Ni55aN]

but also remove the existing connection which is not necessary

Before add a new connection, place will be allocated for it

https://github.com/retejs/connection-plugin/blob/master/src/picker.js#L39

[Ni55aN]

Improved recursion detector plugin based on connectioncreate event

const RecursionPlugin = {
    install(editor) {
      editor.on('connectioncreate', (c) => {
        const recurrectNode = RecursionPlugin.detect(c);
        
        if(recurrectNode) {
          alert('Connection removed due to recursion');
          return false;
        }
      });
    },
      findSelf (node, inputNodes){
        if (inputNodes.some(n => n === node))
          return true;

        for (var i = 0; i < inputNodes.length; i++) {
          if (this.findSelf(node, this.extractInputNodes(inputNodes[i])))
            return true;
        }

        return false;
      },
      extractInputNodes(node) {
        return node.getConnections().filter(c => c.input.node === node).map(c => c.output.node);
      },
      detect(inboundСonnection) {
        // console.log(window.engine.detectRecursions(editor.toJSON().nodes));
        const { input, output } = inboundСonnection;

        return input.node === output.node || this.findSelf(input.node, this.extractInputNodes(output.node));
    }
}

editor.use(RecursionPlugin);

But removed connection before connect() is lost

[petrkrejci1]

        const { input, output } = inboundСonnection;

        return input.node === output.node || this.findSelf(input.node, this.extractInputNodes(output.node));

Regarding of node self connection (output -> input of the same node is connected). I used another approach that does not allows creating connection at all thus there is no removing of the existing one on the input (in case of input.multipleConnections = false).

Here is how I achieve it in picker.js:

  pickInput(input) {
    let isRecursiveNodeConnection = false;

    if (this.output != undefined)
    isRecursiveNodeConnection = input.node.id == this.output.node.id ? true : false;

    if (this.output === null) {
      if (input.hasConnection()) {
        this.output = input.connections[0].output;
        this.editor.removeConnection(input.connections[0]);
      }
      return true;
    }

    if (!input.multipleConnections && input.hasConnection() && !isRecursiveNodeConnection)
      this.editor.removeConnection(input.connections[0]);

    if (!this.output.multipleConnections && this.output.hasConnection())
      this.editor.removeConnection(this.output.connections[0]);

    if (this.output.connectedTo(input)) {
      var connection = input.connections.find(c => c.output === this.output);

      this.editor.removeConnection(connection);
    }

    if (!isRecursiveNodeConnection) {
      this.editor.connect(this.output, input);
      this.reset();
    }
  }

But the problem still remains for the case when connecting to different node that already has connection on it's input.

[Ni55aN]

@petrkrejci1 will the recursion be correctly defined when the old connection has not yet been deleted?

[petrkrejci1]

@petrkrejci1 will the recursion be correctly defined when the old connection has not yet been deleted?

Yes, it will be detected before the connection is made by following condition:

if (this.output != undefined)
isRecursiveNodeConnection = input.node.id == this.output.node.id ? true : false;

But this works only for case when connecting node to itself. Connections among other nodes are bit trickier. It is great that we checking recursion on 'connectioncreate' event in RecursionPlugin you wrote, but we also need to somehow suppress clicking on input of the node when trying to creating recursive connection. If we skip event of clicking on the node's input, we will be able to cancel removing of existing connections that is not recursive and should stay in place.

I honestly do not know how to achieve it. So here are pictures to show the case I am thinking about.
Step 1: https://drive.google.com/open?id=1mgukXhfenzyro22lgoNp6DNJxzDQFATS
Step 2: https://drive.google.com/open?id=1dBbuczP5HXscJNdDYRh2U5XqOHD5CK6k
Step 3: https://drive.google.com/open?id=16A5qbrbhR2OLZ708me-asKCzXvbtp-Xn

... in step 3 you can see what I mean. Missing connection that should not be missing (noted in red).

@Ni55aN Do you thing we can do something about this issue? I am clueless to be honest.

[Ni55aN]

@petrkrejci1 you can save last connection on connectionremoved and restore it. But in some cases, false positives may occur due to manual removal of the connection.

[Ni55aN]

in v1.2.0-rc.1 you can import the Recursion class and export nodes to it

[Ni55aN]

More compact code:

const RecursionPlugin = {
    install(editor) {
      editor.on('connectioncreate', (c) => {
        const nodes = editor.toJSON().nodes;
        nodes[c.input.node.id].inputs[c.input.key].connections.push({ node: c.output.node.id, output: c.output.key })
        
        const recurrectNode = new Rete.Recursion(nodes).detect();
        
        if(recurrectNode) {
          alert('Connection removed due to recursion');
          return false;
        }
      });
    }
}

with restoring connection (and little hack - setTimeout)

const RecursionPlugin = {
    install(editor) {
      let lastConnection = null;
      
      editor.on('connectionremoved', c => {
        lastConnection = c;
        setTimeout(() => lastConnection = null, 0);
      });
          
      editor.on('connectioncreate', (c) => {
        const nodes = editor.toJSON().nodes;
        nodes[c.input.node.id].inputs[c.input.key].connections.push({ node: c.output.node.id, output: c.output.key })
        
        const recurrectNode = new Rete.Recursion(nodes).detect();
        
        if(recurrectNode) {
          alert('Connection removed due to recursion');
          if(lastConnection)
            editor.connect(lastConnection.output, lastConnection.input);
          return false;
        }
      });
    }
}

[petrkrejci1]

Thank you so much for your help and for this wonderful solution.