wurstscript / WurstScript / 271

Committed 29 Sep 2025 12:12PM UTC coverage: 64.649% (+2.4%) from 62.222%

Build # 271

Build Type

Pull #1096

circleci

Committed by

Frotty

Commit Message

Merge branch 'perf-improvements' of https://github.com/wurstscript/WurstScript into perf-improvements

Pull Request Pull Request #1096: Perf improvements

Run Details

18202 of 28155 relevant lines covered (64.65%)

0.65 hits per line

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

81.82

de.peeeq.wurstscript/src/main/java/de/peeeq/datastructures/GraphInterpreter.java

package de.peeeq.datastructures;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import de.peeeq.wurstscript.utils.Utils;
import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
import org.eclipse.jdt.annotation.Nullable;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public abstract class GraphInterpreter<T> {

    protected abstract Collection<T> getIncidentNodes(T t);

    public TopsortResult<T> topSort(List<T> nodes) {
        Set<T> seen = Sets.newHashSet();
        List<T> seenStack = Lists.newArrayList();
        List<T> result = Lists.newArrayList();

        for (T t : nodes) {
            if (!seen.contains(t)) {
                @Nullable TopsortResult<T> r = topSort_add(result, seen, seenStack, t);
                if (r != null) {
                    return r;
                }
            }
        }
        return new TopsortResult<>(false, result);
    }

    private @Nullable TopsortResult<T> topSort_add(List<T> result, Set<T> seen, List<T> seenStack, T n) {
        for (int i = seenStack.size() - 1; i >= 0; i--) {
            if (seenStack.get(i) == n) {
                // cycle
                return new TopsortResult<>(true, Utils.subList(seenStack, i));
            }
        }
        if (!seen.contains(n)) {
            seenStack.add(n);
            for (T m : getIncidentNodes(n)) {
                TopsortResult<T> r = topSort_add(result, seen, seenStack, m);
                if (r != null) {
                    return r;
                }
            }
            seenStack.remove(seenStack.size() - 1);
            seen.add(n);
            result.add(n);
        }
        return null;
    }

    public static class TopsortResult<T> {
        private final boolean isCycle;
        private final List<T> result;

        public TopsortResult(boolean isCycle, List<T> result) {
            this.isCycle = isCycle;
            this.result = result;
        }

        public boolean isCycle() {
            return isCycle;
        }

        public List<T> getResult() {
            return result;
        }
    }

    /**
     * Like topsort, but will find bigger cycles.
     * This is an iterative implementation of the path-based strong component algorithm
     * to prevent StackOverflowErrors on deep graphs.
     * <p>
     * See https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm
     */
    public List<List<T>> findStronglyConnectedComponents(List<T> nodes) {
        Deque<T> s = new ArrayDeque<>(); // S stack
        Deque<T> p = new ArrayDeque<>(); // P stack

        int preorderCounter = 0;
        int componentCounter = 0;

        Object2IntLinkedOpenHashMap<T> preorder = new Object2IntLinkedOpenHashMap<>();
        preorder.defaultReturnValue(-1);
        Object2IntLinkedOpenHashMap<T> compId = new Object2IntLinkedOpenHashMap<>();
        compId.defaultReturnValue(-1);

        Deque<T> frameStack = new ArrayDeque<>();         // simulated recursion
        Map<T, Iterator<T>> childIters = new HashMap<>(); // per-node child iterators

        List<List<T>> sccs = new ArrayList<>();

        for (T start : nodes) {
            if (preorder.getInt(start) != -1) continue;

            frameStack.push(start);
            while (!frameStack.isEmpty()) {
                T v = frameStack.peek();

                // First time at v
                if (preorder.getInt(v) == -1) {
                    preorder.put(v, preorderCounter++);
                    s.push(v);
                    p.push(v);
                    childIters.put(v, getIncidentNodes(v).iterator());
                }

                boolean descended = false;
                Iterator<T> it = childIters.get(v);

                while (it.hasNext()) {
                    T w = it.next();
                    int preW = preorder.getInt(w);
                    if (preW == -1) {
                        frameStack.push(w);
                        descended = true;
                        break;
                    } else if (compId.getInt(w) == -1) {
                        // w discovered but not assigned; shrink P
                        while (!p.isEmpty() && preorder.getInt(p.peek()) > preW) {
                            p.pop();
                        }
                    }
                }

                if (descended) continue;

                // Post-order for v
                frameStack.pop();
                childIters.remove(v);

                if (!p.isEmpty() && p.peek() == v) {
                    int newCid = componentCounter++;
                    ArrayList<T> cur = new ArrayList<>();
                    while (true) {
                        T x = s.pop();
                        compId.put(x, newCid);
                        cur.add(x);
                        if (x == v) break;
                    }
                    p.pop();

                    // Gabow emits SCCs in reverse-topological order
                    sccs.add(cur);
                }
            }
        }

        return sccs;
    }

    public String generateDotFile(List<T> nodes) {
        StringBuilder sb = new StringBuilder();
        Set<T> visited = new HashSet<>();
        Deque<T> todo = new ArrayDeque<>(nodes);
        sb.append("digraph G{\n");
        while (!todo.isEmpty()) {
            T node = todo.removeFirst();
            if (!visited.add(node)) {
                continue;
            }
            sb.append("  \"").append(node).append("\";\n");
            for (T n : getIncidentNodes(node)) {
                sb.append("  ");
                sb.append("\"").append(node).append("\" -> ");
                sb.append("\"").append(n.toString()).append("\";\n\n");
                todo.addFirst(n);
            }
        }
        sb.append("}\n");
        return sb.toString();
    }
}

