[Pester 4.0.3] Call depth overflow on $xmlObject | Should be $xmlObject

[alx9r]

Repro

Describe 'overflow' {
    It '[xml] object is itself.' {
        $doc = [xml]''
        $doc | Should be $doc
    }
}

Expected Result

I expected this test to pass. It passes using Pester 3.4.3.

Actual Result

Describing overflow
  [-] [xml] object is itself. 45.77s
    The script failed due to call depth overflow.
    at <ScriptBlock>, : line 4
    4:         $doc | Should be $doc

Environment

PS C:\> $PSVersionTable

Name                           Value                      
----                           -----                      
PSVersion                      5.1.14409.1005             
PSEdition                      Desktop                    
PSCompatibleVersions           {1.0, 2.0, 3.0, 4.0...}    
BuildVersion                   10.0.14409.1005            
CLRVersion                     4.0.30319.42000            
WSManStackVersion              3.0                        
PSRemotingProtocolVersion      2.3                        
SerializationVersion           1.1.0.1                    

PS C:\> Get-Module Pester

ModuleType Version    Name                                
---------- -------    ----                                
Script     4.0.3      Pester                              

[alx9r]

The problem seems to manifest in this recursive call in ArraysAreEqual. Here is a repro directly calling ArraysAreEqual:

InModuleScope Pester {
    Describe ArraysAreEqual {
        It '[xml] object is itself.' {
            $doc = [xml]''
            ArraysAreEqual -First $doc -Second $doc
        }
    }
}

[alx9r]

I think the original repro does not fail with Pester 3.4.3 because 3.4.3 predates array comparison. As of 2541ef9 Pester seems to treat most IEnumerables the same as arrays for comparison.

I think that might not be a great strategy. It looks to me like ArraysAreEqual uses the subscript operator to iterate into and compare the "Expected" and "Actual" arrays passed to Should. I'm not aware of there being much of a relationship between an object being IEnumerable and what, exactly, the subscript operator returns.

[alx9r]

I think this could be adequately mitigated by implementing a recursion limit that, when reached, throws an understandable error. That would cause a fast failure instead of pinning one CPU until a call depth overflow occurs. The call depth overflow can take minutes to occur, so a fast failure would be a significant improvement.

[nohwnd]

@alx9r Been looking at this to see if there is a simple way of seeing what PowerShell wraps in @() but if I get the login of the compiler correctly, it does a lot of work to identify which implementations of IEnumerable should be considered collections.

For the Should assertion we need to identify a simple set of rules that covers the majority of cases, and can be immediately understood. In the end comparing the arrays as part of Be is a convenience thing. I would suggest changing the collection check to inheriting from Array, which covers 90% of the collections a powersheller encounters, or moving the behavior to a new assertion alltogether.

Thoughts?

[nohwnd]

One thing that I also tried was simply checking the result of @() to see if the value remained the same, but Object.ReferenceEquals does not work in this case, because the reference changes and the result is always $false.

[alx9r]

@nohwnd I don't think the cause of the infinite recursion involves whether a collection is considered enumerable. Given the current algorithm's dependence on indexing into the collection, I think the most appropriate test would be for the IList interface. That's the framework interface customarily used to access items by index.

Here's a test of a bunch of collections I've encountered using PowerShell:

Describe 'IList' {
    $h= @{}
    foreach ( $values in  @(
        @($false,$true,(New-Object string 'TenTwentyThirty')),
        @($true,$true,([System.Collections.ArrayList]@(10,20,30))),
        @($false,$false,(New-Object System.Collections.BitArray 16)),
        @($false,$false,([System.Collections.Hashtable]@{ten=10;twenty=20;thirty=30})),
        @($false,$true,([System.Collections.Queue]@(10,20,30))),
        @($false,$false,([System.Collections.SortedList]@{ten=10;twenty=20;thirty=30})),
        @($false,$true,([System.Collections.Stack]@(10,20,30))),
        @($false,$false,(& {
            $d = New-Object "System.Collections.Generic.Dictionary``2[System.String,int32]"
            ('ten',10),('twenty',20),('thirty',30) | % {$d.Add($_[0],$_[1])}
            $d
        })),
        @($true,$true,(& {
            $l = New-Object "System.Collections.Generic.Queue``1[int32]"
            10,20,30 | % {$l.Enqueue($_)}
            $l
        })),
        @($true,$true,(& {
            $l = New-Object "System.Collections.Generic.List``1[int32]"
            10,20,30 | % {$l.Add($_)}
            $l
        })),
        @($false,$false,([xml]''))
    ))
    {
        $isIList,$subscriptWorks,$object = $values
        $type = $object.GetType()
        Context "$($type.Name), $($type.BaseType)" {
            It "$isIList, is IList" {
                [bool]$type.GetInterface('IList') | Should be $isIList            
            }
            It "$subscriptWorks, subscript operator returns something" {
                [bool]$object[0] | Should be $subscriptWorks
            }
        }
    }
}

