Add support for linked facts that span multiple activations and multiple rules

[uxmal]

I'm trying to implement a rule that is to generate the transitive closure of a relation. I have the following fact class:

    public class SubTypeConstraint
    {
        public SubTypeConstraint(TypeVariable subType, TypeVariable superType)
        {
            this.SubType = subType;
            this.SuperType = superType;
        }

        public TypeVariable SubType { get; }
        public TypeVariable SuperType { get; }

        public override string ToString() => $"{SubType} ⊑ {SuperType}";

        public override bool Equals(object obj)
        {
            if (obj is not SubTypeConstraint that)
                return false;
            return this.SubType == that.SubType &&
                this.SuperType == that.SuperType;
        }

        public override int GetHashCode()
        {
            return SubType.GetHashCode() ^ 31 * SuperType.GetHashCode();
        }
    }

and a rule that expresses transitivity:

        public override void Define()
        {
            // If a ⊑ b && b ⊑ c, then a ⊑ c
            SubTypeConstraint sub1 = default!;
            SubTypeConstraint sub2 = default!;
            When()
                .Match<SubTypeConstraint>(() => sub1)
                .Match<SubTypeConstraint>(() => sub2, s => sub1.SuperType == s.SubType);
            Then()
                .Yield(c => new SubTypeConstraint(sub1.SubType, sub2.SuperType));
        }

The idea is that if two SubTypeContstraints are found that march the transitive relation, then a new fact should be yielded and added to the knowledge base. When I run this query:

            var tvA = new TypeVariable("A");
            var tvB = new TypeVariable("B");
            var tvC = new TypeVariable("C");
            var tvD = new TypeVariable("D");
            session.Insert(new SubTypeConstraint(tvA, tvB));
            session.Insert(new SubTypeConstraint(tvB, tvC));
            session.Insert(new SubTypeConstraint(tvC, tvD));
            session.Fire();

I get the following exception:

This exception was originally thrown at this call stack:
    System.ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException<T>(T)
    System.Collections.Generic.Dictionary<TKey, TValue>.TryInsert(TKey, TValue, System.Collections.Generic.InsertionBehavior)
    System.Collections.Generic.Dictionary<TKey, TValue>.Add(TKey, TValue)
    NRules.WorkingMemory.AddFact(NRules.Rete.Fact)
    NRules.WorkingMemory.AddLinkedFact(NRules.Activation, object, NRules.Rete.Fact)
    NRules.Session.QueueInsertLinked(NRules.Activation, System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<object, object>>)
    NRules.ActionContext.InsertAllLinked(System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<object, object>>)
    NRules.ActionContext.InsertLinked(object, object)
    NRules.RuleAction.Invoke(NRules.IExecutionContext, NRules.IActionContext)
    NRules.ActionExecutor.Execute(NRules.IExecutionContext, NRules.IActionContext)

How can I generate the transitive closure of my relation using the rule? Do I explicitly have to check that a fact doesn't exist before Yielding it?

[snikolayev]

Linked facts (those produced by the Yield clause) are managed at the activation level. An activation is a single set of facts matched by a given rule. In your case, it's a pair of SubTypeConstraint objects that satisfy the rule's conditions. The idea is that the linked fact yielded by a given activation is automatically inserted/updated by the engine, depending on whether it already exists or not.
In your case, however, you have two different activations producing the same exact linked fact, and that's what's causing the duplicate fact exception.
I updated your rule to demonstrate what's going on:

public class TransitiveClosureRule : Rule
{
    public override void Define()
    {
        // If a ⊑ b && b ⊑ c, then a ⊑ c
        SubTypeConstraint sub1 = default!;
        SubTypeConstraint sub2 = default!;
        When()
            .Match<SubTypeConstraint>(() => sub1)
            .Match<SubTypeConstraint>(() => sub2, s => sub1.SuperType == s.SubType);
        Then()
            .Yield(c => CreateConstraint(sub1, sub2));
    }

    private static SubTypeConstraint CreateConstraint(SubTypeConstraint sub1, SubTypeConstraint sub2)
    {
        var derivedConstraint = new SubTypeConstraint(sub1.SubType, sub2.SuperType);
        Console.WriteLine($"{sub1} && {sub2} -> {derivedConstraint}");
        return derivedConstraint;
    }
}

And it prints the following:

A ⊑ B && B ⊑ C -> A ⊑ C
B ⊑ C && C ⊑ D -> B ⊑ D
A ⊑ C && C ⊑ D -> A ⊑ D
A ⊑ B && B ⊑ D -> A ⊑ D

Here you can clearly see that two different matches of the rule yield the same output.

NRules does not natively support producing the same linked fact from multiple activations of the same rule or from different rules. It would need to do some sort of reference counting to support that. I think this is a good feature to support, so I'll keep this issue open, such that I can add this capability in the future.

As a workaround, you can use two rules and an intermediary fact:

public class CalculatedConstraint
{
    public TypeVariable SubType { get; }
    public TypeVariable SuperType { get; }

    public CalculatedConstraint(TypeVariable subType, TypeVariable superType)
    {
        SubType = subType;
        SuperType = superType;
    }
}

public class TransitiveClosureCalculationRule : Rule
{
    public override void Define()
    {
        // If a ⊑ b && b ⊑ c, then a ⊑ c
        SubTypeConstraint sub1 = default!;
        SubTypeConstraint sub2 = default!;
        When()
            .Match<SubTypeConstraint>(() => sub1)
            .Match<SubTypeConstraint>(() => sub2, s => sub1.SuperType == s.SubType);
        Then()
            .Yield(c => new CalculatedConstraint(sub1.SubType, sub2.SuperType));
    }
}

public class TransitiveClosureYieldRule : Rule
{
    public override void Define()
    {
        IEnumerable<CalculatedConstraint> constraints = default!;
        When()
            .Query(() => constraints, q => q
                .Match<CalculatedConstraint>()
                .GroupBy(x => new {x.SubType, x.SuperType}));
        Then()
            .Yield(c => new SubTypeConstraint(constraints.First().SubType, constraints.First().SuperType));
    }
}