Linux GNU 11.4.0 Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 89.1% 238 / 0 / 267
Functions: -% 0 / 1 / 1
Branches: 79.6% 172 / 0 / 216
OMCompiler/Compiler/NBackEnd/Modules/1_Main/NBSorting.mo
Line Branch Exec Source
1 /*
2 * This file is part of OpenModelica.
3 *
4 * Copyright (c) 1998-2026, Open Source Modelica Consortium (OSMC),
5 * c/o Linköpings universitet, Department of Computer and Information Science,
6 * SE-58183 Linköping, Sweden.
7 *
8 * All rights reserved.
9 *
10 * THIS PROGRAM IS PROVIDED UNDER THE TERMS OF AGPL VERSION 3 LICENSE OR
11 * THIS OSMC PUBLIC LICENSE (OSMC-PL) VERSION 1.8.
12 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS PROGRAM CONSTITUTES
13 * RECIPIENT'S ACCEPTANCE OF THE OSMC PUBLIC LICENSE OR THE GNU AGPL
14 * VERSION 3, ACCORDING TO RECIPIENTS CHOICE.
15 *
16 * The OpenModelica software and the OSMC (Open Source Modelica Consortium)
17 * Public License (OSMC-PL) are obtained from OSMC, either from the above
18 * address, from the URLs:
19 * http://www.openmodelica.org or
20 * https://github.com/OpenModelica/ or
21 * http://www.ida.liu.se/projects/OpenModelica,
22 * and in the OpenModelica distribution.
23 *
24 * GNU AGPL version 3 is obtained from:
25 * https://www.gnu.org/licenses/licenses.html#GPL
26 *
27 * This program is distributed WITHOUT ANY WARRANTY; without
28 * even the implied warranty of MERCHANTABILITY or FITNESS
29 * FOR A PARTICULAR PURPOSE, EXCEPT AS EXPRESSLY SET FORTH
30 * IN THE BY RECIPIENT SELECTED SUBSIDIARY LICENSE CONDITIONS OF OSMC-PL.
31 *
32 * See the full OSMC Public License conditions for more details.
33 *
34 */
35
36 encapsulated package NBSorting
37 "file: NBSorting.mo
38 package: NBSorting
39 description: This file contains the functions which perform the sorting process;
40 "
41
42 public
43 import StrongComponent = NBStrongComponent;
44
45 protected
46 // NB imports
47 import Adjacency = NBAdjacency;
48 import NBAdjacency.Mode;
49 import BEquation = NBEquation;
50 import NBEquation.{Equation, EquationPointers};
51 import BVariable = NBVariable;
52 import NBVariable.VariablePointers;
53 import Matching = NBMatching;
54
55 // NF imports
56 import ComponentRef = NFComponentRef;
57
58 // Util imports
59 import BackendUtil = NBBackendUtil;
60 import UnorderedMap;
61
62 public
63 // ############################################################
64 // Pseudo Bucket Structures
65 // ############################################################
66
67 uniontype Value
68 record SINGLE_VAL
69 ComponentRef cref_to_solve "cref to solve for in this mode";
70 list<Integer> eqn_scal_indices "indices of all scalarized equations that have to be solved that way";
71 end SINGLE_VAL;
72
73 record MULTI_VAL
74 list<ComponentRef> crefs_to_solve "crefs to solve for in this mode";
75 list<Integer> eqn_scal_indices "indices of all scalarized equations that have to be solved that way";
76 end MULTI_VAL;
77
78 function toString
79 input Value val;
80 output String str;
81 algorithm
82 str := match val
83 ✗ case SINGLE_VAL() then "\n\tval: (" + ComponentRef.toString(val.cref_to_solve) + ")";
84 ✗ case MULTI_VAL() then "\n\tval: " + List.toString(val.crefs_to_solve, ComponentRef.toString);
85 end match;
86 end toString;
87
88 function filter
89 input output Value val;
90 input UnorderedSet<Integer> set;
91 algorithm
92 val := match val
93
6/6
✓ Branch 1 taken 2282 times.
✓ Branch 2 taken 15228 times.
✓ Branch 3 taken 17510 times.
✓ Branch 4 taken 9336 times.
✓ Branch 5 taken 15228 times.
✓ Branch 6 taken 9336 times.
 36182 case SINGLE_VAL() algorithm val.eqn_scal_indices := list(idx for idx guard(not UnorderedSet.contains(idx, set)) in val.eqn_scal_indices); then val;
94
6/6
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 555 times.
✓ Branch 3 taken 600 times.
✓ Branch 4 taken 115 times.
✓ Branch 5 taken 555 times.
✓ Branch 6 taken 115 times.
 830 case MULTI_VAL() algorithm val.eqn_scal_indices := list(idx for idx guard(not UnorderedSet.contains(idx, set)) in val.eqn_scal_indices); then val;
95 end match;
96 end filter;
97
98 function getEquations
99 input Value val;
100 output list<Integer> eqn_scal_indices;
101 algorithm
102 eqn_scal_indices := match val
103 11446 case SINGLE_VAL() then val.eqn_scal_indices;
104 329 case MULTI_VAL() then val.eqn_scal_indices;
105 end match;
106 end getEquations;
107
108 end Value;
109
110 package PseudoBucket
111 // While collecting, a bucket accumulates its equations and crefs in pointers
112 // so that adding one costs a single cons.
113 type Bucket = tuple<Mode, Boolean, Pointer<list<Integer>>, Pointer<list<ComponentRef>>>;
114
115 function create
116 "recollects subsets of multi-dimensional equations that have to be solved in the same way.
117 currently only for loops!
118 The buckets of one array equation are found by its index instead of by
119 hashing the mode, which keys on the equation name only anyway."
120 input array<Integer> eqn_to_var "eqn to var matching";
121 input EquationPointers eqns;
122 input Adjacency.Mapping mapping "scalar <-> array index mapping";
123 input Adjacency.IntMatrix m "normal adjacency matrix, holding the mode ids";
124 input Adjacency.ModeTable modes;
125 output list<tuple<Mode, Value>> buckets = {};
126 protected
127 array<Integer> data = Adjacency.IntMatrix.entries(m);
128 array<Integer> ids = Adjacency.IntMatrix.payload(m);
129 array<list<Bucket>> per_eqn = arrayCreate(intMax(arrayLength(mapping.eqn_AtS), 1), {});
130 list<Bucket> order = {};
131 Option<Mode> mode_opt;
132 Mode mode;
133 ComponentRef cref;
134 Integer eqn_arr_idx;
135 Boolean multi, fresh;
136 Pointer<list<Integer>> idx_ptr;
137 Pointer<list<ComponentRef>> cref_ptr;
138 Value val;
139 algorithm
140 // add each equation to a bucket if solved the same way
141
1/2
✓ Branch 0 taken 1622 times.
✗ Branch 1 not taken.
 19853 for eqn_scal_idx in 1:arrayLength(eqn_to_var) loop