I think .GetInterface('IList') tells us what we need to know. I've opened #824 with the fixes I had in mind.

[nohwnd]

@alx9r Revisited the problem and I think my implementation is correct, pls review :)

It does matter, because when there is mismatch between what we consider a collection and what powershell considers a collection, then on the recursive call we wrap the object in an array, then we unwrap it, incorrectly mark it as an array and call ArraysAreEqual, it wraps it in array, then unwraps it again, calls ArraysAreEqual and so on ad-infinitum.

This implementation highlights the problem. The [xml] type is IEnumerable, and so the implementation chokes.

function IsCollection ($o) {
    $o -isnot [string] -and $o -is [Collections.IEnumerable] 
}

function ArraysAreEqual ([object[]] $o, $i=0) {    
    "Call $i"
    "Object is: " + $o.GetType().FullName
    $first = $o[0]
    "First is: " + $first.GetType().FullName

    if ($i -gt 2) { throw "call is recursive" }
    if (IsCollection $first) 
    {
        ArraysAreEqual  $first (++$i)
    }
}

"`nUsing Int:"
ArraysAreEqual 1
"`n`nUsing String:"
# this would have failed but we explicitly exclude string
# in IsCollection function
ArraysAreEqual "abc" 
"`n`nUsing Array:"
ArraysAreEqual 1,2,3
"`n`nUsing List:"
ArraysAreEqual ([System.Collections.Generic.List[int]]@(1,2,3))
"`n`nUsing XmlDocument:"
ArraysAreEqual ([xml]'')

You can trigger overflow on string as well if you remove it from the IsCollection function, in fact you can make it choke on int as well, or any non-collection type, if you just return $true from the IsCollection function. Collections types will try to unwrap till they hit a non-collection type, and then it chokes again.

Now if you try and take different collections and enumerable types and cast them to [object[]] as the paramter does, you will get [object[]], but the conversion is clever the same way @() is clever . It correctly wraps values that are enumerable but not considered collections in an array, and does not wrap values that already are collections. So inside of the IsCollection function it really is sufficient to check for array, because that is what we will ever get.

So the fixed code should be what is currently in the master:

function IsCollection ($o) {
    $o -is [array]
}

function ArraysAreEqual ([object[]] $o, $i=0) {    
    "Call $i"
    "Object is: " + $o.GetType().FullName
    $first = $o[0]
    "First is: " + $first.GetType().FullName

    if ($i -gt 2) { throw "call is recursive" }
    if (IsCollection $first) 
    {
        ArraysAreEqual  $first (++$i)
    }
}

$innerList = [System.Collections.Generic.List[string]]("hello", "its", "me")
$list = [System.Collections.Generic.List[System.Collections.Generic.List[string]]]$innerList
ArraysAreEqual $list

Unless we want to consider types that Powershell does not consider collections as collections (say Dictionary).

[alx9r]

@nohwnd I think your analysis is correct. I misunderstood how that algorithm was expected to work. This leaves me with two remaining concerns: Naming and cyclic object graphs.

Shouldn't IsCollection really be named IsArray? Termination of ArraysAreEqual seems to depend very much on testing for precisely whatever conversion to [object[]] creates. It seems like that should be reflected in the function name.

The specter of infinite recursion seems to remain for cyclic object graphs. The head of master currently fails by call depth overflow on this:

$a1 = @(0,1)
$a2 = @($a1,2)
$a1[0] = $a2
$a1 | Should be $a2

Because of this I think there ought to be a self-imposed recursion limit.

I've updated PR #824 with all of this in mind. Let me know what you think.

[nohwnd]

Don't worry, took me quite a few looks before I understood why precisely it breaks :) Yes, IsArray is a better name, and I think we should put a short explanation and link to this issue there as well. The self imposed recursion limit is a good idea, I did not like it at first, but I didn't realize how simple it is to create cyclic arrays :) ( the recursion limit seems to be over 5000 calls on my computer, so it takes a while till it hangs/throws. ) 100 seems to be enough, as we can reasonably expect that people won't be creating 100 layer arrays on purpose. I would just make the error message more descriptive, but that can be fixed by someone else. And I would make the recursion depth parameter explicit in the function and make it default to 0, to avoid get-variable.

[alx9r]

Those all look like good recommendations. Thank you.

[it-praktyk]

@nohwnd, @alx9r I've followed your discussion and I'm little confused if the 631ef02 addresses

I would just make the error message more descriptive, but that can be fixed by someone else.

or should be added/changed something more.

[alx9r]

@it-praktyk That suggestion prompted this change, but I'm not sure exactly what @nohwnd had in mind.

[nohwnd]

@it-praktyk The error seems fine now, the small suggestion of what probably have happened is what I was looking for 👍
@alx9r You forgot to propagate the recursion limit to the subsequent calls so it would always stay 100 after the first call. I fixed that, then some casing and spacing and merged. Thanks :)

[alx9r]

@nohwd Oh right. Nice spot. Thanks for the merge. :)