StackOverflow 发生且无明显递归

Question

我遇到 StackOverflowException 问题，但我看不到任何地方发生递归。

以下代码是 QR 码创建库的 SVG 生成例程的一部分。该代码在 Kotlin 中完美运行，但当我尝试将算法转换为 C# 时却无法运行。

考虑以下函数，它通过检查每个邻居并重复此过程直到找不到更多方块来找到黑色方块的连通区域。

private static HashSet<Point> GetPolygon(QRCode qr, Point point) {
    
    HashSet<Point> Polygon = new HashSet<Point>();
    HashSet<Point> NewPolygon = new HashSet<Point>();
    
    Polygon.Add(point);
    NewPolygon.Add(point);
    
    int OldSize = 0;
    int Size = 1;
    
    do {
        OldSize = Size;
        
        HashSet<Point> NewPolygonMapped = NewPolygon
            .SelectMany(it => it.Neighbors)
            .Where(it => !Polygon.Contains(it))
            .Where(it => qr.GetValue(it.x,it.y)==1)
            .ToHashSet();
            
        NewPolygon = NewPolygonMapped;
        Polygon.UnionWith(NewPolygon);
            
        Size = Polygon.Count;
    } while (Size > OldSize);
    
    return Polygon;
}

Point 类的相关部分是

class Point {
            
    public int x {get; private set;}
    public int y {get; private set;}
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public Point Right {get {return new Point(x+1,y);}}
    public Point Left {get {return new Point(x-1,y);}}
    public Point Above {get {return new Point(x,y-1);}}
    public Point Below {get {return new Point(x,y+1);}}
    
     public HashSet<Point> Neighbors {get {
         HashSet<Point> neighbors = new HashSet<Point>();
         neighbors.Add(this.Right);
         neighbors.Add(this.Left);
         neighbors.Add(this.Above);
         neighbors.Add(this.Below);
         return neighbors;
    }}
}

QRCode.GetValue(int,int) 方法返回 0 或 1。

GetPolygon 方法导致 StackOverflow。它似乎发生在 do-while 循环的第二次迭代上。我已经在多个版本中重写了它，试图解决这个问题，包括使用 foreach 循环。

我尝试过的事情

如果我修改，Point.Neighbors 只返回 1 个值：

public HashSet<Point> Neighbors {get {
     HashSet<Point> neighbors = new HashSet<Point>();
     neighbors.Add(this.Right);
     return neighbors;
}}

它工作得很好（虽然，显然没有找到正确的点集）。

将 Linq 代码更改为一组嵌套的 foreach 循环

HashSet<Point> NewPolygon2 = new HashSet<Point>();
foreach (Point p in NewPolygon) {
    foreach (Point n in p.Neighbors) {
        if (!Polygon.Contains(n) && qr.GetValue(p.x,p.y)==1) {
            NewPolygon2.Add(n);
        }
    }
}

NewPolygon = NewPolygon2;
Polygon.UnionWith(NewPolygon);

表现出相同的行为。

显然，某个地方发生了一些递归导致了stackoverflow异常，但我找不到它。

此循环的第一次递归将找到两个点。第二个会找到2个额外的点，所以这里不涉及数千个点。

新信息

看起来问题可能出在 Point 中的 GetHashCode 覆盖或 Equals 覆盖中。以下是它们的定义：

            public override int GetHashCode() {
                int hash = 13;
                hash = (hash * 7) + x.GetHashCode();
                hash = (hash * 7) + y.GetHashCode();
                return hash;
            }
            
            public override bool Equals(object obj) {
                var item = obj as Point;
                if (item==null) {return false;}
                else {
                    return (x==item.x && y==item.y);
                }
            }

Answer 1

这是由 Equals 和 GetHashCode 方法以及附加运算符中的重写引起的。我不确定，但 HashSet 可能使用 == 运算符来测试相等性。这些被定义（差）为

            public static bool operator== (Point obj1, Point obj2) {
                return ((obj1==null && obj2==null) || (obj1!=null && obj1.Equals(obj2)) || (obj2!=null && obj2.Equals(obj1)));
            }
            
            public static bool operator!= (Point obj1, Point obj2) {
                return !(obj1==obj2);
            }

在某些地方，这些可能会导致递归。删除这些方法（我实际上没有使用它们）并依赖 Equals 方法可以解决问题。

我会删除这个问题，但我确信其他人也会遇到这个问题，这是一个很好的提醒，在处理 HashSet 时检查你的相等性测试！这正是数据类和记录存在的原因（但我需要使用 C# 5 来完成此操作，并且不能依赖此处的那些）。