11382959677

Committed 17 Oct 2024 10:17AM UTC coverage: 55.74% (-0.2%) from 55.924%

Build # 11382959677

Build Type

Pull #3521

github

Committed by

web-flow

Commit Message

Merge 97bcd019b into bb71676fd

Pull Request Pull Request #3521: Handle https://github.com/neo-project/neo/pull/3520

Run Details

5748 of 8916 branches covered (64.47%)

Branch coverage included in aggregate %.

9 of 9 new or added lines in 2 files covered. (100.0%)

64 existing lines in 4 files now uncovered.

21682 of 40295 relevant lines covered (53.81%)

86429.61 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

10.43

/src/Neo.VM/StronglyConnectedComponents/Tarjan.cs

// Copyright (C) 2015-2024 The Neo Project.
//
// Tarjan.cs file belongs to the neo project and is free
// software distributed under the MIT software license, see the
// accompanying file LICENSE in the main directory of the
// repository or http://www.opensource.org/licenses/mit-license.php
// for more details.
//
// Redistribution and use in source and binary forms with or without
// modifications are permitted.

using System;
using System.Collections.Generic;
using T = Neo.VM.Types.StackItem;

namespace Neo.VM.StronglyConnectedComponents
{
    class Tarjan
    {
        private readonly IEnumerable<T> vertexs;
        private readonly LinkedList<HashSet<T>> components = new();
        private readonly Stack<T> stack = new();
        private int index = 0;

        public Tarjan(IEnumerable<T> vertexs)
        {
            this.vertexs = vertexs;
        }

        public LinkedList<HashSet<T>> Invoke()
        {
            foreach (var v in vertexs)
            {
                if (v.DFN < 0)
                {
                    StrongConnectNonRecursive(v);
                }
            }
            return components;
        }

        private void StrongConnect(T v)
        {
            v.DFN = v.LowLink = ++index;
            stack.Push(v);
            v.OnStack = true;

            foreach (T w in v.Successors)
            {
                if (w.DFN < 0)
                {
                    StrongConnect(w);
                    v.LowLink = Math.Min(v.LowLink, w.LowLink);
                }
                else if (w.OnStack)
                {
                    v.LowLink = Math.Min(v.LowLink, w.DFN);
                }
            }

            if (v.LowLink == v.DFN)
            {
                HashSet<T> scc = new(ReferenceEqualityComparer.Instance);
                T w;
                do
                {
                    w = stack.Pop();
                    w.OnStack = false;
                    scc.Add(w);
                } while (v != w);
                components.AddLast(scc);
            }
        }

        private void StrongConnectNonRecursive(T v)
        {
            Stack<(T node, T?, IEnumerator<T>?, int)> sstack = new();
            sstack.Push((v, null, null, 0));
            while (sstack.TryPop(out var state))
            {
                v = state.node;
                var (_, w, s, n) = state;
                switch (n)
                {
                    case 0:
                        v.DFN = v.LowLink = ++index;
                        stack.Push(v);
                        v.OnStack = true;
                        s = v.Successors.GetEnumerator();
                        goto case 2;
                    case 1:
                        v.LowLink = Math.Min(v.LowLink, w!.LowLink);
                        goto case 2;
                    case 2:
                        while (s!.MoveNext())
                        {
                            w = s.Current;
                            if (w.DFN < 0)
                            {
                                sstack.Push((v, w, s, 1));
                                v = w;
                                goto case 0;
                            }
                            else if (w.OnStack)
                            {
                                v.LowLink = Math.Min(v.LowLink, w.DFN);
                            }
                        }
                        if (v.LowLink == v.DFN)
                        {
                            HashSet<T> scc = new(ReferenceEqualityComparer.Instance);
                            do
                            {
                                w = stack.Pop();
                                w.OnStack = false;
                                scc.Add(w);
                            } while (v != w);
                            components.AddLast(scc);
                        }
                        break;
                }
            }
        }
    }
}