142 18231 mode_opt := Adjacency.Modes.get(modes, m, data, ids, eqn_scal_idx, eqn_to_var[eqn_scal_idx]);
143
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 18231 times.
✓ Branch 2 taken 18110 times.
✓ Branch 3 taken 121 times.
 18231 if isSome(mode_opt) then
144 18110 mode := Util.getOption(mode_opt);
145 18110 eqn_arr_idx := mapping.eqn_StA[eqn_scal_idx];
146 18110 multi := Equation.isRecordOrTupleEquation(EquationPointers.getEqnAt(eqns, eqn_arr_idx));
147 cref := ComponentRef.EMPTY();
148
2/2
✓ Branch 0 taken 600 times.
✓ Branch 1 taken 17510 times.
 18110 if multi then
149 // add the cref to the result, but remove it from the modes so all modes of a tuple equations are equal
150 600 cref := listHead(mode.crefs);
151 600 mode.crefs := {};
152 end if;
153
154 18110 (idx_ptr, cref_ptr, fresh) := getBucket(mode, multi, eqn_arr_idx, per_eqn);
155
2/2
✓ Branch 0 taken 9451 times.
✓ Branch 1 taken 8659 times.
 18110 if fresh then
156
2/2
✓ Branch 0 taken 9336 times.
✓ Branch 1 taken 115 times.
 18787 order := (mode, multi, idx_ptr, cref_ptr) :: order;
157 elseif multi then
158 970 Pointer.update(cref_ptr, cref :: Pointer.access(cref_ptr));
159 end if;
160 36220 Pointer.update(idx_ptr, eqn_scal_idx :: Pointer.access(idx_ptr));
161 end if;
162 end for;
163
164 // order holds the buckets newest first, prepending reverses it back
165
2/2
✓ Branch 0 taken 9451 times.
✓ Branch 1 taken 1622 times.
 11073 for bucket in order loop
166 9451 (mode, multi, idx_ptr, cref_ptr) := bucket;
167
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 9336 times.
 9451 if multi then
168 115 val := Value.MULTI_VAL(Pointer.access(cref_ptr), Pointer.access(idx_ptr));
169 else
170 9336 val := Value.SINGLE_VAL(listHead(mode.crefs), Pointer.access(idx_ptr));
171 end if;
172 9451 buckets := (mode, val) :: buckets;
173 end for;
174
175
1/2
✓ Branch 1 taken 1622 times.
✗ Branch 2 not taken.
 1622 if Flags.isSet(Flags.DUMP_SORTING) then
176 ✗ for bucket_tpl in buckets loop
177 ✗ (mode, val) := bucket_tpl;
178 ✗ print(Mode.toString(mode) + Value.toString(val) + "\n");
179 end for;
180 end if;
181 end create;
182
183 function getBucket
184 "Returns the accumulators of this mode's bucket, creating it if the array
185 equation does not have one for the mode yet."
186 input Mode mode;
187 input Boolean multi;
188 input Integer eqn_arr_idx;
189 input array<list<Bucket>> per_eqn;
190 output Pointer<list<Integer>> idx_ptr;
191 output Pointer<list<ComponentRef>> cref_ptr;
192 output Boolean fresh = false;
193 protected
194 Mode m;
195 Boolean mu;
196 algorithm
197
2/2
✓ Branch 1 taken 8775 times.
✓ Branch 2 taken 9451 times.
 18226 for bucket in per_eqn[eqn_arr_idx] loop
198 8775 (m, mu, idx_ptr, cref_ptr) := bucket;
199
3/4
✓ Branch 0 taken 8775 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 8659 times.
✓ Branch 4 taken 116 times.
 8775 if mu == multi and Mode.isEqual(m, mode) then
200 8659 return;
201 end if;
202 end for;
203 9451 idx_ptr := Pointer.create({});
204
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 9336 times.
 9451 cref_ptr := Pointer.create(if multi then mode.crefs else {});
205 fresh := true;
206
2/2
✓ Branch 0 taken 9336 times.
✓ Branch 1 taken 115 times.
 28238 arrayUpdate(per_eqn, eqn_arr_idx, (mode, multi, idx_ptr, cref_ptr) :: per_eqn[eqn_arr_idx]);
207 end getBucket;
208
209 function filter
210 "filters out the indices that are in in the set"
211 input output tuple<Mode, Value> tpl;
212 input UnorderedSet<Integer> set;
213 protected
214 Mode mode;
215 Value val;
216 algorithm
217 9451 (mode, val) := tpl;
218 9451 val := Value.filter(val, set);
219 9451 tpl := (mode, val);
220 end filter;
221
222 function relevant
223 "returns true if the value has more than one entry"
224 input tuple<Mode, Value> tpl;
225 output Boolean b;
226 protected
227 Value val;
228 algorithm
229 9451 (_, val) := tpl;
230 9451 b := List.hasSeveralElements(Value.getEquations(val));
231 end relevant;
232 end PseudoBucket;
233
234 // ############################################################
235 // Main Functions
236 // ############################################################
237
238 function tarjan
239 "author: kabdelhak
240 Sorting algorithm for directed graphs by Robert E. Tarjan.
241 First published in doi:10.1137/0201010"
242 input Adjacency.Matrix adj;
243 input Matching matching;
244 input VariablePointers vars;
245 input EquationPointers eqns;
246 output list<StrongComponent> comps = {};
247 protected
248 Option<Adjacency.Mapping> mapping_opt;
249 Option<array<tuple<Integer,Integer>>> eqn_AtS "eqn: arr_idx -> start_idx/length";
250 Option<array<tuple<Integer,Integer>>> var_AtS "var: arr_idx -> start_idx/length";
251 algorithm
252 try
253 comps := match adj
254 local
255 list<list<Integer>> comps_indices, phase2_indices;
256 Adjacency.Matrix phase2_adj;
257 Matching phase2_matching;
258 array<SuperNode> super_nodes;
259 array<Integer> var_loc;
260 list<tuple<Mode, Value>> buckets;
261
262 case Adjacency.Matrix.FINAL() algorithm
263
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1622 times.
 1622 if Flags.isSet(Flags.DUMP_SORTING) then
264 ✗ print(StringUtil.headline_1("Sorting"));
265 end if;
266
267 // phase 1 tarjan
268 1622 buckets := PseudoBucket.create(matching.eqn_to_var, eqns, adj.mapping, adj.m, adj.modes);
269 1622 comps_indices := tarjanScalar(adj.m, matching);
270
271 // phase 2 tarjan
272 1622 (phase2_adj, phase2_matching, super_nodes) := SuperNode.create(adj, adj.mapping, matching, eqns.map, comps_indices, buckets);
273
274 // kabdelhak: this match-statement is superfluous, SuperNode.create always returns these types.
275 // it is just safer if something is changed in the future
276 () := match phase2_adj
277 case Adjacency.Matrix.FINAL() algorithm
278 // phase 3 tarjan
279 1622 phase2_indices := tarjanScalar(phase2_adj.m, phase2_matching);
280
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1622 times.
 3244 var_loc := arrayCreate(arrayLength(matching.var_to_eqn), 0);
281
4/4
✓ Branch 0 taken 7967 times.
✓ Branch 1 taken 1622 times.
✓ Branch 2 taken 7967 times.
✓ Branch 3 taken 1622 times.
 9589 comps := list(SuperNode.collapse(comp, super_nodes, adj.m, adj.mapping, matching, vars, eqns, var_loc) for comp in phase2_indices);
282 1622 GCExt.free(var_loc);
283 then ();
284
285 else algorithm
286 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because of unknown adjacency matrix or matching type."});
287 ✗ then fail();
288 end match;
289 then comps;
290
291 // do nothing for empty matrix (empty system)
292 case Adjacency.Matrix.EMPTY() then {};
293
294 else algorithm
295 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because adjacency matrix has unknown type."});
296 ✗ then fail();
297 end match;
298 else
299 ✗ mapping_opt := Adjacency.Matrix.getMappingOpt(adj);
300 (eqn_AtS, var_AtS) := match mapping_opt
301 local
302 Adjacency.Mapping mapping;
303 ✗ case SOME(mapping) then (SOME(mapping.eqn_AtS), SOME(mapping.var_AtS));
304 else (NONE(), NONE());
305 end match;
306 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed to sort system:\n"
307 + VariablePointers.toString(vars, "System", var_AtS) + "\n"
308 + EquationPointers.toString(eqns, "System", eqn_AtS) + "\n"
309 + Matching.toString(matching)});
310 ✗ fail();
311 end try;
312 end tarjan;
313
314 function tarjanScalar
315 "author: lochel, kabdelhak
316 This sorting algorithm only considers equations e that have a matched variable v with e = var_to_eqn[v]."
317 input Adjacency.IntMatrix m "normal adjacency matrix";
318 input Matching matching "eqn <-> var";
319 output list<list<Integer>> comps = {} "eqn indices";
320 protected
321 Integer index = 0;
322 list<Integer> stack = {};
323 array<Integer> number, lowlink;
324 array<Boolean> onStack;
325 array<Integer> data = Adjacency.IntMatrix.entries(m);
326 Integer N = arrayLength(matching.var_to_eqn);
327 Integer M = arrayLength(matching.eqn_to_var);
328 array<Integer> call_eqn, call_pos;
329 Integer eqn;
330 algorithm
331 4307 number := arrayCreate(M, -1);
332 4307 lowlink := arrayCreate(M, -1);
333 4307 onStack := arrayCreate(M, false);
334 4307 call_eqn := arrayCreate(M, 0);
335 4307 call_pos := arrayCreate(M, 0);
336
337 // loop over all variables and find their component
338
2/2
✓ Branch 0 taken 4306 times.
✓ Branch 1 taken 1 time.
 50682 for var in 1:N loop
339 46375 eqn := matching.var_to_eqn[var];
340
4/4
✓ Branch 0 taken 34790 times.
✓ Branch 1 taken 11585 times.
✓ Branch 3 taken 23257 times.
✓ Branch 4 taken 11533 times.
 46375 if eqn > 0 and number[eqn] == -1 then