1	package de.peeeq.datastructures;
2
3	import com.google.common.collect.ImmutableSet;
4	import com.google.common.collect.Lists;
5	import com.google.common.collect.Sets;
6	import de.peeeq.wurstscript.utils.Utils;
7	import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
8	import org.eclipse.jdt.annotation.Nullable;
9
10	import java.util.*;
11	import java.util.concurrent.atomic.AtomicInteger;
12
13	public abstract class GraphInterpreter<T> {	1✔
14
15	protected abstract Collection<T> getIncidentNodes(T t);
16
17	public TopsortResult<T> topSort(List<T> nodes) {
18	Set<T> seen = Sets.newHashSet();	1✔
19	List<T> seenStack = Lists.newArrayList();	1✔
20	List<T> result = Lists.newArrayList();	1✔
21
22	for (T t : nodes) {	1✔
23	if (!seen.contains(t)) {	1✔
24	@Nullable TopsortResult<T> r = topSort_add(result, seen, seenStack, t);	1✔
25	if (r != null) {	1✔
26	return r;	1✔
27	}
28	}
29	}	1✔
30	return new TopsortResult<>(false, result);	1✔
31	}
32
33	private @Nullable TopsortResult<T> topSort_add(List<T> result, Set<T> seen, List<T> seenStack, T n) {
34	for (int i = seenStack.size() - 1; i >= 0; i--) {	1✔
35	if (seenStack.get(i) == n) {	1✔
36	// cycle
37	return new TopsortResult<>(true, Utils.subList(seenStack, i));	1✔
38	}
39	}
40	if (!seen.contains(n)) {	1✔
41	seenStack.add(n);	1✔
42	for (T m : getIncidentNodes(n)) {	1✔
43	TopsortResult<T> r = topSort_add(result, seen, seenStack, m);	1✔
44	if (r != null) {	1✔
45	return r;	1✔
46	}
47	}	1✔
48	seenStack.remove(seenStack.size() - 1);	1✔
49	seen.add(n);	1✔
50	result.add(n);	1✔
51	}
52	return null;	1✔
53	}
54
55	public static class TopsortResult<T> {
56	private final boolean isCycle;
57	private final List<T> result;
58
59	public TopsortResult(boolean isCycle, List<T> result) {	1✔
60	this.isCycle = isCycle;	1✔
61	this.result = result;	1✔
62	}	1✔
63
64	public boolean isCycle() {
65	return isCycle;	1✔
66	}
67
68	public List<T> getResult() {
69	return result;	1✔
70	}
71	}
72
73	/**
74	* Like topsort, but will find bigger cycles.
75	* This is an iterative implementation of the path-based strong component algorithm
76	* to prevent StackOverflowErrors on deep graphs.
77	* <p>
78	* See https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm
79	*/
80	public List<List<T>> findStronglyConnectedComponents(List<T> nodes) {
81	Deque<T> s = new ArrayDeque<>(); // S stack	1✔
82	Deque<T> p = new ArrayDeque<>(); // P stack	1✔
83
84	int preorderCounter = 0;	1✔
85	int componentCounter = 0;	1✔
86
87	Object2IntLinkedOpenHashMap<T> preorder = new Object2IntLinkedOpenHashMap<>();	1✔
88	preorder.defaultReturnValue(-1);	1✔
89	Object2IntLinkedOpenHashMap<T> compId = new Object2IntLinkedOpenHashMap<>();	1✔
90	compId.defaultReturnValue(-1);	1✔
91
92	Deque<T> frameStack = new ArrayDeque<>(); // simulated recursion	1✔
93	Map<T, Iterator<T>> childIters = new HashMap<>(); // per-node child iterators	1✔
94
95	List<List<T>> sccs = new ArrayList<>();	1✔
96
97	for (T start : nodes) {	1✔
98	if (preorder.getInt(start) != -1) continue;	1✔
99
100	frameStack.push(start);	1✔
101	while (!frameStack.isEmpty()) {	1✔
102	T v = frameStack.peek();	1✔
103
104	// First time at v
105	if (preorder.getInt(v) == -1) {	1✔
106	preorder.put(v, preorderCounter++);	1✔
107	s.push(v);	1✔
108	p.push(v);	1✔
109	childIters.put(v, getIncidentNodes(v).iterator());	1✔
110	}
111
112	boolean descended = false;	1✔
113	Iterator<T> it = childIters.get(v);	1✔
114
115	while (it.hasNext()) {	1✔
116	T w = it.next();	1✔
117	int preW = preorder.getInt(w);	1✔
118	if (preW == -1) {	1✔
119	frameStack.push(w);	1✔
120	descended = true;	1✔
121	break;	1✔
122	} else if (compId.getInt(w) == -1) {	1✔
123	// w discovered but not assigned; shrink P
124	while (!p.isEmpty() && preorder.getInt(p.peek()) > preW) {	1✔
125	p.pop();	1✔
126	}
127	}
128	}	1✔
129
130	if (descended) continue;	1✔
131
132	// Post-order for v
133	frameStack.pop();	1✔
134	childIters.remove(v);	1✔
135
136	if (!p.isEmpty() && p.peek() == v) {	1✔
137	int newCid = componentCounter++;	1✔
138	ArrayList<T> cur = new ArrayList<>();	1✔
139	while (true) {
140	T x = s.pop();	1✔
141	compId.put(x, newCid);	1✔
142	cur.add(x);	1✔
143	if (x == v) break;	1✔
144	}	1✔
145	p.pop();	1✔
146
147	// Gabow emits SCCs in reverse-topological order
148	sccs.add(cur);	1✔
149	}
150	}	1✔
151	}	1✔
152
153	return sccs;	1✔
154	}
155
156	public String generateDotFile(List<T> nodes) {
157	StringBuilder sb = new StringBuilder();	×
158	Set<T> visited = new HashSet<>();	×
159	Deque<T> todo = new ArrayDeque<>(nodes);	×
160	sb.append("digraph G{\n");	×
161	while (!todo.isEmpty()) {	×
162	T node = todo.removeFirst();	×
163	if (!visited.add(node)) {	×
164	continue;	×
165	}
166	sb.append(" \"").append(node).append("\";\n");	×
167	for (T n : getIncidentNodes(node)) {	×
168	sb.append(" ");	×
169	sb.append("\"").append(node).append("\" -> ");	×
170	sb.append("\"").append(n.toString()).append("\";\n\n");	×
171	todo.addFirst(n);	×
172	}	×
173	}	×
174	sb.append("}\n");	×
175	return sb.toString();	×
176	}
177	}

wurstscript / WurstScript / 271

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