Why is linq executing the same code twice depending on where I put ToList?

Question

When I call the following function:

public ICombatTransaction PayCost(CostTransaction costTransaction)
{
    if (costTransaction.Cost is CompositeAndCost compositeAndCost)
    {
        var res = compositeAndCost.Costs.Select(cost => PayCost(new CostTransaction(costTransaction.Source, cost, costTransaction, this)));

        if (res.All(t => t.IsFulfilled))
            return new CompositeFulfilledTransaction(res.ToList(), costTransaction, this);

        throw new Exception($"Composite 'and' system cannot pay ({string.Join(", ", res.Where(x => !x.IsFulfilled).Select(x => ((CostTransaction)x).Cost.GetType()))}) costs");
    }
    else
    {
        foreach (var costSystem in CostSystems)
            if (costSystem.Accepts(costTransaction.Cost.GetType()))
                return costSystem.PayCost(costTransaction);

        return costTransaction;
    }
}

The recursive PayCost call in line 5 ends up getting called twice for each element in compositeAndCost.Costs. This is not intentional. Simply moving the ToList from under the if statement to above it resolves this problem entirely:

public ICombatTransaction PayCost(CostTransaction costTransaction)
{
    if (costTransaction.Cost is CompositeAndCost compositeAndCost)
    {
        var res = compositeAndCost.Costs.Select(cost => PayCost(new CostTransaction(costTransaction.Source, cost, costTransaction, this))).ToList();

        if (res.All(t => t.IsFulfilled))
            return new CompositeFulfilledTransaction(res, costTransaction, this);

        throw new Exception($"Composite 'and' system cannot pay ({string.Join(", ", res.Where(x => !x.IsFulfilled).Select(x => ((CostTransaction)x).Cost.GetType()))}) costs");
    }
    else
    {
        foreach (var costSystem in CostSystems)
            if (costSystem.Accepts(costTransaction.Cost.GetType()))
                return costSystem.PayCost(costTransaction);

        return costTransaction;
    }
}

This is one of the strangest C# bugs I've ever seen, I haven't seen anything like it in like 7 years of working with C# and Linq. I'm sure it's because of lazy evaluation (which I didn't know C# just did sometimes!) but I still don't understand the mechanism that leads to calling a function twice, and I don't understand why it isn't resolving to a list when res.All is called.

My concrete questions are 1. what's the exact mechanism that leads to calling the function twice and 2. what should I be thinking about/paying attention to in order to avoid this kind of bug when using linq?

Answer 1

I had same problem. LinQ select return IEnumerable. It means, that it's not loading data until you need to access it. For example if you have database 'MyDbContext' with table 'Data'. Then in some method you use it:

var records = MyDbContext.Data.Select(o=>o.Id>10); // this not loading data to records
var count = records.Count(); // here all query data is loaded from DB and returns count.
var secondCount = records.Count() // here again data is loaded from DB and returns count. 

but if you change first line to:

var records = MyDbContext.Data.Select(o=>o.Id>10).ToList();

then data from database would be loaded once. Because ToList() creates an object with data. So when you need to make several manipulations with same data, like counting, sorting and etc. it is better to load it to list or array.