341 23257 (stack, index, comps) := strongConnect(m, data, matching.var_to_eqn, eqn, stack, index, number, lowlink, onStack, call_eqn, call_pos, comps);
342 end if;
343 end for;
344
345 // free auxiliary arrays
346 4307 GCExt.free(number);
347 4307 GCExt.free(lowlink);
348 4307 GCExt.free(onStack);
349 4307 GCExt.free(call_eqn);
350 4307 GCExt.free(call_pos);
351
352 // reverse for correct ordering
353 4307 comps := listReverse(comps);
354 end tarjanScalar;
355
356 type SCC = list<Integer>;
357
358 uniontype LoopIdentifier
359 "used to identify algebraic loops that are structurally equal just differ in local indexing"
360 record LOOP_IDENTIFIER
361 UnorderedSet<Integer> eqns;
362 UnorderedSet<Integer> vars;
363 end LOOP_IDENTIFIER;
364
365 function hash
366 input LoopIdentifier li;
367 output Integer i = stringHashDjb2(toString(li));
368 end hash;
369
370 function isEqual
371 input LoopIdentifier li1;
372 input LoopIdentifier li2;
373 output Boolean b = UnorderedSet.isEqual(li1.eqns, li2.eqns) and UnorderedSet.isEqual(li1.vars, li2.vars);
374 end isEqual;
375
376 function toString
377 input LoopIdentifier li;
378 output String str;
379 algorithm
380 374 str := " eqns: " + UnorderedSet.toString(li.eqns, intString) + "\n vars:" + UnorderedSet.toString(li.vars, intString) + "\n";
381 end toString;
382
383 function fromSCC
384 input list<Integer> scc;
385 input Adjacency.Mapping mapping;
386 input Matching matching;
387 output LoopIdentifier li;
388 algorithm
389
8/8
✓ Branch 0 taken 2431 times.
✓ Branch 1 taken 187 times.
✓ Branch 2 taken 2431 times.
✓ Branch 3 taken 187 times.
✓ Branch 5 taken 2431 times.
✓ Branch 6 taken 187 times.
✓ Branch 7 taken 2431 times.
✓ Branch 8 taken 187 times.
 5049 li := LOOP_IDENTIFIER(
390 eqns = UnorderedSet.fromList(list(mapping.eqn_StA[i] for i in scc), Util.id, intEq),
391 vars = UnorderedSet.fromList(list(mapping.var_StA[matching.eqn_to_var[i]] for i in scc), Util.id, intEq));
392 end fromSCC;
393 end LoopIdentifier;
394
395 uniontype SuperNode
396 record SINGLE
397 "does not belong to an algebraic loop or array"
398 Integer index;
399 end SINGLE;
400
401 record ELEMENT
402 "is part of either an algebraic loop or array"
403 Integer index;
404 Integer parent;
405 end ELEMENT;
406
407 record ALGEBRAIC_LOOP
408 "an algebraic loop of equations"
409 Integer index;
410 list<Integer> eqn_indices;
411 end ALGEBRAIC_LOOP;
412
413 record ARRAY_BUCKET
414 "a bucket of array equations solved for the same cref"
415 Integer index;
416 ComponentRef cref_to_solve;
417 list<Integer> eqn_indices;
418 Integer arr_idx;
419 end ARRAY_BUCKET;
420
421 function toString
422 "increment index by 1 to have it consistent with index plots"
423 input SuperNode node;
424 output String str;
425 algorithm
426 str := match node
427 ✗ case SINGLE() then "[" + intString(node.index + 1) + "] single ";
428 ✗ case ELEMENT() then "[" + intString(node.index + 1) + "] scalar element of (" + intString(node.parent + 1) + ")";
429 ✗ case ALGEBRAIC_LOOP() then "[" + intString(node.index + 1) + "] algebraic loop " + List.toString(list(i + 1 for i in node.eqn_indices), intString);
430 ✗ case ARRAY_BUCKET() then "[" + intString(node.index + 1) + "] array bucket " + List.toString(list(i + 1 for i in node.eqn_indices), intString);
431 else "ERROR";
432 end match;
433 end toString;
434
435 function isArrayBucket
436 input SuperNode node;
437 output Boolean b;
438 algorithm
439 b := match node
440 case ARRAY_BUCKET() then true;
441 else false;
442 end match;
443 end isArrayBucket;
444
445 function getEqnIndices
446 input SuperNode node;
447 output list<Integer> eqn_indices;
448 algorithm
449 eqn_indices := match node
450 ✗ case SINGLE() then {node.index};
451 ✗ case ALGEBRAIC_LOOP() then node.eqn_indices;
452 6 case ARRAY_BUCKET() then node.eqn_indices;
453 case ELEMENT() algorithm
454 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because elements should not be accessed, only their parents: " + toString(node)});
455 ✗ then fail();
456 else algorithm
457 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because of incorrect super node type."});
458 ✗ then fail();
459 end match;
460 end getEqnIndices;
461
462 function create
463 input Adjacency.Matrix adj;
464 input Adjacency.Mapping mapping;
465 input Matching matching;
466 input UnorderedMap<ComponentRef, Integer> eqn_map;
467 input list<SCC> scc_phase1;
468 input list<tuple<Mode, Value>> buck;
469 output Adjacency.Matrix phase2_adj = adj;
470 output Matching phase2_matching = matching;
471 output array<SuperNode> super_nodes;
472 protected
473 LoopIdentifier li;
474 UnorderedMap<LoopIdentifier, SCC> loop_map = UnorderedMap.new<SCC>(LoopIdentifier.hash, LoopIdentifier.isEqual);
475 list<SCC> algebraic_loops = list(scc for scc guard List.hasSeveralElements(scc) in scc_phase1);
476 list<tuple<Mode, Value>> buckets = buck;
477 Mode mode;
478 Value val;
479 Integer index, shift;
480 list<Integer> var_lst, eqn_lst;
481 list<list<Integer>> eqn_rows, var_rows, rest_var_rows "the rows merged into one super node, in merge order";
482 UnorderedSet<Integer> alg_loop_set = UnorderedSet.new(Util.id, intEq) "the set of indices appearing in algebraic loops";
483 array<Integer> stamp, counts, uniq, sorted "mergeRows scratch";
484 Integer mx;
485 algorithm
486 phase2_adj := match phase2_adj
487 case Adjacency.FINAL() algorithm
488 // merge algebraic loops with identical interface (array based)
489 // ToDo: proper handling without merging them all and having a for-loop around instead
490
2/2
✓ Branch 0 taken 187 times.
✓ Branch 1 taken 1622 times.
 1809 for scc in algebraic_loops loop
491 187 li := LoopIdentifier.fromSCC(scc, mapping, matching);
492 187 UnorderedMap.add(li, listAppend(scc, UnorderedMap.getOrDefault(li, loop_map, {})), loop_map);
493 end for;
494 1622 algebraic_loops := UnorderedMap.valueList(loop_map);
495
496 //### 1. store all loop indices ###
497
4/4
✓ Branch 0 taken 2431 times.
✓ Branch 1 taken 127 times.
✓ Branch 2 taken 127 times.
✓ Branch 3 taken 1622 times.
 4180 for scc in algebraic_loops loop for idx in scc loop
498 2431 UnorderedSet.add(idx, alg_loop_set);
499 end for; end for;
500
501 // remove loop indices from array buckets (so they are not used twice)
502
4/4
✓ Branch 0 taken 9451 times.
✓ Branch 1 taken 1622 times.
✓ Branch 2 taken 9451 times.
✓ Branch 3 taken 1622 times.
 11073 buckets := list(PseudoBucket.filter(bucket_tpl, alg_loop_set) for bucket_tpl in buckets);
503
6/6
✓ Branch 1 taken 8289 times.
✓ Branch 2 taken 1162 times.
✓ Branch 3 taken 9451 times.
✓ Branch 4 taken 1622 times.
✓ Branch 5 taken 1162 times.
✓ Branch 6 taken 1622 times.
 11073 buckets := list(bucket_tpl for bucket_tpl guard(PseudoBucket.relevant(bucket_tpl)) in buckets);
504 1622 shift := listLength(algebraic_loops) + listLength(buckets);
505
506 // ### 2. initialize super nodes ###
507 1622 super_nodes := arrayCreate(Adjacency.IntMatrix.rows(phase2_adj.m) + shift, SuperNode.SINGLE(0));
508
1/2
✓ Branch 0 taken 1622 times.
✗ Branch 1 not taken.
 21142 for i in 1:arrayLength(super_nodes) loop
509 19520 arrayUpdate(super_nodes, i, SuperNode.SINGLE(i));
510 end for;
511
512 // ### 3. expand matching ###
513
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1622 times.
 1622 index := arrayLength(phase2_matching.eqn_to_var);
514
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1622 times.
 3244 phase2_matching.eqn_to_var := Array.expandToSize(arrayLength(phase2_matching.eqn_to_var) + shift, phase2_matching.eqn_to_var, -1);
515
2/2
✓ Branch 0 taken 378 times.
✓ Branch 1 taken 1244 times.
 2911 for i in index+1:index+shift loop