1	// Copyright (C) 2015-2024 The Neo Project.
2	//
3	// Tarjan.cs file belongs to the neo project and is free
4	// software distributed under the MIT software license, see the
5	// accompanying file LICENSE in the main directory of the
6	// repository or http://www.opensource.org/licenses/mit-license.php
7	// for more details.
8	//
9	// Redistribution and use in source and binary forms with or without
10	// modifications are permitted.
11
12	using System;
13	using System.Collections.Generic;
14	using T = Neo.VM.Types.StackItem;
15
16	namespace Neo.VM.StronglyConnectedComponents
17	{
18	class Tarjan
19	{
20	private readonly IEnumerable<T> vertexs;
21	private readonly LinkedList<HashSet<T>> components = new();	1✔
22	private readonly Stack<T> stack = new();	1✔
23	private int index = 0;	1✔
24
25	public Tarjan(IEnumerable<T> vertexs)	1✔
26	{	1✔
27	this.vertexs = vertexs;	1✔
28	}	1✔
29
30	public LinkedList<HashSet<T>> Invoke()
31	{	1✔
32	foreach (var v in vertexs)	3!
UNCOV 33	{	×
UNCOV 34	if (v.DFN < 0)	×
UNCOV 35	{	×
UNCOV 36	StrongConnectNonRecursive(v);	×
UNCOV 37	}	×
UNCOV 38	}	×
39	return components;	1✔
40	}	1✔
41
42	private void StrongConnect(T v)
43	{	×
44	v.DFN = v.LowLink = ++index;	×
45	stack.Push(v);	×
46	v.OnStack = true;	×
47
48	foreach (T w in v.Successors)	×
49	{	×
50	if (w.DFN < 0)	×
51	{	×
52	StrongConnect(w);	×
53	v.LowLink = Math.Min(v.LowLink, w.LowLink);	×
54	}	×
55	else if (w.OnStack)	×
56	{	×
57	v.LowLink = Math.Min(v.LowLink, w.DFN);	×
58	}	×
59	}	×
60
61	if (v.LowLink == v.DFN)	×
62	{	×
63	HashSet<T> scc = new(ReferenceEqualityComparer.Instance);	×
64	T w;
65	do
66	{	×
67	w = stack.Pop();	×
68	w.OnStack = false;	×
69	scc.Add(w);	×
70	} while (v != w);	×
71	components.AddLast(scc);	×
72	}	×
73	}	×
74
75	private void StrongConnectNonRecursive(T v)
UNCOV 76	{	×
UNCOV 77	Stack<(T node, T?, IEnumerator<T>?, int)> sstack = new();	×
UNCOV 78	sstack.Push((v, null, null, 0));	×
UNCOV 79	while (sstack.TryPop(out var state))	×
UNCOV 80	{	×
UNCOV 81	v = state.node;	×
UNCOV 82	var (_, w, s, n) = state;	×
UNCOV 83	switch (n)	×
84	{
85	case 0:
UNCOV 86	v.DFN = v.LowLink = ++index;	×
UNCOV 87	stack.Push(v);	×
UNCOV 88	v.OnStack = true;	×
UNCOV 89	s = v.Successors.GetEnumerator();	×
UNCOV 90	goto case 2;	×
91	case 1:
92	v.LowLink = Math.Min(v.LowLink, w!.LowLink);	×
93	goto case 2;	×
94	case 2:
UNCOV 95	while (s!.MoveNext())	×
96	{	×
97	w = s.Current;	×
98	if (w.DFN < 0)	×
99	{	×
100	sstack.Push((v, w, s, 1));	×
101	v = w;	×
102	goto case 0;	×
103	}
104	else if (w.OnStack)	×
105	{	×
106	v.LowLink = Math.Min(v.LowLink, w.DFN);	×
107	}	×
108	}	×
UNCOV 109	if (v.LowLink == v.DFN)	×
UNCOV 110	{	×
UNCOV 111	HashSet<T> scc = new(ReferenceEqualityComparer.Instance);	×
112	do
UNCOV 113	{	×
UNCOV 114	w = stack.Pop();	×
UNCOV 115	w.OnStack = false;	×
UNCOV 116	scc.Add(w);	×
UNCOV 117	} while (v != w);	×
UNCOV 118	components.AddLast(scc);	×
UNCOV 119	}	×
UNCOV 120	break;	×
121	}
UNCOV 122	}	×
UNCOV 123	}	×
124	}
125	}

neo-project / neo / 11382959677

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous