1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   expriter.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  functions for iterating over algebraic expressions
28   	 * @author Benjamin Mueller
29   	 * @author Stefan Vigerske
30   	 */
31   	
32   	/* enable this to record where active iterators were initialized
33   	 * (not thread-safe; problematic when using several SCIP instances concurrently)
34   	 */
35   	/* #define SCIP_DEBUG_EXPRITER */
36   	
37   	#include <assert.h>
38   	
39   	#include "scip/expr.h"
40   	#include "scip/pub_misc.h"
41   	#include "scip/struct_expr.h"
42   	#include "scip/struct_stat.h"
43   	
44   	#define MINDFSSIZE  16 /**< minimum stack size for DFS*/
45   	#define MINBFSSIZE  16 /**< minimum queue size for BFS */
46   	
47   	#ifdef SCIP_DEBUG_EXPRITER
48   	#include <execinfo.h>
49   	#include <string.h>
50   	#include <stdlib.h>
51   	
52   	#define MAXSUBSCIPDEPTH   10   /**< minimal subscip-depth to no longer store backtrace */
53   	#define MAXBACKTRACE      20   /**< maximal length of backtrace to store */
54   	
55   	/** backtrace when iterator was initialized
56   	 * - store per subscip-depth (easier than storing per SCIP instance)
57   	 * - store per iterator position that can be active concurrently
58   	 * - one string for each entry in backtrace
59   	 * - each entry up to 200 characters
60   	 */
61   	char iterinitbacktrace[MAXSUBSCIPDEPTH][SCIP_EXPRITER_MAXNACTIVE][MAXBACKTRACE][200];
62   	#endif
63   	
64   	/*
65   	 * local functions
66   	 */
67   	
68   	#ifdef SCIP_DEBUG_EXPRITER
69   	/** obtain current backtrace and store it in iterinitbacktrace */
70   	static
71   	void storeBacktrace(
72   	   int                   subscipdepth,       /**< current subscip depth */
73   	   int                   iterpos             /**< iterator position where to store backtrace */
74   	   )
75   	{
76   	   void* array[MAXBACKTRACE];
77   	   char** strings;
78   	   int size;
79   	   int i;
80   	
81   	   assert(subscipdepth >= 0);
82   	   assert(iterpos >= 0);
83   	   assert(iterpos < SCIP_EXPRITER_MAXNACTIVE);
84   	
85   	   if( subscipdepth > MAXSUBSCIPDEPTH )
86   	      return;
87   	
88   	   size = backtrace(array, MAXBACKTRACE);
89   	   strings = backtrace_symbols(array, size);
90   	   if( strings == NULL )
91   	      size = 0;
92   	
93   	   for( i = 0; i < size; i++ )
94   	      strncpy(iterinitbacktrace[subscipdepth][iterpos][i], strings[i], sizeof(iterinitbacktrace[0][0][0]));
95   	
96   	   /* '\0' for remining backtrace entries */
97   	   while( size < MAXBACKTRACE )
98   	      iterinitbacktrace[subscipdepth][iterpos][size++][0] = '\0';
99   	
100  	   free(strings);
101  	}
102  	
103  	static
104  	void printBacktraces(
105  	   int                   subscipdepth        /**< current subscip depth */
106  	   )
107  	{
108  	   int i, j;
109  	
110  	   assert(subscipdepth >= 0);
111  	   if( subscipdepth >= MAXSUBSCIPDEPTH )
112  	   {
113  	      SCIPerrorMessage("subscip depth %d too high to report active iterators", subscipdepth);
114  	      return;
115  	   }
116  	
117  	   for( i = 0; i < SCIP_EXPRITER_MAXNACTIVE-1; ++i )
118  	   {
119  	      SCIPerrorMessage("Active iterator %d created at:\n", i);
120  	      for( j = 0; j < MAXBACKTRACE; ++j )
121  	      {
122  	         if( iterinitbacktrace[subscipdepth][i][j][0] == '\0' )
123  	            break;
124  	         SCIPerrorMessage("  %s\n", iterinitbacktrace[subscipdepth][i][j]);
125  	      }
126  	   }
127  	}
128  	#else
129  	#define storeBacktrace(subscipdepth, iterpos)
130  	
131  	/*lint -e{715}*/
132  	static
133  	void printBacktraces(
134  	   int                   subscipdepth        /**< current subscip depth */
135  	   )
136  	{  /*lint --e{715}*/
137  	   SCIPerrorMessage("Rebuild with SCIP_DEBUG_EXPRITER defined in src/scip/expriter.c to see where currently "
138  	         "active iterators were initialized.\n");
139  	}
140  	#endif
141  	
142  	static
143  	void deinit(
144  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
145  	   )
146  	{
147  	   assert(iterator != NULL );
148  	
149  	   if( !iterator->initialized )
150  	      return;
151  	
152  	   if( iterator->iterindex >= 0 )
153  	   {
154  	      /* the iterindex must be the one of the last initialized iterator */
155  	      assert(iterator->iterindex == iterator->stat->nactiveexpriter-1);
156  	
157  	      /* tell core that this iterator is no longer active */
158  	      --iterator->stat->nactiveexpriter;
159  	
160  	      iterator->iterindex = -1;
161  	   }
162  	
163  	   switch( iterator->itertype )
164  	   {
165  	      case SCIP_EXPRITER_BFS :
166  	      {
167  	         assert(iterator->queue != NULL);
168  	
169  	         SCIPqueueFree(&iterator->queue);
170  	
171  	         break;
172  	      }
173  	
174  	      case SCIP_EXPRITER_RTOPOLOGIC :
175  	      {
176  	         assert(iterator->dfsnvisited != NULL);
177  	         assert(iterator->dfsexprs != NULL);
178  	
179  	         /* free dfs arrays */
180  	         BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize);
181  	         BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize);
182  	         iterator->dfssize = 0;
183  	
184  	         break;
185  	      }
186  	
187  	      case SCIP_EXPRITER_DFS :
188  	      default: break;
189  	   }
190  	}
191  	
192  	/** ensures minimum stack size of iterator's data */
193  	static
194  	SCIP_RETCODE ensureStackSize(
195  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
196  	   int                   size                /**< minimum requires size */
197  	   )
198  	{
199  	   assert(iterator != NULL);
200  	   assert(iterator->blkmem != NULL);
201  	   assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC);
202  	   assert(size >= 0);
203  	
204  	   if( size > iterator->dfssize )
205  	   {
206  	      int newsize = size * 2;
207  	
208  	      SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize, newsize) );
209  	      SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize, newsize) );
210  	      iterator->dfssize = newsize;
211  	   }
212  	
213  	   return SCIP_OKAY;
214  	}
215  	
216  	/** adds an expression to the DFS stack */
217  	static
218  	void reverseTopologicalInsert(
219  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
220  	   SCIP_EXPR*            expr                /**< expression */
221  	   )
222  	{
223  	   assert(iterator != NULL);
224  	   assert(expr != NULL);
225  	
226  	   SCIP_CALL_ABORT( ensureStackSize(iterator, iterator->dfsnexprs + 1) );
227  	   iterator->dfsexprs[iterator->dfsnexprs] = expr;
228  	   iterator->dfsnvisited[iterator->dfsnexprs] = 0;
229  	   ++(iterator->dfsnexprs);
230  	}
231  	
232  	/** moves to the next expression according to a reverse topological order */
233  	static
234  	SCIP_EXPR* doReverseTopologicalNext(
235  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
236  	   )
237  	{
238  	   SCIP_EXPR* expr;
239  	   int childidx;
240  	
241  	   assert(iterator != NULL);
242  	   assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC);
243  	
244  	   /* no expression left */
245  	   if( iterator->dfsnexprs == 0 )
246  	      return NULL;
247  	
248  	   /* get expression on the top of the stack */
249  	   expr = iterator->dfsexprs[iterator->dfsnexprs - 1];
250  	   childidx = iterator->dfsnvisited[iterator->dfsnexprs - 1];
251  	
252  	   /* remove the expression if all children have been visited */
253  	   if( childidx >= SCIPexprGetNChildren(expr) )
254  	   {
255  	      --(iterator->dfsnexprs);
256  	      return expr;
257  	   }
258  	   /* go to the next child */
259  	   else
260  	   {
261  	      SCIP_EXPR* child = SCIPexprGetChildren(expr)[childidx];
262  	      assert(child != NULL);
263  	
264  	      /* mark that the child has been visited */
265  	      ++(iterator->dfsnvisited[iterator->dfsnexprs-1]);
266  	
267  	      /* do left-most step */
268  	      while( SCIPexprGetNChildren(child) > 0 )
269  	      {
270  	         /* add child to the DFS stack */
271  	         reverseTopologicalInsert(iterator, child);
272  	
273  	         /* mark that the child has been visited; note that child is on top of the DFS stack */
274  	         ++(iterator->dfsnvisited[iterator->dfsnexprs-1]);
275  	
276  	         child = SCIPexprGetChildren(child)[0];
277  	      }
278  	
279  	      /* return last child; NOTE this child is not been added to the stack */
280  	      return child;
281  	   }
282  	}
283  	
284  	/** moves to the next expression according to the BFS rule */
285  	static
286  	SCIP_EXPR* doBfsNext(
287  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
288  	   )
289  	{
290  	   SCIP_EXPR* expr;
291  	   int i;
292  	
293  	   assert(iterator != NULL);
294  	   assert(iterator->itertype == SCIP_EXPRITER_BFS);
295  	   assert(iterator->queue != NULL);
296  	
297  	   /* no expression left */
298  	   if( SCIPqueueIsEmpty(iterator->queue) )
299  	      return NULL;
300  	
301  	   expr = (SCIP_EXPR*) SCIPqueueRemove(iterator->queue);
302  	   assert(expr != NULL);
303  	
304  	   assert(iterator->visitedtag == 0 || iterator->iterindex >= 0);
305  	   assert(iterator->visitedtag == 0 || iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
306  	   /* we should have set the visitedtag when adding the expression to the queue */
307  	   assert(iterator->visitedtag == 0 || expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag);
308  	
309  	   /* add all (possibly non-visited) children to the queue */
310  	   for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
311  	   {
312  	      SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
313  	      assert(child != NULL);
314  	
315  	      if( iterator->visitedtag != 0 )
316  	      {
317  	         assert(iterator->iterindex >= 0);
318  	         assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
319  	
320  	         /* skip children that have already been visited or have already been added to the queue */
321  	         if( child->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
322  	            continue;
323  	
324  	         /* mark child as being in the queue (will be inserted next) */
325  	         child->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
326  	      }
327  	
328  	      /* add child to the queue */
329  	      SCIP_CALL_ABORT( SCIPqueueInsert(iterator->queue, child) );
330  	   }
331  	
332  	   return expr;
333  	}
334  	
335  	/** moves to the next expression according to the DFS rule */
336  	static
337  	SCIP_EXPR* doDfsNext(
338  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
339  	   )
340  	{
341  	   SCIP_EXPRITERDATA* iterdata;
342  	
343  	   assert(iterator != NULL);
344  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
345  	   assert(iterator->iterindex >= 0);
346  	
347  	   if( iterator->curr == NULL )
348  	      return NULL;
349  	
350  	   iterdata = &iterator->curr->iterdata[iterator->iterindex];
351  	
352  	   switch( iterator->dfsstage )
353  	   {
354  	      case SCIP_EXPRITER_VISITEDCHILD:
355  	         /* consider next child */
356  	         ++iterdata->currentchild;
357  	         /* fall through */ /* no break */ /*lint -fallthrough*/
358  	
359  	      case SCIP_EXPRITER_ENTEREXPR:
360  	      {
361  	         /* if there is an unvisited child (left), then go into visitingchild stage, otherwise go to leave stage */
362  	         iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR;  /* expect that we will leave expr, and change mind to visitingchild below */
363  	         while( iterdata->currentchild < iterator->curr->nchildren )
364  	         {
365  	            if( iterator->visitedtag == 0 || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag )
366  	            {
367  	               /* if visitedtag is not used or child "currentchild" has not been visited yet, then go into visitingchild stage for this child */
368  	               iterator->dfsstage = SCIP_EXPRITER_VISITINGCHILD;
369  	               break;
370  	            }
371  	            ++iterdata->currentchild;
372  	         }
373  	         /* if leaving expr, then currentchild should be at nchildren */
374  	         assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterdata->currentchild == iterator->curr->nchildren);
375  	         /* if visiting child, then currentchild should be a valid index */
376  	         assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterdata->currentchild < iterator->curr->nchildren);
377  	         /* if visiting child, then either we don't care whether we visited it already or it has not been visited yet */
378  	         assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterator->visitedtag == 0
379  	         || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag);
380  	
381  	         return iterator->curr;
382  	      }
383  	
384  	      case SCIP_EXPRITER_VISITINGCHILD:
385  	      {
386  	         SCIP_EXPR* child;
387  	
388  	         assert(iterdata->currentchild < iterator->curr->nchildren);
389  	
390  	         /* remember the parent and set the first child that should be visited of the new root */
391  	         child = iterator->curr->children[iterdata->currentchild];
392  	         child->iterdata[iterator->iterindex].parent = iterator->curr;
393  	         child->iterdata[iterator->iterindex].currentchild = 0;
394  	
395  	         /* visit child */
396  	         iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
397  	
398  	         return child;
399  	      }
400  	
401  	      case SCIP_EXPRITER_LEAVEEXPR:
402  	      {
403  	         /* go back to parent expression */
404  	
405  	         /* remember that this expression has been visited */
406  	         iterdata->visitedtag = iterator->visitedtag;
407  	
408  	         /* be in visitedchild stage for the parent */
409  	         iterator->dfsstage = SCIP_EXPRITER_VISITEDCHILD;
410  	
411  	         return iterdata->parent;
412  	      }
413  	
414  	      default:
415  	         /* unknown stage */
416  	         SCIPABORT();
417  	         return NULL;
418  	   }
419  	}
420  	
421  	/*
422  	 * private functions (expr.h)
423  	 */
424  	
425  	/** creates an expression iterator */
426  	SCIP_RETCODE SCIPexpriterCreate(
427  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
428  	   BMS_BLKMEM*           blkmem,             /**< block memory */
429  	   SCIP_EXPRITER**       iterator            /**< buffer to store expression iterator */
430  	   )
431  	{
432  	   assert(stat != NULL);
433  	   assert(blkmem  != NULL);
434  	   assert(iterator != NULL);
435  	
436  	   SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, iterator) );
437  	
438  	   (*iterator)->stat = stat;
439  	   (*iterator)->blkmem = blkmem;
440  	
441  	   return SCIP_OKAY;
442  	}
443  	
444  	/** frees an expression iterator */
445  	void SCIPexpriterFree(
446  	   SCIP_EXPRITER**       iterator            /**< pointer to the expression iterator */
447  	   )
448  	{
449  	   assert(iterator != NULL);
450  	   assert(*iterator != NULL);
451  	   assert((*iterator)->blkmem != NULL);
452  	
453  	   deinit(*iterator);
454  	
455  	   assert((*iterator)->queue == NULL);
456  	   assert((*iterator)->dfsnvisited == NULL);
457  	   assert((*iterator)->dfsexprs == NULL);
458  	
459  	   /* free iterator */
460  	   BMSfreeBlockMemory((*iterator)->blkmem, iterator);
461  	}
462  	
463  	/*
464  	 * public functions (pub_expr.h)
465  	 */
466  	
467  	#ifdef NDEBUG
468  	#undef SCIPexpriterIsInit
469  	#undef SCIPexpriterGetCurrent
470  	#undef SCIPexpriterGetStageDFS
471  	#undef SCIPexpriterGetChildIdxDFS
472  	#undef SCIPexpriterGetChildExprDFS
473  	#undef SCIPexpriterGetParentDFS
474  	#undef SCIPexpriterGetCurrentUserData
475  	#undef SCIPexpriterGetChildUserDataDFS
476  	#undef SCIPexpriterGetExprUserData
477  	#undef SCIPexpriterSetCurrentUserData
478  	#undef SCIPexpriterSetExprUserData
479  	#undef SCIPexpriterSetChildUserData
480  	#undef SCIPexpriterIsEnd
481  	#endif
482  	
483  	/** returns whether expression iterator is currently initialized */
484  	SCIP_Bool SCIPexpriterIsInit(
485  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
486  	   )
487  	{
488  	   assert(iterator != NULL);
489  	
490  	   return iterator->initialized;
491  	}
492  	
493  	/** initializes an expression iterator
494  	 *
495  	 * @note If `expr` is NULL, then iterator will be set into ended-state (SCIPexpriterIsEnd() is TRUE). Useful if following with SCIPexpriterRestartDFS().
496  	 *
497  	 * If type is DFS, then `stopstages` will be set to \ref SCIP_EXPRITER_ENTEREXPR.
498  	 * Use `SCIPexpriterSetStagesDFS` to change this.
499  	 */
500  	SCIP_RETCODE SCIPexpriterInit(
501  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
502  	   SCIP_EXPR*            expr,               /**< expression of the iterator, can be NULL */
503  	   SCIP_EXPRITER_TYPE    type,               /**< type of expression iterator */
504  	   SCIP_Bool             allowrevisit        /**< whether expression are allowed to be visited more than once */
505  	   )
506  	{
507  	   assert(iterator != NULL);
508  	
509  	   deinit(iterator);
510  	
511  	   /* store the new type of the iterator */
512  	   iterator->itertype = type;
513  	
514  	   /* get iterindex, if necessary */
515  	   if( !allowrevisit || type == SCIP_EXPRITER_DFS )
516  	   {
517  	      if( iterator->stat->nactiveexpriter + 1 >= SCIP_EXPRITER_MAXNACTIVE )
518  	      {
519  	         SCIPerrorMessage("Maximal number of active expression iterators reached at subscip-depth %d.\n",
520  	               iterator->stat->subscipdepth);
521  	         printBacktraces(iterator->stat->subscipdepth);
522  	         return SCIP_MAXDEPTHLEVEL;
523  	      }
524  	
525  	      iterator->iterindex = iterator->stat->nactiveexpriter++;
526  	
527  	      storeBacktrace(iterator->stat->subscipdepth, iterator->iterindex);
528  	   }
529  	   else
530  	   {
531  	      iterator->iterindex = -1;
532  	   }
533  	
534  	   /* get new tag to recognize visited expressions */
535  	   if( !allowrevisit )
536  	   {
537  	      iterator->visitedtag = ++iterator->stat->exprlastvisitedtag;
538  	   }
539  	   else
540  	   {
541  	      iterator->visitedtag = 0L;
542  	   }
543  	
544  	   switch( iterator->itertype )
545  	   {
546  	      case SCIP_EXPRITER_BFS:
547  	      {
548  	         SCIP_CALL( SCIPqueueCreate(&iterator->queue, MINBFSSIZE, 2.0) );
549  	
550  	         assert(iterator->queue != NULL);
551  	         SCIPqueueClear(iterator->queue);
552  	
553  	         if( expr == NULL )
554  	         {
555  	            iterator->curr = NULL;
556  	            break;
557  	         }
558  	
559  	         SCIP_CALL( SCIPqueueInsert(iterator->queue, expr) );
560  	
561  	         if( iterator->visitedtag != 0 )
562  	         {
563  	            assert(iterator->iterindex >= 0);
564  	            assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
565  	            assert(expr->iterdata[iterator->iterindex].visitedtag != iterator->visitedtag);
566  	
567  	            /* mark expression as being in the queue */
568  	            expr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
569  	         }
570  	
571  	         iterator->curr = SCIPexpriterGetNext(iterator);
572  	         break;
573  	      }
574  	
575  	      case SCIP_EXPRITER_RTOPOLOGIC :
576  	      {
577  	         SCIP_CALL( ensureStackSize(iterator, MINDFSSIZE) );
578  	
579  	         if( expr != NULL )
580  	         {
581  	            reverseTopologicalInsert(iterator, expr);
582  	            iterator->curr = SCIPexpriterGetNext(iterator);
583  	         }
584  	         else
585  	         {
586  	            iterator->curr = NULL;
587  	         }
588  	
589  	         break;
590  	      }
591  	
592  	      case SCIP_EXPRITER_DFS :
593  	      {
594  	         assert(iterator->iterindex >= 0);
595  	
596  	         iterator->stopstages = SCIP_EXPRITER_ENTEREXPR;
597  	         iterator->curr = expr;
598  	
599  	         if( expr == NULL )
600  	            break;
601  	
602  	         expr->iterdata[iterator->iterindex].currentchild = 0;
603  	         expr->iterdata[iterator->iterindex].parent = NULL;
604  	         iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
605  	
606  	         break;
607  	      }
608  	   }
609  	
610  	   iterator->initialized = TRUE;
611  	
612  	   return SCIP_OKAY;
613  	}
614  	
615  	/** restarts an already initialized expression iterator in DFS mode
616  	 *
617  	 * The expression iterator will continue from the given expression, not revisiting expressions that
618  	 * this iterator has already been visited (if initialized with `allowrevisit=FALSE`) and giving access
619  	 * to the same iterator specified expression data that may have been set already.
620  	 * Also the stop-stages are not reset.
621  	 *
622  	 * If revisiting is forbidden and given expr has already been visited, then the iterator will behave
623  	 * as on the end of iteration (SCIPexpriterIsEnd() is TRUE).
624  	 * If the enterexpr stage is not one of the stop stages, then the iterator will be moved forward
625  	 * (SCIPexpriterGetNext() is called).
626  	 *
627  	 * @return The current expression.
628  	 */
629  	SCIP_EXPR* SCIPexpriterRestartDFS(
630  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
631  	   SCIP_EXPR*            expr                /**< expression of the iterator */
632  	   )
633  	{
634  	   assert(iterator != NULL);
635  	   assert(iterator->initialized);
636  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
637  	
638  	   /* if we forbid revisiting and root expr has already been visited, then set curr to NULL, that is, be at end of iterator */
639  	   if( iterator->visitedtag > 0 && expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
640  	   {
641  	      iterator->curr = NULL;
642  	      return NULL;
643  	   }
644  	
645  	   /* set current to given expr, make it the root, and set stage to enterexpr */
646  	   iterator->curr = expr;
647  	   expr->iterdata[iterator->iterindex].currentchild = 0;
648  	   expr->iterdata[iterator->iterindex].parent = NULL;
649  	   iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
650  	
651  	   if( (iterator->stopstages & SCIP_EXPRITER_ENTEREXPR) == 0 )
652  	      return SCIPexpriterGetNext(iterator);
653  	
654  	   return iterator->curr;
655  	}
656  	
657  	/** specifies in which stages to stop a DFS iterator
658  	 *
659  	 * Parameter `stopstages` should be a bitwise OR of different \ref SCIP_EXPRITER_STAGE values
660  	 *
661  	 * If the current stage is not one of the `stopstages`, then the iterator will be moved on.
662  	 */
663  	void SCIPexpriterSetStagesDFS(
664  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
665  	   SCIP_EXPRITER_STAGE   stopstages          /**< the stages in which to stop when iterating via DFS */
666  	   )
667  	{
668  	   assert(iterator != NULL);
669  	
670  	   if( (iterator->dfsstage & stopstages) == 0 )
671  	   {
672  	      iterator->stopstages = stopstages;
673  	      (void) SCIPexpriterGetNext(iterator);
674  	   }
675  	   else
676  	   {
677  	      iterator->stopstages = stopstages;
678  	   }
679  	}
680  	
681  	/** gets the current expression that the expression iterator points to */
682  	SCIP_EXPR* SCIPexpriterGetCurrent(
683  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
684  	   )
685  	{
686  	   assert(iterator != NULL);
687  	
688  	   return iterator->curr;
689  	}
690  	
691  	/** gets the current stage that the expression iterator is in when using DFS
692  	 *
693  	 * If the iterator has finished (SCIPexpriterIsEnd() is TRUE), then the stage is undefined.
694  	 */
695  	SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(
696  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
697  	   )
698  	{
699  	   assert(iterator != NULL);
700  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
701  	
702  	   return iterator->dfsstage;
703  	}
704  	
705  	/** gets the index of the child that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */
706  	int SCIPexpriterGetChildIdxDFS(
707  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
708  	   )
709  	{
710  	   assert(iterator != NULL);
711  	   assert(iterator->curr != NULL);
712  	   assert(iterator->iterindex >= 0);
713  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
714  	   assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
715  	
716  	   return iterator->curr->iterdata[iterator->iterindex].currentchild;
717  	}
718  	
719  	/** gets the child expression that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */
720  	SCIP_EXPR* SCIPexpriterGetChildExprDFS(
721  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
722  	   )
723  	{
724  	   assert(iterator != NULL);
725  	   assert(iterator->curr != NULL);
726  	   assert(iterator->iterindex >= 0);
727  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
728  	   assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
729  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
730  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
731  	
732  	   return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild];
733  	}
734  	
735  	/** gives the parent of the current expression of an expression iteration if in DFS mode
736  	 *
737  	 * @return the expression from which the current expression has been accessed
738  	 */
739  	SCIP_EXPR* SCIPexpriterGetParentDFS(
740  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
741  	   )
742  	{
743  	   assert(iterator != NULL);
744  	   assert(iterator->curr != NULL);
745  	   assert(iterator->iterindex >= 0);
746  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
747  	
748  	   return iterator->curr->iterdata[iterator->iterindex].parent;
749  	}
750  	
751  	/** gives the iterator specific user data of the current expression
752  	 *
753  	 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
754  	 */
755  	SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData(
756  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
757  	   )
758  	{
759  	   assert(iterator != NULL);
760  	   assert(iterator->curr != NULL);
761  	   assert(iterator->iterindex >= 0);
762  	
763  	   return iterator->curr->iterdata[iterator->iterindex].userdata;
764  	}
765  	
766  	/** gives the iterator specific user data of the current expressions current child
767  	 *
768  	 * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD
769  	 */
770  	SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS(
771  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
772  	   )
773  	{
774  	   assert(iterator != NULL);
775  	   assert(iterator->curr != NULL);
776  	   assert(iterator->iterindex >= 0);
777  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
778  	   assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
779  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
780  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
781  	
782  	   return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata;
783  	}
784  	
785  	/** gives the iterator specific user data of a given expression
786  	 *
787  	 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
788  	 */
789  	SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData(
790  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
791  	   SCIP_EXPR*            expr                /**< expression for which to get the userdata of this iterator */
792  	   )
793  	{
794  	   assert(iterator != NULL);
795  	   assert(expr != NULL);
796  	   assert(iterator->iterindex >= 0);
797  	
798  	   return expr->iterdata[iterator->iterindex].userdata;
799  	}
800  	
801  	/** sets the iterator specific user data of the current expression for an expression iteration if in DFS mode
802  	 *
803  	 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
804  	 */
805  	void SCIPexpriterSetCurrentUserData(
806  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
807  	   SCIP_EXPRITER_USERDATA userdata           /**< data to be stored */
808  	   )
809  	{
810  	   assert(iterator != NULL);
811  	   assert(iterator->curr != NULL);
812  	   assert(iterator->iterindex >= 0);
813  	
814  	   iterator->curr->iterdata[iterator->iterindex].userdata = userdata;
815  	}
816  	
817  	/** sets the iterator specific user data of a given expression
818  	 *
819  	 * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
820  	 */
821  	void SCIPexpriterSetExprUserData(
822  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
823  	   SCIP_EXPR*            expr,               /**< expression where to set iterator data */
824  	   SCIP_EXPRITER_USERDATA userdata           /**< data to be stored in current child */
825  	   )
826  	{
827  	   assert(iterator != NULL);
828  	   assert(iterator->iterindex >= 0);
829  	
830  	   expr->iterdata[iterator->iterindex].userdata = userdata;
831  	}
832  	
833  	/** sets the iterator specific user data of the current expressions current child
834  	 *
835  	 * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD
836  	 */
837  	void SCIPexpriterSetChildUserData(
838  	   SCIP_EXPRITER*        iterator,           /**< expression iterator */
839  	   SCIP_EXPRITER_USERDATA userdata           /**< data to be stored in current child */
840  	   )
841  	{
842  	   assert(iterator != NULL);
843  	   assert(iterator->curr != NULL);
844  	   assert(iterator->iterindex >= 0);
845  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
846  	   assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
847  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
848  	   assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
849  	
850  	   iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata = userdata;
851  	}
852  	
853  	/** moves the iterator to the next expression according to the mode of the expression iterator
854  	 *
855  	 * @return the next expression, if any, and NULL otherwise
856  	 */
857  	SCIP_EXPR* SCIPexpriterGetNext(
858  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
859  	   )
860  	{
861  	   /* move to the next expression according to iterator type */
862  	   switch( iterator->itertype )
863  	   {
864  	      case SCIP_EXPRITER_BFS:
865  	      {
866  	         iterator->curr = doBfsNext(iterator);
867  	         break;
868  	      }
869  	
870  	      case SCIP_EXPRITER_RTOPOLOGIC :
871  	      {
872  	         iterator->curr = doReverseTopologicalNext(iterator);
873  	         if( iterator->visitedtag != 0 )
874  	         {
875  	            assert(iterator->iterindex >= 0);
876  	            assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
877  	
878  	            /* skip already visited expressions */
879  	            while( iterator->curr != NULL )
880  	            {
881  	               if( iterator->curr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
882  	               {
883  	                  /* if curr has already been visited, get next one
884  	                   * TODO this isn't really efficient, since we still walk through already visited expressions
885  	                   */
886  	                  iterator->curr = doReverseTopologicalNext(iterator);
887  	               }
888  	               else
889  	               {
890  	                  /* curr has not been visited yet, so mark it as visited and interrupt loop */
891  	                  iterator->curr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
892  	                  break;
893  	               }
894  	            }
895  	         }
896  	         break;
897  	      }
898  	
899  	      case SCIP_EXPRITER_DFS :
900  	      {
901  	         assert(iterator->iterindex >= 0);
902  	
903  	         /* get next until we are in a stopstage again
904  	          * this might give expressions more than once, depending on what the stopstages are
905  	          */
906  	         do
907  	         {
908  	            iterator->curr = doDfsNext(iterator);
909  	         }
910  	         while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 );
911  	
912  	         break;
913  	      }
914  	   }
915  	
916  	   return iterator->curr;
917  	}
918  	
919  	/** moves a DFS iterator to one of the next expressions
920  	 *
921  	 * - If in \ref SCIP_EXPRITER_ENTEREXPR stage, then all children of that expression will be skipped.
922  	 *   If \ref SCIP_EXPRITER_LEAVEEXPR is one of the `stopstages`, then it will be the next stage. Otherwise, the iterator will move further on (go to the parent, etc).
923  	 * - If in \ref SCIP_EXPRITER_VISITINGCHILD stage, then the child that was going to be visited next will be skipped and the iterator will be moved on to the next child (if any).
924  	 * - If in \ref SCIP_EXPRITER_VISITEDCHILD stage, then all remaining children will be skipped and we move on to the \ref SCIP_EXPRITER_LEAVEEXPR stage (if a stop stage, otherwise further on).
925  	 * - It is not allowed to call this function when in \ref SCIP_EXPRITER_LEAVEEXPR stage.
926  	 *
927  	 * @return the next expression, if any, and NULL otherwise
928  	 */
929  	SCIP_EXPR* SCIPexpriterSkipDFS(
930  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
931  	   )
932  	{
933  	   assert(iterator != NULL);
934  	   assert(iterator->curr != NULL);
935  	   assert(iterator->itertype == SCIP_EXPRITER_DFS);
936  	   assert(iterator->iterindex >= 0);
937  	
938  	   switch( iterator->dfsstage )
939  	   {
940  	      case SCIP_EXPRITER_ENTEREXPR :
941  	      case SCIP_EXPRITER_VISITEDCHILD :
942  	      {
943  	         /* move directly to leaveexpr */
944  	         iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR;
945  	         /* if leaveexpr is not a stopstage, then move on */
946  	         while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 )
947  	            iterator->curr = doDfsNext(iterator);
948  	         return iterator->curr;
949  	      }
950  	
951  	      case SCIP_EXPRITER_VISITINGCHILD :
952  	      {
953  	         /* skip the child to be visited */
954  	         /* pretend we just visited this child and get next */
955  	         iterator->dfsstage = SCIP_EXPRITER_VISITEDCHILD;
956  	         return SCIPexpriterGetNext(iterator);
957  	      }
958  	
959  	      case SCIP_EXPRITER_LEAVEEXPR :
960  	      default :
961  	         SCIPerrorMessage("SCIPexpriterSkipDFS called in invalid stage %u", iterator->dfsstage);
962  	         SCIPABORT();
963  	         return iterator->curr;
964  	   }
965  	}
966  	
967  	/** returns whether the iterator visited all expressions already */
968  	SCIP_Bool SCIPexpriterIsEnd(
969  	   SCIP_EXPRITER*        iterator            /**< expression iterator */
970  	   )
971  	{
972  	   assert(iterator != NULL);
973  	
974  	   return iterator->curr == NULL;
975  	}
976