516 1289 phase2_matching.eqn_to_var[i] := i;
517 end for;
518
519
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1622 times.
 1622 index := arrayLength(phase2_matching.var_to_eqn);
520
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1622 times.
 3244 phase2_matching.var_to_eqn := Array.expandToSize(arrayLength(phase2_matching.var_to_eqn) + shift, phase2_matching.var_to_eqn, -1);
521
2/2
✓ Branch 0 taken 378 times.
✓ Branch 1 taken 1244 times.
 2911 for i in index+1:index+shift loop
522 1289 phase2_matching.var_to_eqn[i] := i;
523 end for;
524
525 // ### 4. adjust transposed matrix ###
526 // 4.1. enlarge transposed matrix by the maximum possible amount of new nodes
527 1622 index := Adjacency.IntMatrix.rows(phase2_adj.mT) + 1;
528 1622 stamp := arrayCreate(intMax(Adjacency.IntMatrix.rows(phase2_adj.m), Adjacency.IntMatrix.rows(phase2_adj.mT)) + shift, 0);
529 1622 phase2_adj.mT := Adjacency.IntMatrix.expandRows(phase2_adj.mT, shift);
530
4/4
✓ Branch 0 taken 1162 times.
✓ Branch 1 taken 1622 times.
✓ Branch 2 taken 1162 times.
✓ Branch 3 taken 1622 times.
 2784 eqn_rows := listAppend(algebraic_loops, list(Value.getEquations(Util.tuple22(bucket)) for bucket in buckets));
531
8/8
✓ Branch 0 taken 1289 times.
✓ Branch 1 taken 1622 times.
✓ Branch 2 taken 1289 times.
✓ Branch 3 taken 1622 times.
✓ Branch 4 taken 11549 times.
✓ Branch 5 taken 1289 times.
✓ Branch 6 taken 11549 times.
✓ Branch 7 taken 1289 times.
 14460 var_rows := list(list(phase2_matching.eqn_to_var[idx] for idx in row) for row in eqn_rows);
532 1622 Adjacency.IntMatrix.reserveData(phase2_adj.mT, mergedSize(phase2_adj.mT, var_rows));
533 1622 mx := maxMergedRow(phase2_adj.mT, var_rows);
534 1622 counts := arrayCreate(Util.nextPrime(mx), 0);
535 1622 uniq := arrayCreate(mx, 0);
536 1622 sorted := arrayCreate(mx, 0);
537
538 // 4.2. merge all algebraic loop variables of one scc to one single variable
539 rest_var_rows := var_rows;
540
2/2
✓ Branch 0 taken 127 times.
✓ Branch 1 taken 1622 times.
 1749 for scc in algebraic_loops loop
541
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 127 times.
 127 var_lst :: rest_var_rows := rest_var_rows;
542 127 mergeLoopNodes(super_nodes, var_lst, index, false);
543 127 index := mergeRows(phase2_adj.mT, phase2_matching.var_to_eqn, super_nodes, var_lst, index, stamp, counts, uniq, sorted);
544 end for;
545
546 // 4.3. merge all array variables of one bucket to one single variable
547
2/2
✓ Branch 0 taken 1162 times.
✓ Branch 1 taken 1622 times.
 2784 for bucket in buckets loop
548 1162 (mode, val) := bucket;
549
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1162 times.
 1162 var_lst :: rest_var_rows := rest_var_rows;
550 () := match val
551 1055 case Value.SINGLE_VAL() algorithm mergeArrayNodes(super_nodes, val.cref_to_solve, var_lst, index, UnorderedMap.getSafe(mode.eqn_name, eqn_map, sourceInfo()), false); then ();
552 107 case Value.MULTI_VAL() algorithm mergeLoopNodes(super_nodes, var_lst, index, false); then ();
553 end match;
554 1162 index := mergeRows(phase2_adj.mT, phase2_matching.var_to_eqn, super_nodes, var_lst, index, stamp, counts, uniq, sorted);
555 end for;
556
557 /// ### 5. adjust normal matrix ###
558 // 5.1. transpose the transposed matrix and enlarge it by the maximum possible amount of new nodes
559 1622 index := Adjacency.IntMatrix.rows(phase2_adj.m) + 1;
560 1622 phase2_adj.m := Adjacency.IntMatrix.transpose(phase2_adj.mT, Adjacency.IntMatrix.rows(phase2_adj.m) + shift,
561 mergedSize(phase2_adj.m, eqn_rows));
562 1622 mx := maxMergedRow(phase2_adj.m, eqn_rows);
563 1622 counts := arrayCreate(Util.nextPrime(mx), 0);
564 1622 uniq := arrayCreate(mx, 0);
565 1622 sorted := arrayCreate(mx, 0);
566 // 5.2 merge all algebraic loop equations of one scc to one single equation
567
2/2
✓ Branch 0 taken 127 times.
✓ Branch 1 taken 1622 times.
 1749 for scc in algebraic_loops loop
568 127 mergeLoopNodes(super_nodes, scc, index, true);
569 127 index := mergeRows(phase2_adj.m, phase2_matching.eqn_to_var, super_nodes, scc, index, stamp, counts, uniq, sorted);
570 end for;
571
572 // 5.3. merge all for-loop equations of one bucket to one single equation
573
2/2
✓ Branch 0 taken 1162 times.
✓ Branch 1 taken 1622 times.
 2784 for bucket in buckets loop
574 1162 (mode, val) := bucket;
575 1162 eqn_lst := Value.getEquations(val);
576 () := match val
577 1055 case Value.SINGLE_VAL() algorithm mergeArrayNodes(super_nodes, val.cref_to_solve, eqn_lst, index, UnorderedMap.getSafe(mode.eqn_name, eqn_map, sourceInfo()), true); then ();
578 107 case Value.MULTI_VAL() algorithm mergeLoopNodes(super_nodes, eqn_lst, index, true); then ();
579 end match;
580 1162 index := mergeRows(phase2_adj.m, phase2_matching.eqn_to_var, super_nodes, eqn_lst, index, stamp, counts, uniq, sorted);
581 end for;
582
583 // phase 3 tarjan only reads phase2_adj.m, so mT is left as it is
584
585 then phase2_adj;
586
587 else algorithm
588 ✗ Error.addMessage(Error.INTERNAL_ERROR,{getInstanceName() + " failed because of unknown adjacency matrix type."});
589 ✗ then fail();
590 end match;
591 end create;
592
593 function collapse
594 input list<Integer> comp_indices;
595 input array<SuperNode> super_nodes;
596 input Adjacency.IntMatrix m;
597 input Adjacency.Mapping mapping;
598 input Matching matching;
599 input VariablePointers vars;
600 input EquationPointers eqns;
601 input array<Integer> var_loc "scratch for getLocalSystem";
602 output StrongComponent comp;
603 protected
604 list<SuperNode> node_comp = list(super_nodes[i] for i in comp_indices);
605 list<list<Integer>> sorted_body_components;
606 list<Integer> sorted_body_indices;
607 algorithm
608 comp := match node_comp
609 local
610 SuperNode node;
611 Adjacency.IntMatrix m_local;
612 Matching matching_local;
613 Boolean indep = true;
614 array<Integer> map_back "local to global equation indices";
615 Integer eqn_arr_idx, var_arr_idx;
616
617 // a single scalar equation that has nothing to do with arrays
618 case {SINGLE()}
619 6682 then StrongComponent.createPseudoScalar(comp_indices, matching.eqn_to_var, mapping, vars, eqns);
620
621 // a single strong component from phase I
622 case {node as ALGEBRAIC_LOOP()}
623 234 then StrongComponent.createPseudoScalar(node.eqn_indices, matching.eqn_to_var, mapping, vars, eqns);
624
625 // a single array equation
626 case {node as ARRAY_BUCKET()} algorithm
627 // sort local system to determine in what order the equations have to be solved
628 1049 (m_local, matching_local, map_back) := getLocalSystem(m, matching, node.eqn_indices, var_loc);
629 1049 sorted_body_components := tarjanScalar(m_local, matching_local);
630 1049 sorted_body_indices := mapFlatten(sorted_body_components, map_back);
631
632 // if new strong components of size > 1 were created it is an error, this should
633 // have occured in sorting phase I
634
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1049 times.
 1049 if List.compareLength(sorted_body_components, sorted_body_indices) <> 0 then
635 ✗ Error.addMessage(Error.INTERNAL_ERROR, {getInstanceName()
636 + " crucially failed for the following Phase II strong component"
637 + " because the body turned out to still have strong components:\n"
638 + List.toString(node_comp, SuperNode.toString, List.Style.NEWLINE_TAB) + "\n"});
639 end if;
640
641 // check for independence of the element equations
642 // if locally each variable occurs in only one equation, then they are all independent
643 1049 indep := Array.all(m_local.len, function intEq(i2 = 1));
644
645 1049 eqn_arr_idx := mapping.eqn_StA[listHead(node.eqn_indices)];
646 1049 var_arr_idx := mapping.var_StA[matching.eqn_to_var[listHead(node.eqn_indices)]];
647 1049 then StrongComponent.createPseudoSlice(var_arr_idx, eqn_arr_idx, node.cref_to_solve, sorted_body_indices, matching.eqn_to_var, eqns, mapping, indep);
648
649 // entwined equations: at least one array bucket mixed with scalar equations
650 case _ guard(List.any(node_comp, isArrayBucket)) algorithm
651 // sort local system to determine in what order the equations have to be solved
652
4/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 2 times.
 8 (m_local, matching_local, map_back) := getLocalSystem(m, matching, List.flatten(list(getEqnIndices(n) for n in node_comp)), var_loc);
653 2 sorted_body_components := tarjanScalar(m_local, matching_local);
654 2 sorted_body_indices := mapFlatten(sorted_body_components, map_back);
655 2 comp := StrongComponent.createPseudoEntwined(sorted_body_indices, matching.eqn_to_var, mapping, vars, eqns, node_comp);
656 then comp;
657
658 // fallback: pure scalar or algebraic loop phase III nodes (body components not actually sorted)
659 else algorithm
660 ✗ sorted_body_indices := List.flatten(list(getEqnIndices(n) for n in node_comp));
661 ✗ then StrongComponent.createPseudoScalar(sorted_body_indices, matching.eqn_to_var, mapping, vars, eqns);
662 end match;
663 end collapse;
664
665 protected
666 function mapFlatten
667 "flattens the components and maps the local indices back to global ones"
668 input list<list<Integer>> components;
669 input array<Integer> map_back;
670 output list<Integer> indices = {};
671 algorithm
672
2/2
✓ Branch 0 taken 8571 times.
✓ Branch 1 taken 1051 times.
 9622 for comp in components loop
673
2/2
✓ Branch 0 taken 8571 times.
✓ Branch 1 taken 8571 times.
 17142 for i in comp loop
674 8571 indices := map_back[i] :: indices;
675 end for;
676 end for;
677 1051 indices := MetaModelica.Dangerous.listReverseInPlace(indices);
678 end mapFlatten;
679
680 function mergedSize
681 "how much buffer the merged rows need at most, so that merging them does
682 not have to grow it"
683 input Adjacency.IntMatrix m;
684 input list<list<Integer>> rows;
685 output Integer total = 0;
686 algorithm
687
2/2
✓ Branch 0 taken 2578 times.
✓ Branch 1 taken 3244 times.
 5822 for row in rows loop
688
2/2
✓ Branch 0 taken 23098 times.
✓ Branch 1 taken 2578 times.
 25676 for idx in row loop
689 23098 total := total + m.len[idx];
690 end for;
691 end for;
692 end mergedSize;
693
694 function maxMergedRow
695 "the largest row that merging any of rows can produce"
696 input Adjacency.IntMatrix m;
697 input list<list<Integer>> rows;
698 output Integer mx = 0;
699 protected
700 Integer total;
701 algorithm
702
2/2
✓ Branch 0 taken 2578 times.
✓ Branch 1 taken 3244 times.
 5822 for row in rows loop
703 total := 0;
704
2/2
✓ Branch 0 taken 23098 times.
✓ Branch 1 taken 2578 times.
 25676 for idx in row loop
705 23098 total := total + m.len[idx];
706 end for;
707 mx := intMax(mx, total);
708 end for;
709 end maxMergedRow;
710
711 function mergeRows
712 "merges rows_to_merge into row new_idx. The entries come out in the order
713 UnorderedSet.toList gave for a set with nextPrime(total) buckets, which
714 the reconstructed for-loops depend on: descending bucket, insertion order
715 inside a bucket."
716 input Adjacency.IntMatrix m;
717 input array<Integer> matching;
718 input array<SuperNode> super_nodes;
719 input list<Integer> rows_to_merge;
720 input output Integer new_idx;
721 input array<Integer> stamp "indexed by entry, all zero on entry and exit";
722 input array<Integer> counts "one slot per bucket";
723 input array<Integer> uniq "scratch of the merged size";
724 input array<Integer> sorted "scratch of the merged size";
725 protected
726 array<Integer> data = Adjacency.IntMatrix.entries(m);
727 Integer total = 0, first, n = 0, p, h, v, acc, c;
728 algorithm
729
2/2
✓ Branch 0 taken 23098 times.
✓ Branch 1 taken 2578 times.
 25676 for idx in rows_to_merge loop
730 23098 total := total + m.len[idx];
731 end for;
732 2578 p := Util.nextPrime(total);
733
2/2
✓ Branch 0 taken 23098 times.
✓ Branch 1 taken 2578 times.
 25676 for idx in rows_to_merge loop
734 23098 first := m.start[idx];
735
1/2
✓ Branch 1 taken 23098 times.
✗ Branch 2 not taken.
 71607 for k in first:first + m.len[idx] - 1 loop
736 48509 v := data[k];
737
2/2
✓ Branch 1 taken 21801 times.
✓ Branch 2 taken 26708 times.
 48509 if stamp[v] == 0 then
738 21801 arrayUpdate(stamp, v, 1);
739 21801 n := n + 1;
740 21801 arrayUpdate(uniq, n, v);
741 end if;
742 end for;
743 end for;
744 // counting sort by bucket, descending
745
1/2
✓ Branch 0 taken 2578 times.
✗ Branch 1 not taken.
 53789 for i in 1:p loop
746 51211 arrayUpdate(counts, i, 0);
747 end for;
748
1/2
✓ Branch 0 taken 2578 times.
✗ Branch 1 not taken.
 24379 for i in 1:n loop
749
1/2
✓ Branch 1 taken 21801 times.
✗ Branch 2 not taken.
 21801 h := intMod(uniq[i], p) + 1;
750 21801 arrayUpdate(counts, h, counts[h] + 1);
751 end for;
752 acc := 0;
753
1/2
✓ Branch 0 taken 2578 times.
✗ Branch 1 not taken.
 2578 for i in p:-1:1 loop
754 51211 c := counts[i];
755 51211 arrayUpdate(counts, i, acc);
756 51211 acc := acc + c;
757 end for;
758
1/2
✓ Branch 0 taken 2578 times.
✗ Branch 1 not taken.
 24379 for i in 1:n loop
759
1/2
✓ Branch 1 taken 21801 times.
✗ Branch 2 not taken.
 21801 v := uniq[i];
760 21801 h := intMod(v, p) + 1;
761 21801 arrayUpdate(sorted, counts[h] + 1, v);
762 21801 arrayUpdate(counts, h, counts[h] + 1);
763 21801 arrayUpdate(stamp, v, 0);
764 end for;
765 2578 Adjacency.IntMatrix.setRowFromArray(m, new_idx, sorted, n);
766 // remove the original rows
767
2/2
✓ Branch 0 taken 23098 times.
✓ Branch 1 taken 2578 times.
 25676 for idx in rows_to_merge loop
768 23098 Adjacency.IntMatrix.clearRow(m, idx);
769 23098 arrayUpdate(matching, idx, -1);
770 end for;
771 2578 new_idx := new_idx + 1;
772 end mergeRows;
773
774 function mergeArrayNodes
775 input array<SuperNode> super_nodes;
776 input ComponentRef cref_to_solve;
777 input list<Integer> rows_to_merge;
778 input output Integer new_idx;
779 input Integer arr_idx;
780 input Boolean update_scalar;
781 algorithm
782 2110 arrayUpdate(super_nodes, new_idx, SuperNode.ARRAY_BUCKET(new_idx, cref_to_solve, rows_to_merge, arr_idx));
783 // this is not necessary but better to debug.
784
2/2
✓ Branch 0 taken 1055 times.
✓ Branch 1 taken 1055 times.
 2110 if update_scalar then
785
2/2
✓ Branch 0 taken 8571 times.
✓ Branch 1 taken 1055 times.
 9626 for i in rows_to_merge loop
786 8571 arrayUpdate(super_nodes, i, SuperNode.ELEMENT(i, new_idx));
787 end for;
788 end if;
789 end mergeArrayNodes;
790
791 function mergeLoopNodes
792 input array<SuperNode> super_nodes;
793 input list<Integer> rows_to_merge;
794 input output Integer new_idx;
795 input Boolean update_scalar;
796 algorithm
797 468 arrayUpdate(super_nodes, new_idx, SuperNode.ALGEBRAIC_LOOP(new_idx, rows_to_merge));
798 // this is not necessary but better to debug.
799
2/2
✓ Branch 0 taken 234 times.
✓ Branch 1 taken 234 times.
 468 if update_scalar then
800
2/2
✓ Branch 0 taken 2978 times.
✓ Branch 1 taken 234 times.
 3212 for i in rows_to_merge loop
801 2978 arrayUpdate(super_nodes, i, SuperNode.ELEMENT(i, new_idx));
802 end for;
803 end if;
804 end mergeLoopNodes;
805 end SuperNode;
806
807 // ############################################################
808 // Protected Functions and Types
809 // ############################################################
810
811 protected
812 function getLocalSystem
813 input Adjacency.IntMatrix m "global adjacency matrix";
814 input Matching matching "global matching";
815 input list<Integer> eqn_indices "global equation indices to keep";
816 input array<Integer> var_loc "scratch: global -> local variable index, all zero on entry and on exit";
817 output Adjacency.IntMatrix m_loc "local adjacency matrix";
818 output Matching matching_loc "local matching";
819 output array<Integer> map_back "local to global equation indices";
820 protected
821 constant Integer N = listLength(eqn_indices);
822 array<Integer> var_to_eqn = arrayCreate(N, -1);
823 array<Integer> eqn_to_var = arrayCreate(N, -1);
824 array<Integer> data = Adjacency.IntMatrix.entries(m);
825 Adjacency.IntMatrix.Builder builder;
826 Integer j = 1, row, first, edges = 0, loc, var;
827 algorithm
828 // map matching from full system and save eqn map back
829 1051 map_back := arrayCreate(N, -1);
830
2/2
✓ Branch 1 taken 8571 times.
✓ Branch 2 taken 1051 times.
 9622 for i in eqn_indices loop
831 // set equation map (local -> global)
832 8571 map_back[j] := i;
833
834 // set var from matching (global -> local)
835 8571 var := matching.eqn_to_var[i];
836
1/2
✓ Branch 0 taken 8571 times.
✗ Branch 1 not taken.
 8571 if var > 0 then
837 8571 arrayUpdate(var_loc, var, j);
838 end if;
839
840 // set local matching
841 8571 eqn_to_var[j] := j;
842 8571 var_to_eqn[j] := j;
843
844 8571 j := j + 1;
845 end for;
846 1051 matching_loc := MATCHING(var_to_eqn, eqn_to_var);
847
848 // filter only local edges of adjacency matrix
849
1/2
✓ Branch 1 taken 1051 times.
✗ Branch 2 not taken.
 1051 for j in 1:N loop
850 8571 edges := edges + m.len[map_back[j]];
851 end for;
852 1051 builder := Adjacency.IntMatrix.newBuilder(edges);
853
1/2
✓ Branch 1 taken 1051 times.
✗ Branch 2 not taken.
 9622 for j in 1:N loop
854 8571 row := map_back[j];
855 8571 first := m.start[row];
856
1/2
✓ Branch 1 taken 8571 times.
✗ Branch 2 not taken.
 28129 for k in first + m.len[row] - 1:-1:first loop
857 19558 var := data[k];
858
1/2
✓ Branch 0 taken 19558 times.
✗ Branch 1 not taken.
 19558 loc := if var > 0 then var_loc[var] else 0;
859
2/2
✓ Branch 0 taken 9623 times.
✓ Branch 1 taken 9935 times.
 19558 if loc > 0 then
860 9623 Adjacency.IntMatrix.builderAdd(builder, j, loc);
861 end if;
862 end for;
863 end for;
864 1051 m_loc := Adjacency.IntMatrix.fromBuilder(builder, N);
865
866 // leave the scratch clean for the next component
867
2/2
✓ Branch 0 taken 8571 times.
✓ Branch 1 taken 1051 times.
 9622 for i in eqn_indices loop
868 8571 var := matching.eqn_to_var[i];
869
1/2
✓ Branch 0 taken 8571 times.
✗ Branch 1 not taken.
 8571 if var > 0 then
870 8571 arrayUpdate(var_loc, var, 0);
871 end if;
872 end for;
873 end getLocalSystem;
874
875 function strongConnect
876 "author: lochel, kabdelhak
877 Iterative depth-first search, the recursion depth would be the length of
878 the longest dependency chain."
879 input Adjacency.IntMatrix m "normal adjacency matrix";
880 input array<Integer> data "its entry buffer";
881 input array<Integer> var_to_eqn "eqn := var_to_eqn[var]";
882 input Integer root "equation to start from";
883 input output list<Integer> stack "equation stack";
884 input output Integer index "component index";
885 input array<Integer> number "auxiliary array";
886 input array<Integer> lowlink "represents the component groups";
887 input array<Boolean> onStack "true if eqn index is on the stack";
888 input array<Integer> call_eqn "depth-first search stack: equation";
889 input array<Integer> call_pos "depth-first search stack: next entry of m to visit";
890 input output list<list<Integer>> comps "accumulator for components";
891 protected
892 list<Integer> SCC;
893 Integer depth, eqn, eqn2, k, cand;
894 algorithm
895 depth := 1;
896 23257 (stack, index) := strongConnectVisit(m, root, depth, stack, index, number, lowlink, onStack, call_eqn, call_pos);
897
898
2/2
✓ Branch 0 taken 101908 times.
✓ Branch 1 taken 23257 times.
 125165 while depth > 0 loop
899 101908 eqn := call_eqn[depth];
900 101908 k := call_pos[depth];
901
2/2
✓ Branch 2 taken 67118 times.
✓ Branch 3 taken 34790 times.
 101908 if k < m.start[eqn] + m.len[eqn] then
902 67118 arrayUpdate(call_pos, depth, k + 1);
903 67118 cand := data[k];
904
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 67118 times.
 67118 if cand > 0 then
905 67118 eqn2 := var_to_eqn[cand];
906
2/2
✓ Branch 0 taken 34773 times.
✓ Branch 1 taken 32345 times.
 67118 if eqn2 > 0 and eqn2 <> eqn then
907
2/2
✓ Branch 1 taken 11533 times.
✓ Branch 2 taken 20812 times.
 32345 if number[eqn2] == -1 then
908 // Successor eqn2 has not yet been visited; descend into it
909 11533 depth := depth + 1;
910 11533 (stack, index) := strongConnectVisit(m, eqn2, depth, stack, index, number, lowlink, onStack, call_eqn, call_pos);
911 elseif onStack[eqn2] then
912 // Successor eqn2 is in the stack and hence in the current SCC
913 1293 arrayUpdate(lowlink, eqn, intMin(lowlink[eqn], number[eqn2]));
914 end if;
915 end if;
916 end if;
917 else
918 // If eqn is a root node, pop the stack and generate an SCC
919
2/2
✓ Branch 2 taken 32541 times.
✓ Branch 3 taken 2249 times.
 34790 if lowlink[eqn] == number[eqn] then
920
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32541 times.
 32541 eqn2::stack := stack;
921 32541 arrayUpdate(onStack, eqn2, false);
922 SCC := {eqn2};
923
2/2
✓ Branch 0 taken 2249 times.
✓ Branch 1 taken 32541 times.
 34790 while eqn <> eqn2 loop
924
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2249 times.
 2249 eqn2::stack := stack;
925 2249 arrayUpdate(onStack, eqn2, false);
926 SCC := eqn2::SCC;
927 end while;
928 32541 comps := MetaModelica.Dangerous.listReverseInPlace(SCC)::comps;
929 end if;
930
931 34790 depth := depth - 1;
932
2/2
✓ Branch 0 taken 23257 times.
✓ Branch 1 taken 11533 times.
 34790 if depth > 0 then
933 11533 eqn2 := call_eqn[depth];
934 11533 arrayUpdate(lowlink, eqn2, intMin(lowlink[eqn2], lowlink[eqn]));
935 end if;
936 end if;
937 end while;
938 end strongConnect;
939
940 function strongConnectVisit
941 input Adjacency.IntMatrix m;
942 input Integer eqn;
943 input Integer depth;
944 input output list<Integer> stack;
945 input output Integer index;
946 input array<Integer> number;
947 input array<Integer> lowlink;
948 input array<Boolean> onStack;
949 input array<Integer> call_eqn;
950 input array<Integer> call_pos;
951 algorithm
952 // Set the depth index for eqn to the smallest unused index
953 34790 arrayUpdate(number, eqn, index);
954 34790 arrayUpdate(lowlink, eqn, index);
955 34790 arrayUpdate(onStack, eqn, true);
956 34790 index := index + 1;
957 stack := eqn::stack;
958 34790 arrayUpdate(call_eqn, depth, eqn);
959 34790 arrayUpdate(call_pos, depth, m.start[eqn]);
960 end strongConnectVisit;
961
962
963 annotation(__OpenModelica_Interface="nbackend");
964 end NBSorting;
965