2 * This file is part of the GROMACS molecular simulation package.
4 * Copyright (c) 2009,2010,2011,2012,2013 by the GROMACS development team.
5 * Copyright (c) 2014,2015,2016,2017,2018 by the GROMACS development team.
6 * Copyright (c) 2019,2020, by the GROMACS development team, led by
7 * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
8 * and including many others, as listed in the AUTHORS file in the
9 * top-level source directory and at http://www.gromacs.org.
11 * GROMACS is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public License
13 * as published by the Free Software Foundation; either version 2.1
14 * of the License, or (at your option) any later version.
16 * GROMACS is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Lesser General Public License for more details.
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with GROMACS; if not, see
23 * http://www.gnu.org/licenses, or write to the Free Software Foundation,
24 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
26 * If you want to redistribute modifications to GROMACS, please
27 * consider that scientific software is very special. Version
28 * control is crucial - bugs must be traceable. We will be happy to
29 * consider code for inclusion in the official distribution, but
30 * derived work must not be called official GROMACS. Details are found
31 * in the README & COPYING files - if they are missing, get the
32 * official version at http://www.gromacs.org.
34 * To help us fund GROMACS development, we humbly ask that you cite
35 * the research papers on the package. Check out http://www.gromacs.org.
38 * \brief Selection compilation and optimization.
41 * Better error handling and memory management in error situations.
42 * At least, the main compilation function leaves the selection collection in
43 * a bad state if an error occurs.
46 * The memory usage could still be optimized.
47 * Use of memory pooling could still be extended, and a lot of redundant
48 * gmin/gmax data could be eliminated for complex arithmetic expressions.
50 * \author Teemu Murtola <teemu.murtola@gmail.com>
51 * \ingroup module_selection
54 * \page page_module_selection_compiler Selection compilation
56 * The compiler takes the selection element tree from the selection parser
57 * (see \ref page_module_selection_parser) as input.
58 * The selection parser is quite independent of selection evaluation details,
59 * and the compiler processes the tree to conform to what the evaluation
61 * For better control and optimization possibilities, the compilation is
62 * done on all selections simultaneously.
63 * Hence, all the selections should be parsed before the compiler can be
66 * The compiler initializes all fields in gmx::SelectionTreeElement not
67 * initialized by the parser: gmx::SelectionTreeElement::v (some fields have
68 * already been initialized by the parser),
69 * gmx::SelectionTreeElement::evaluate, and gmx::SelectionTreeElement::u
70 * (again, some elements have been initialized in the parser).
71 * The gmx::SelectionTreeElement::cdata field is used during the compilation to store
72 * internal data, but the data is freed when the compiler returns.
74 * In addition to initializing the elements, the compiler reorganizes the tree
75 * to simplify and optimize evaluation. The compiler also evaluates the static
76 * parts of the selection: in the end of the compilation, static parts have
77 * been replaced by the result of the evaluation.
79 * The compiler is invoked using gmx::SelectionCompiler.
80 * The gmx::SelectionCompiler::compile() method does the compilation in several
81 * passes over the gmx::SelectionTreeElement tree.
82 * -# Defaults are set for the position type and flags of position calculation
83 * methods that were not explicitly specified in the user input.
84 * -# Subexpressions are extracted: a separate root is created for each
85 * subexpression, and placed before the expression is first used.
86 * Currently, only variables and expressions used to evaluate parameter
87 * values are extracted, but common subexpression could also be detected
89 * -# A second pass (in fact, multiple passes because of interdependencies)
90 * with simple reordering and initialization is done:
91 * -# Boolean expressions are combined such that one element can evaluate,
92 * e.g., "A and B and C". The subexpressions in boolean expression are
93 * reordered such that static expressions come first without otherwise
94 * altering the relative order of the expressions.
95 * -# The compiler data structure is allocated for each element, and
96 * the fields are initialized, with the exception of the contents of
97 * \c gmax and \c gmin fields. This is the part that needs multiple
98 * passes, because some flags are set recursively based on which elements
99 * refer to an element, and these flags need to be set to initialize
101 * -# The gmx::SelectionTreeElement::evaluate field is set to the correct
102 * evaluation function from evaluate.h.
104 * -# The evaluation function of all elements is replaced with the
105 * analyze_static() function to be able to initialize the element before
106 * the actual evaluation function is called.
107 * The evaluation machinery is then called to initialize the whole tree,
108 * while simultaneously evaluating the static expressions.
109 * During the evaluation, track is kept of the smallest and largest
110 * possible selections, and these are stored in the internal compiler
111 * data structure for each element.
112 * To be able to do this for all possible values of dynamical expressions,
113 * special care needs to be taken with boolean expressions because they
114 * are short-circuiting. This is done through the
115 * \c SEL_CDATA_EVALMAX flag, which makes dynamic child expressions
116 * of \c BOOL_OR expressions evaluate to empty groups, while subexpressions
117 * of \c BOOL_AND are evaluated to largest possible groups.
118 * Memory is also allocated to store the results of the evaluation.
119 * For each element, analyze_static() calls the actual evaluation function
120 * after the element has been properly initialized.
121 * -# Another evaluation pass is done over subexpressions with more than
122 * one reference to them. These cannot be completely processed during the
123 * first pass, because it is not known whether later references require
124 * additional evaluation of static expressions.
125 * -# Unused subexpressions are removed. For efficiency reasons (and to avoid
126 * some checks), this is actually done several times already earlier in
127 * the compilation process.
128 * -# Most of the processing is now done, and the next pass simply sets the
129 * evaluation group of root elements to the largest selection as determined
130 * in pass 4. For root elements of subexpressions that should not be
131 * evaluated before they are referred to, the evaluation group/function is
132 * cleared. At the same time, position calculation data is initialized for
133 * for selection method elements that require it. Compiler data is also
134 * freed as it is no longer needed.
135 * -# A final pass initializes the total masses and charges in the
136 * \c gmx_ana_selection_t data structures.
138 * The actual evaluation of the selection is described in the documentation
139 * of the functions in evaluate.h.
142 * Some combinations of method parameter flags are not yet properly treated by
143 * the compiler or the evaluation functions in evaluate.cpp. All the ones used by
144 * currently implemented methods should work, but new combinations might not.
147 * \section selcompiler_tree Element tree after compilation
149 * After the compilation, the selection element tree is suitable for
150 * gmx_ana_selcollection_evaluate().
151 * Enough memory has been allocated for gmx::SelectionTreeElement::v
152 * (and gmx::SelectionTreeElement::cgrp for \ref SEL_SUBEXPR elements) to allow
153 * the selection to be evaluated without allocating any memory.
156 * \subsection selcompiler_tree_root Root elements
158 * The top level of the tree consists of a chain of \ref SEL_ROOT elements.
159 * These are used for two purposes:
160 * -# A selection that should be evaluated.
161 * These elements appear in the same order as the selections in the input.
162 * For these elements, gmx::SelectionTreeElement::v has been set to the
163 * maximum possible group that the selection can evaluate to (only for
164 * dynamic selections), and gmx::SelectionTreeElement::cgrp has been set to
165 * use a NULL group for evaluation.
166 * -# A subexpression that appears in one or more selections.
167 * Each selection that gives a value for a method parameter is a
168 * potential subexpression, as is any variable value.
169 * Only subexpressions that require evaluation for each frame are left
170 * after the selection is compiled.
171 * Each subexpression appears in the chain before any references to it.
172 * For these elements, gmx::SelectionTreeElement::cgrp has been set to the
173 * group that should be used to evaluate the subexpression.
174 * If gmx::SelectionTreeElement::cgrp is empty, the total evaluation group
175 * is not known in advance or it is more efficient to evaluate the
176 * subexpression only when it is referenced. If this is the case,
177 * gmx::SelectionTreeElement::evaluate is also NULL.
179 * The children of the \ref SEL_ROOT elements can be used to distinguish
180 * the two types of root elements from each other; the rules are the same
181 * as for the parsed tree (see \ref selparser_tree_root).
182 * Subexpressions are treated as if they had been provided through variables.
184 * Selection names are stored as after parsing (see \ref selparser_tree_root).
187 * \subsection selcompiler_tree_const Constant elements
189 * All (sub)selections that do not require particle positions have been
190 * replaced with \ref SEL_CONST elements.
191 * Constant elements from the parser are also retained if present in
192 * dynamic parts of the selections.
193 * Several constant elements with a NULL gmx::SelectionTreeElement::evaluate
194 * are left for debugging purposes; of these, only the ones for \ref BOOL_OR
195 * expressions are used during evaluation.
197 * The value is stored in gmx::SelectionTreeElement::v, and for group values
198 * with an evaluation function set, also in gmx::SelectionTreeElement::cgrp.
199 * For \ref GROUP_VALUE elements, unnecessary atoms (i.e., atoms that
200 * could never be selected) have been removed from the value.
202 * \ref SEL_CONST elements have no children.
205 * \subsection selcompiler_tree_method Method evaluation elements
207 * All selection methods that need to be evaluated dynamically are described
208 * by a \ref SEL_EXPRESSION element. The gmx::SelectionTreeElement::method and
209 * gmx::SelectionTreeElement::mdata fields have already been initialized by the parser,
210 * and the compiler only calls the initialization functions in the method
211 * data structure to do some additional initialization of these fields at
212 * appropriate points. If the gmx::SelectionTreeElement::pc data field has been
213 * created by the parser, the compiler initializes the data structure properly
214 * once the required positions are known. If the gmx::SelectionTreeElement::pc
215 * field is NULL after the parser, but the method provides only
216 * sel_updatefunc_pos(), an appropriate position calculation data structure is
217 * created. If gmx::SelectionTreeElement::pc is not NULL,
218 * gmx::SelectionTreeElement::pos is also initialized to hold the positions
221 * Children of these elements are of type \ref SEL_SUBEXPRREF, and describe
222 * parameter values that need to be evaluated for each frame. See the next
223 * section for more details.
224 * \ref SEL_CONST children can also appear, and stand for parameters that get
225 * their value from a static expression. These elements are present only for
226 * debugging purposes: they always have a NULL evaluation function.
229 * \subsection selcompiler_tree_subexpr Subexpression elements
231 * As described in \ref selcompiler_tree_root, subexpressions are created
232 * for each variable and each expression that gives a value to a selection
233 * method parameter. As the only child of the \ref SEL_ROOT element,
234 * these elements have a \ref SEL_SUBEXPR element. The \ref SEL_SUBEXPR
235 * element has a single child, which evaluates the actual expression.
236 * After compilation, only subexpressions that require particle positions
237 * for evaluation are left.
238 * For non-variable subexpression, automatic names have been generated to
241 * For \ref SEL_SUBEXPR elements, memory has been allocated for
242 * gmx::SelectionTreeElement::cgrp to store the group for which the expression
243 * has been evaluated during the current frame. This is only done if full
244 * subexpression evaluation by _gmx_sel_evaluate_subexpr() is needed; the other
245 * evaluation functions do not require this memory.
247 * \ref SEL_SUBEXPRREF elements are used to describe references to
248 * subexpressions. They have always a single child, which is the
249 * \ref SEL_SUBEXPR element being referenced.
251 * If a subexpression is used only once, the evaluation has been optimized by
252 * setting the child of the \ref SEL_SUBEXPR element to evaluate the value of
253 * \ref SEL_SUBEXPRREF directly (in the case of memory pooling, this is managed
254 * by the evaluation functions). In such cases, the evaluation routines for the
255 * \ref SEL_SUBEXPRREF and \ref SEL_SUBEXPR elements only propagate some status
256 * information, but do not unnecessarily copy the values.
259 * \subsection selcompiler_tree_bool Boolean elements
261 * \ref SEL_BOOLEAN elements have been merged such that one element
262 * may carry out evaluation of more than one operation of the same type.
263 * The static parts of the expressions have been evaluated, and are placed
264 * in the first child. These are followed by the dynamic expressions, in the
265 * order provided by the user.
268 * \subsection selcompiler_tree_arith Arithmetic elements
270 * Constant and static expressions in \ref SEL_ARITHMETIC elements have been
272 * Currently, no other processing is done.
276 #include "compiler.h"
283 #include "gromacs/math/vec.h"
284 #include "gromacs/selection/indexutil.h"
285 #include "gromacs/selection/selection.h"
286 #include "gromacs/utility/exceptions.h"
287 #include "gromacs/utility/gmxassert.h"
288 #include "gromacs/utility/smalloc.h"
289 #include "gromacs/utility/stringutil.h"
291 #include "evaluate.h"
292 #include "keywords.h"
295 #include "selectioncollection_impl.h"
297 #include "selmethod.h"
299 using gmx::SelectionLocation
;
300 using gmx::SelectionTreeElement
;
301 using gmx::SelectionTreeElementPointer
;
310 * Whether a subexpression needs to evaluated for all atoms.
312 * This flag is set for \ref SEL_SUBEXPR elements that are used to
313 * evaluate non-atom-valued selection method parameters, as well as
314 * those that are used directly as values of selections.
316 SEL_CDATA_FULLEVAL
= 1,
318 * Whether the whole subexpression should be treated as static.
320 * This flag is always false if \ref SEL_DYNAMIC is set for the element,
321 * but it is also false for static elements within common subexpressions.
323 SEL_CDATA_STATIC
= 2,
324 /** Whether the subexpression will always be evaluated in the same group. */
325 SEL_CDATA_STATICEVAL
= 4,
326 /** Whether the compiler evaluation routine should return the maximal selection. */
327 SEL_CDATA_EVALMAX
= 8,
328 /** Whether memory has been allocated for \p gmin and \p gmax. */
329 SEL_CDATA_MINMAXALLOC
= 16,
330 /** Whether to update \p gmin and \p gmax in static analysis. */
331 SEL_CDATA_DOMINMAX
= 256,
332 /** Whether the subexpression uses simple pass evaluation functions. */
333 SEL_CDATA_SIMPLESUBEXPR
= 32,
335 * Whether a static subexpression needs to support multiple evaluations.
337 * This flag may only be set on \ref SEL_SUBEXPR elements that also have
338 * SEL_CDATA_SIMPLESUBEXPR.
340 SEL_CDATA_STATICMULTIEVALSUBEXPR
= 64,
341 /** Whether this expression is a part of a common subexpression. */
342 SEL_CDATA_COMMONSUBEXPR
= 128
346 * Internal data structure used by the compiler.
348 typedef struct t_compiler_data
350 /** The real evaluation method. */
351 gmx::sel_evalfunc evaluate
;
352 /** Number of references to a \ref SEL_SUBEXPR element. */
354 /** Flags for specifying how to treat this element during compilation. */
356 /** Smallest selection that can be selected by the subexpression. */
357 gmx_ana_index_t
* gmin
;
358 /** Largest selection that can be selected by the subexpression. */
359 gmx_ana_index_t
* gmax
;
363 /********************************************************************
364 * COMPILER UTILITY FUNCTIONS
365 ********************************************************************/
368 * Helper method for printing out debug information about a min/max group.
370 static void print_group_info(FILE* fp
, const char* name
, const SelectionTreeElement
& sel
, gmx_ana_index_t
* g
)
372 fprintf(fp
, " %s=", name
);
375 fprintf(fp
, "(null)");
377 else if (sel
.cdata
->flags
& SEL_CDATA_MINMAXALLOC
)
379 fprintf(fp
, "(%d atoms, %p)", g
->isize
, static_cast<void*>(g
));
381 else if (sel
.v
.type
== GROUP_VALUE
&& g
== sel
.v
.u
.g
)
383 fprintf(fp
, "(static, %p)", static_cast<void*>(g
));
387 fprintf(fp
, "%p", static_cast<void*>(g
));
392 * \param[in] fp File handle to receive the output.
393 * \param[in] sel Selection element to print.
394 * \param[in] level Indentation level, starting from zero.
396 void _gmx_selelem_print_compiler_info(FILE* fp
, const SelectionTreeElement
& sel
, int level
)
402 fprintf(fp
, "%*c cdata: flg=", level
* 2 + 1, ' ');
403 if (sel
.cdata
->flags
& SEL_CDATA_FULLEVAL
)
407 if (!(sel
.cdata
->flags
& SEL_CDATA_STATIC
))
411 if (sel
.cdata
->flags
& SEL_CDATA_STATICEVAL
)
415 if (sel
.cdata
->flags
& SEL_CDATA_EVALMAX
)
419 if (sel
.cdata
->flags
& SEL_CDATA_MINMAXALLOC
)
423 if (sel
.cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
427 if (sel
.cdata
->flags
& SEL_CDATA_STATICMULTIEVALSUBEXPR
)
431 if (sel
.cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
)
435 if (!sel
.cdata
->flags
)
439 if (sel
.cdata
->refcount
> 0)
441 fprintf(fp
, " refc=%d", sel
.cdata
->refcount
);
443 fprintf(fp
, " eval=");
444 _gmx_sel_print_evalfunc_name(fp
, sel
.cdata
->evaluate
);
445 print_group_info(fp
, "gmin", sel
, sel
.cdata
->gmin
);
446 print_group_info(fp
, "gmax", sel
, sel
.cdata
->gmax
);
453 void SelectionTreeElement::freeCompilerData()
457 evaluate
= cdata
->evaluate
;
458 if (cdata
->flags
& SEL_CDATA_MINMAXALLOC
)
460 gmx_ana_index_deinit(cdata
->gmin
);
461 gmx_ana_index_deinit(cdata
->gmax
);
473 * Allocates memory for storing the evaluated value of a selection element.
475 * \param sel Selection element to initialize
476 * \param[in] isize Maximum evaluation group size.
477 * \param[in] bChildEval true if children have already been processed.
479 * If called more than once, memory is (re)allocated to ensure that the
480 * maximum of the \p isize values can be stored.
482 * Allocation of POS_VALUE selection elements is a special case, and is
483 * handled by alloc_selection_pos_data().
485 static void alloc_selection_data(const SelectionTreeElementPointer
& sel
, int isize
, bool bChildEval
)
489 GMX_RELEASE_ASSERT(sel
->v
.type
!= POS_VALUE
, "Wrong allocation method called");
494 /* Find out the number of elements to allocate */
495 if (sel
->flags
& SEL_SINGLEVAL
)
499 else if (sel
->flags
& SEL_ATOMVAL
)
503 else /* sel->flags should contain SEL_VARNUMVAL */
505 // TODO: Consider whether the bChildEval is any longer necessary.
510 SelectionTreeElementPointer child
= sel
;
511 if (sel
->type
== SEL_SUBEXPRREF
)
513 GMX_RELEASE_ASSERT(sel
->child
&& sel
->child
->type
== SEL_SUBEXPR
,
514 "Subexpression expected for subexpression reference");
515 child
= sel
->child
->child
;
516 GMX_RELEASE_ASSERT(child
, "Subexpression elements should always have a child element");
518 nalloc
= child
->v
.nr
;
520 /* Allocate memory for sel->v.u if needed */
521 if (sel
->flags
& SEL_ALLOCVAL
)
523 _gmx_selvalue_reserve(&sel
->v
, nalloc
);
525 /* Reserve memory inside group structure if SEL_ALLOCDATA is set. */
526 if ((sel
->flags
& SEL_ALLOCDATA
) && sel
->v
.type
== GROUP_VALUE
)
528 gmx_ana_index_reserve(sel
->v
.u
.g
, isize
);
533 * Allocates memory for storing the evaluated value of a selection element.
535 * \param sel Selection element to initialize.
537 * Allocation of POS_VALUE selection elements is a special case, and is
538 * handled by this function instead of by alloc_selection_data().
540 static void alloc_selection_pos_data(const SelectionTreeElementPointer
& sel
)
544 GMX_RELEASE_ASSERT(sel
->v
.type
== POS_VALUE
, "Wrong allocation method called");
545 GMX_RELEASE_ASSERT(!(sel
->flags
& SEL_ATOMVAL
), "Per-atom evaluated positions not implemented");
551 SelectionTreeElementPointer child
= sel
;
552 if (sel
->type
== SEL_SUBEXPRREF
)
554 GMX_RELEASE_ASSERT(sel
->child
&& sel
->child
->type
== SEL_SUBEXPR
,
555 "Subexpression expected for subexpression reference");
556 child
= sel
->child
->child
;
557 GMX_RELEASE_ASSERT(child
, "Subexpression elements should always have a child element");
559 nalloc
= child
->v
.u
.p
->count();
560 isize
= child
->v
.u
.p
->m
.b
.nra
;
562 /* For positions, we want to allocate just a single structure
563 * for nalloc positions. */
564 if (sel
->flags
& SEL_ALLOCVAL
)
566 _gmx_selvalue_reserve(&sel
->v
, 1);
569 /* Reserve memory inside position structure if SEL_ALLOCDATA is set. */
570 if (sel
->flags
& SEL_ALLOCDATA
)
572 gmx_ana_pos_reserve(sel
->v
.u
.p
, nalloc
, isize
);
577 * Replace the evaluation function of each element in the subtree.
579 * \param sel Root of the selection subtree to process.
580 * \param[in] eval The new evaluation function.
582 static void set_evaluation_function(const SelectionTreeElementPointer
& sel
, gmx::sel_evalfunc eval
)
584 sel
->evaluate
= eval
;
585 if (sel
->type
!= SEL_SUBEXPRREF
)
587 SelectionTreeElementPointer child
= sel
->child
;
590 set_evaluation_function(child
, eval
);
597 /********************************************************************
598 * POSITION KEYWORD DEFAULT INITIALIZATION
599 ********************************************************************/
602 * Initializes default values for position keyword evaluation.
604 * \param[in,out] root Root of the element tree to initialize.
605 * \param[in] spost Default output position type.
606 * \param[in] rpost Default reference position type.
607 * \param[in] sel Selection that the element evaluates the positions
608 * for, or NULL if the element is an internal element.
610 static void init_pos_keyword_defaults(SelectionTreeElement
* root
,
613 const gmx::internal::SelectionData
* sel
)
615 /* Selections use largest static group by default, while
616 * reference positions use the whole residue/molecule. */
617 if (root
->type
== SEL_EXPRESSION
)
619 bool bSelection
= (sel
!= nullptr);
620 int flags
= bSelection
? POS_COMPLMAX
: POS_COMPLWHOLE
;
623 if (sel
->hasFlag(gmx::efSelection_DynamicMask
))
625 flags
|= POS_MASKONLY
;
627 if (sel
->hasFlag(gmx::efSelection_EvaluateVelocities
))
629 flags
|= POS_VELOCITIES
;
631 if (sel
->hasFlag(gmx::efSelection_EvaluateForces
))
636 _gmx_selelem_set_kwpos_type(root
, bSelection
? spost
: rpost
);
637 _gmx_selelem_set_kwpos_flags(root
, flags
);
639 /* Change the defaults once we are no longer processing modifiers */
640 if (root
->type
!= SEL_ROOT
&& root
->type
!= SEL_MODIFIER
&& root
->type
!= SEL_SUBEXPRREF
641 && root
->type
!= SEL_SUBEXPR
)
645 /* Recurse into children */
646 SelectionTreeElementPointer child
= root
->child
;
649 init_pos_keyword_defaults(child
.get(), spost
, rpost
, sel
);
655 /********************************************************************
656 * SUBEXPRESSION PROCESSING
657 ********************************************************************/
660 * Reverses the chain of selection elements starting at \p root.
662 * \param root First selection in the whole selection chain.
663 * \returns The new first element for the chain.
665 static SelectionTreeElementPointer
reverse_selelem_chain(const SelectionTreeElementPointer
& root
)
667 SelectionTreeElementPointer prev
;
668 SelectionTreeElementPointer item
= root
;
671 SelectionTreeElementPointer next
= item
->next
;
680 * Removes subexpressions that don't have any references.
682 * \param root First selection in the whole selection chain.
683 * \returns The new first element for the chain.
685 * The elements are processed in reverse order to correctly detect
686 * subexpressions only referred to by other subexpressions.
688 static SelectionTreeElementPointer
remove_unused_subexpressions(SelectionTreeElementPointer root
)
692 return SelectionTreeElementPointer();
694 root
= reverse_selelem_chain(root
);
695 while (root
->child
->type
== SEL_SUBEXPR
&& root
->child
.unique())
697 // Frees the root element.
700 SelectionTreeElementPointer prev
= root
;
701 SelectionTreeElementPointer item
= root
->next
;
704 SelectionTreeElementPointer next
= item
->next
;
705 if (item
->child
->type
== SEL_SUBEXPR
&& item
->child
.unique())
707 // Frees the current item when it goes out of scope.
716 return reverse_selelem_chain(root
);
720 * Creates a name with a running number for a subexpression.
722 * \param[in,out] sel The subexpression to be named.
723 * \param[in] i Running number for the subexpression.
725 * The name of the selection becomes "SubExpr N", where N is \p i;
726 * Memory is allocated for the name and the name is stored both as the
727 * name of the subexpression element and as
728 * gmx::SelectionTreeElement::u::cgrp::name; the latter is freed by
729 * _gmx_selelem_free().
731 static void create_subexpression_name(const SelectionTreeElementPointer
& sel
, int i
)
733 std::string
name(gmx::formatString("SubExpr %d", i
));
738 * Processes and extracts subexpressions from a given selection subtree.
740 * \param sel Root of the subtree to process.
741 * \param subexprn Pointer to a subexpression counter.
742 * \returns Pointer to a chain of subselections, or NULL if none were found.
744 * This function finds recursively all \ref SEL_SUBEXPRREF elements below
745 * the given root element and ensures that their children are within
746 * \ref SEL_SUBEXPR elements. It also creates a chain of \ref SEL_ROOT elements
747 * that contain the subexpression as their children and returns the first
748 * of these root elements.
750 static SelectionTreeElementPointer
extract_item_subselections(const SelectionTreeElementPointer
& sel
,
753 SelectionTreeElementPointer root
;
754 SelectionTreeElementPointer subexpr
;
755 SelectionTreeElementPointer child
= sel
->child
;
761 root
= subexpr
= extract_item_subselections(child
, subexprn
);
765 subexpr
->next
= extract_item_subselections(child
, subexprn
);
767 while (subexpr
&& subexpr
->next
)
769 subexpr
= subexpr
->next
;
771 /* The latter check excludes variable references. */
772 if (child
->type
== SEL_SUBEXPRREF
&& child
->child
->type
!= SEL_SUBEXPR
)
774 SelectionLocation location
= child
->child
->location();
775 /* Create the root element for the subexpression */
778 root
= std::make_shared
<SelectionTreeElement
>(SEL_ROOT
, location
);
783 subexpr
->next
= std::make_shared
<SelectionTreeElement
>(SEL_ROOT
, location
);
784 subexpr
= subexpr
->next
;
786 /* Create the subexpression element and
787 * move the actual subexpression under the created element. */
788 subexpr
->child
= std::make_shared
<SelectionTreeElement
>(SEL_SUBEXPR
, location
);
789 _gmx_selelem_set_vtype(subexpr
->child
, child
->v
.type
);
790 subexpr
->child
->child
= child
->child
;
791 child
->child
= subexpr
->child
;
792 create_subexpression_name(subexpr
->child
, ++*subexprn
);
793 /* Set the flags for the created elements */
794 subexpr
->flags
|= (child
->flags
& SEL_VALFLAGMASK
);
795 subexpr
->child
->flags
|= (child
->flags
& SEL_VALFLAGMASK
);
797 if (child
->type
== SEL_SUBEXPRREF
)
799 child
->setName(child
->child
->name());
808 * Extracts subexpressions of the selection chain.
810 * \param sel First selection in the whole selection chain.
811 * \returns The new first element for the chain.
813 * Finds all the subexpressions (and their subexpressions) in the
814 * selection chain starting from \p sel and creates \ref SEL_SUBEXPR
816 * \ref SEL_ROOT elements are also created for each subexpression
817 * and inserted into the selection chain before the expressions that
820 static SelectionTreeElementPointer
extract_subexpressions(SelectionTreeElementPointer sel
)
822 SelectionTreeElementPointer root
;
823 SelectionTreeElementPointer next
= sel
;
827 SelectionTreeElementPointer item
= extract_item_subselections(next
, &subexprn
);
855 /********************************************************************
856 * BOOLEAN OPERATION REORDERING
857 ********************************************************************/
860 * Removes redundant boolean selection elements.
862 * \param sel Root of the selection subtree to optimize.
864 * This function merges similar boolean operations (e.g., (A or B) or C becomes
865 * a single OR operation with three operands).
867 static void optimize_boolean_expressions(const SelectionTreeElementPointer
& sel
)
869 /* Do recursively for children */
870 if (sel
->type
!= SEL_SUBEXPRREF
)
872 SelectionTreeElementPointer prev
;
873 SelectionTreeElementPointer child
= sel
->child
;
876 optimize_boolean_expressions(child
);
877 /* Remove double negations */
878 if (child
->type
== SEL_BOOLEAN
&& child
->u
.boolt
== BOOL_NOT
879 && child
->child
->type
== SEL_BOOLEAN
&& child
->child
->u
.boolt
== BOOL_NOT
)
881 /* Move the doubly negated expression up two levels */
884 sel
->child
= child
->child
->child
;
889 prev
->next
= child
->child
->child
;
892 child
->child
->child
->next
= child
->next
;
893 // Discards the two negations.
900 if (sel
->type
!= SEL_BOOLEAN
|| sel
->u
.boolt
== BOOL_NOT
)
904 /* Merge subsequent binary operations */
905 SelectionTreeElementPointer prev
;
906 SelectionTreeElementPointer child
= sel
->child
;
909 if (child
->type
== SEL_BOOLEAN
&& child
->u
.boolt
== sel
->u
.boolt
)
913 sel
->child
= child
->child
;
918 prev
->next
= child
->child
;
924 prev
->next
= child
->next
;
925 // Discards the old child.
937 * Reorders children of boolean expressions such that static selections
940 * \param sel Root of the selection subtree to reorder.
942 * The relative order of static expressions does not change.
943 * The same is true for the dynamic expressions.
945 static void reorder_boolean_static_children(const SelectionTreeElementPointer
& sel
)
947 /* Do recursively for children */
948 if (sel
->type
!= SEL_SUBEXPRREF
)
950 SelectionTreeElementPointer child
= sel
->child
;
953 reorder_boolean_static_children(child
);
958 /* Reorder boolean expressions such that static selections come first */
959 if (sel
->type
== SEL_BOOLEAN
&& (sel
->flags
& SEL_DYNAMIC
))
961 // Add a dummy head element that precedes the first child.
962 SelectionTreeElementPointer
dummy(
963 new SelectionTreeElement(SEL_BOOLEAN
, SelectionLocation::createEmpty()));
964 dummy
->next
= sel
->child
;
965 SelectionTreeElementPointer prev
= dummy
;
966 SelectionTreeElementPointer child
= dummy
;
969 /* child is the last handled static expression */
970 /* prev is the last handled non-static expression */
971 SelectionTreeElementPointer next
= prev
->next
;
972 while (next
&& (next
->flags
& SEL_DYNAMIC
))
977 /* next is now the first static expression after child */
982 /* Reorder such that next comes after child */
985 prev
->next
= next
->next
;
986 next
->next
= child
->next
;
993 /* Advance child by one */
997 sel
->child
= dummy
->next
;
1002 /********************************************************************
1003 * ARITHMETIC EXPRESSION PROCESSING
1004 ********************************************************************/
1007 * Processes arithmetic expressions to simplify and speed up evaluation.
1009 * \param sel Root of the selection subtree to process.
1011 * Currently, this function only converts integer constants to reals
1012 * within arithmetic expressions.
1014 static void optimize_arithmetic_expressions(const SelectionTreeElementPointer
& sel
)
1016 /* Do recursively for children. */
1017 if (sel
->type
!= SEL_SUBEXPRREF
)
1019 SelectionTreeElementPointer child
= sel
->child
;
1022 optimize_arithmetic_expressions(child
);
1023 child
= child
->next
;
1027 if (sel
->type
!= SEL_ARITHMETIC
)
1032 /* Convert integer constants to reals. */
1033 SelectionTreeElementPointer child
= sel
->child
;
1036 if (child
->v
.type
== INT_VALUE
)
1040 if (child
->type
!= SEL_CONST
)
1043 gmx::InconsistentInputError("Non-constant integer expressions not "
1044 "implemented in arithmetic evaluation"));
1047 r
[0] = child
->v
.u
.i
[0];
1048 sfree(child
->v
.u
.i
);
1050 child
->v
.type
= REAL_VALUE
;
1052 else if (child
->v
.type
!= REAL_VALUE
)
1054 GMX_THROW(gmx::InternalError("Non-numerical value in arithmetic expression"));
1056 child
= child
->next
;
1061 /********************************************************************
1062 * EVALUATION PREPARATION COMPILER
1063 ********************************************************************/
1066 * Sets the evaluation functions for the selection (sub)tree.
1068 * \param[in,out] sel Root of the selection subtree to process.
1070 * This function sets the evaluation function
1071 * (gmx::SelectionTreeElement::evaluate) for the selection elements.
1073 static void init_item_evalfunc(const SelectionTreeElementPointer
& sel
)
1075 /* Process children. */
1076 if (sel
->type
!= SEL_SUBEXPRREF
)
1078 SelectionTreeElementPointer child
= sel
->child
;
1081 init_item_evalfunc(child
);
1082 child
= child
->next
;
1086 /* Set the evaluation function */
1090 if (sel
->v
.type
== GROUP_VALUE
)
1092 sel
->evaluate
= &_gmx_sel_evaluate_static
;
1096 case SEL_EXPRESSION
:
1097 if (!(sel
->flags
& SEL_DYNAMIC
) && sel
->u
.expr
.method
&& sel
->u
.expr
.method
->init_frame
)
1099 sel
->flags
|= SEL_INITFRAME
;
1101 sel
->evaluate
= &_gmx_sel_evaluate_method
;
1104 case SEL_ARITHMETIC
: sel
->evaluate
= &_gmx_sel_evaluate_arithmetic
; break;
1107 if (sel
->v
.type
!= NO_VALUE
)
1109 sel
->evaluate
= &_gmx_sel_evaluate_modifier
;
1114 switch (sel
->u
.boolt
)
1116 case BOOL_NOT
: sel
->evaluate
= &_gmx_sel_evaluate_not
; break;
1117 case BOOL_AND
: sel
->evaluate
= &_gmx_sel_evaluate_and
; break;
1118 case BOOL_OR
: sel
->evaluate
= &_gmx_sel_evaluate_or
; break;
1120 GMX_THROW(gmx::NotImplementedError("xor expressions not implemented"));
1124 case SEL_ROOT
: sel
->evaluate
= &_gmx_sel_evaluate_root
; break;
1127 if ((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
1128 && !(sel
->cdata
->flags
& SEL_CDATA_STATICMULTIEVALSUBEXPR
))
1130 sel
->evaluate
= &_gmx_sel_evaluate_subexpr_simple
;
1134 sel
->evaluate
= &_gmx_sel_evaluate_subexpr
;
1138 case SEL_SUBEXPRREF
:
1139 sel
->evaluate
= ((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
1140 ? &_gmx_sel_evaluate_subexprref_simple
1141 : &_gmx_sel_evaluate_subexprref
);
1144 case SEL_GROUPREF
: GMX_THROW(gmx::APIError("Unresolved group reference in compilation"));
1146 sel
->cdata
->evaluate
= sel
->evaluate
;
1150 * Sets the memory pool for selection elements that can use it.
1152 * \param sel Root of the selection subtree to process.
1153 * \param[in] mempool Memory pool to use.
1155 static void setup_memory_pooling(const SelectionTreeElementPointer
& sel
, gmx_sel_mempool_t
* mempool
)
1157 if (sel
->type
!= SEL_SUBEXPRREF
)
1159 SelectionTreeElementPointer child
= sel
->child
;
1162 if ((sel
->type
== SEL_BOOLEAN
&& (child
->flags
& SEL_DYNAMIC
))
1163 || (sel
->type
== SEL_ARITHMETIC
&& child
->type
!= SEL_CONST
&& !(child
->flags
& SEL_SINGLEVAL
))
1164 || (sel
->type
== SEL_SUBEXPR
&& !(sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)))
1166 child
->mempool
= mempool
;
1167 if (child
->type
== SEL_SUBEXPRREF
&& (child
->child
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
1169 child
->child
->child
->mempool
= mempool
;
1172 setup_memory_pooling(child
, mempool
);
1173 child
= child
->next
;
1179 * Prepares the selection (sub)tree for evaluation.
1181 * \param[in,out] sel Root of the selection subtree to prepare.
1183 * It also allocates memory for the \p sel->v.u.g or \p sel->v.u.p
1184 * structure if required.
1186 static void init_item_evaloutput(const SelectionTreeElementPointer
& sel
)
1188 GMX_ASSERT(!(sel
->child
== nullptr && (sel
->type
== SEL_SUBEXPRREF
|| sel
->type
== SEL_SUBEXPR
)),
1189 "Subexpression elements should always have a child element");
1191 /* Process children. */
1192 if (sel
->type
!= SEL_SUBEXPRREF
)
1194 SelectionTreeElementPointer child
= sel
->child
;
1197 init_item_evaloutput(child
);
1198 child
= child
->next
;
1202 if (sel
->type
== SEL_SUBEXPR
&& (sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
1203 && !(sel
->cdata
->flags
& SEL_CDATA_STATICMULTIEVALSUBEXPR
))
1205 sel
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
1206 if (sel
->v
.type
== GROUP_VALUE
|| sel
->v
.type
== POS_VALUE
)
1208 _gmx_selvalue_setstore(&sel
->v
, sel
->child
->v
.u
.ptr
);
1211 else if (sel
->type
== SEL_SUBEXPR
&& (sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
1213 sel
->evaluate
= &_gmx_sel_evaluate_subexpr_staticeval
;
1214 sel
->cdata
->evaluate
= sel
->evaluate
;
1215 sel
->child
->mempool
= nullptr;
1216 sel
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
1217 if (sel
->v
.type
== GROUP_VALUE
|| sel
->v
.type
== POS_VALUE
)
1219 _gmx_selvalue_setstore(&sel
->v
, sel
->child
->v
.u
.ptr
);
1222 else if (sel
->type
== SEL_SUBEXPRREF
&& (sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
1226 _gmx_selvalue_setstore(&sel
->child
->v
, sel
->v
.u
.ptr
);
1227 sel
->child
->child
->freeValues();
1228 sel
->child
->child
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
1229 sel
->child
->child
->flags
|= (sel
->flags
& SEL_ALLOCDATA
);
1230 _gmx_selvalue_setstore(&sel
->child
->child
->v
, sel
->v
.u
.ptr
);
1232 else if (sel
->v
.type
== GROUP_VALUE
|| sel
->v
.type
== POS_VALUE
)
1234 _gmx_selvalue_setstore(&sel
->v
, sel
->child
->child
->v
.u
.ptr
);
1236 sel
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
1239 /* Make sure that the group/position structure is allocated. */
1240 if (!sel
->v
.u
.ptr
&& (sel
->flags
& SEL_ALLOCVAL
))
1242 if (sel
->v
.type
== GROUP_VALUE
|| sel
->v
.type
== POS_VALUE
)
1244 _gmx_selvalue_reserve(&sel
->v
, 1);
1251 /********************************************************************
1252 * COMPILER DATA INITIALIZATION
1253 ********************************************************************/
1256 * Allocates memory for the compiler data and initializes the structure.
1258 * \param sel Root of the selection subtree to process.
1260 static void init_item_compilerdata(const SelectionTreeElementPointer
& sel
)
1262 /* Allocate the compiler data structure */
1263 snew(sel
->cdata
, 1);
1265 /* Store the real evaluation method because the compiler will replace it */
1266 sel
->cdata
->evaluate
= sel
->evaluate
;
1268 /* This will be computed separately. */
1269 sel
->cdata
->refcount
= 0;
1271 /* Initialize the flags */
1272 sel
->cdata
->flags
= SEL_CDATA_STATICEVAL
;
1273 if (!(sel
->flags
& SEL_DYNAMIC
))
1275 sel
->cdata
->flags
|= SEL_CDATA_STATIC
;
1277 if (sel
->type
== SEL_SUBEXPR
)
1279 sel
->cdata
->flags
|= SEL_CDATA_EVALMAX
;
1281 /* Set the full evaluation flag for subexpressions that require it;
1282 * the subexpression has already been initialized, so we can simply
1283 * access its compilation flags.*/
1284 if (sel
->type
== SEL_EXPRESSION
|| sel
->type
== SEL_MODIFIER
)
1286 SelectionTreeElementPointer child
= sel
->child
;
1289 if (!(child
->flags
& SEL_ATOMVAL
) && child
->child
)
1291 child
->child
->cdata
->flags
|= SEL_CDATA_FULLEVAL
;
1293 child
= child
->next
;
1296 else if (sel
->type
== SEL_ROOT
&& sel
->child
->type
== SEL_SUBEXPRREF
)
1298 sel
->child
->child
->cdata
->flags
|= SEL_CDATA_FULLEVAL
;
1301 /* Initialize children */
1302 if (sel
->type
!= SEL_SUBEXPRREF
)
1304 SelectionTreeElementPointer child
= sel
->child
;
1307 init_item_compilerdata(child
);
1308 child
= child
->next
;
1312 /* Determine whether we should evaluate the minimum or the maximum
1313 * for the children of this element. */
1314 if (sel
->type
== SEL_BOOLEAN
)
1318 bEvalMax
= (sel
->u
.boolt
== BOOL_AND
);
1319 SelectionTreeElementPointer child
= sel
->child
;
1324 child
->cdata
->flags
|= SEL_CDATA_EVALMAX
;
1326 else if (child
->type
== SEL_BOOLEAN
&& child
->u
.boolt
== BOOL_NOT
)
1328 child
->child
->cdata
->flags
|= SEL_CDATA_EVALMAX
;
1330 child
= child
->next
;
1333 else if (sel
->type
== SEL_EXPRESSION
|| sel
->type
== SEL_MODIFIER
|| sel
->type
== SEL_SUBEXPR
)
1335 SelectionTreeElementPointer child
= sel
->child
;
1338 child
->cdata
->flags
|= SEL_CDATA_EVALMAX
;
1339 child
= child
->next
;
1345 * Initializes the static evaluation flag for a selection subtree.
1347 * \param[in,out] sel Root of the selection subtree to process.
1349 * Sets the \c bStaticEval in the compiler data structure:
1350 * for any element for which the evaluation group may depend on the trajectory
1351 * frame, the flag is cleared.
1353 * reorder_boolean_static_children() should have been called.
1355 static void init_item_staticeval(const SelectionTreeElementPointer
& sel
)
1357 /* Subexpressions with full evaluation should always have bStaticEval,
1358 * so don't do anything if a reference to them is encountered. */
1359 if (sel
->type
== SEL_SUBEXPRREF
&& (sel
->child
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
1364 /* Propagate the bStaticEval flag to children if it is not set */
1365 if (!(sel
->cdata
->flags
& SEL_CDATA_STATICEVAL
))
1367 SelectionTreeElementPointer child
= sel
->child
;
1370 if ((sel
->type
!= SEL_EXPRESSION
&& sel
->type
!= SEL_MODIFIER
) || (child
->flags
& SEL_ATOMVAL
))
1372 if (child
->cdata
->flags
& SEL_CDATA_STATICEVAL
)
1374 child
->cdata
->flags
&= ~SEL_CDATA_STATICEVAL
;
1375 init_item_staticeval(child
);
1378 /* If an expression is evaluated for a dynamic group, then also
1379 * atom-valued parameters need to be evaluated every time. */
1380 if ((sel
->flags
& SEL_DYNAMIC
) && (sel
->type
== SEL_EXPRESSION
|| sel
->type
== SEL_MODIFIER
)
1381 && (child
->flags
& SEL_ATOMVAL
))
1383 child
->flags
|= SEL_DYNAMIC
;
1384 child
->cdata
->flags
&= ~SEL_CDATA_STATIC
;
1386 child
= child
->next
;
1389 else /* bStaticEval is set */
1391 /* For boolean expressions, any expression after the first dynamic
1392 * expression should not have bStaticEval. */
1393 if (sel
->type
== SEL_BOOLEAN
)
1395 SelectionTreeElementPointer child
= sel
->child
;
1396 while (child
&& !(child
->flags
& SEL_DYNAMIC
))
1398 child
= child
->next
;
1402 child
= child
->next
;
1406 child
->cdata
->flags
&= ~SEL_CDATA_STATICEVAL
;
1407 child
= child
->next
;
1411 /* Process the children */
1412 SelectionTreeElementPointer child
= sel
->child
;
1415 init_item_staticeval(child
);
1416 child
= child
->next
;
1422 * Compute reference counts for subexpressions.
1424 * \param sel Root of the selection subtree to process.
1426 static void init_item_subexpr_refcount(const SelectionTreeElementPointer
& sel
)
1428 // Reset the counter when the subexpression is first encountered.
1429 if (sel
->type
== SEL_ROOT
&& sel
->child
->type
== SEL_SUBEXPR
&& sel
->child
->cdata
)
1431 sel
->child
->cdata
->refcount
= 0;
1434 if (sel
->type
== SEL_SUBEXPRREF
)
1436 ++sel
->child
->cdata
->refcount
;
1440 SelectionTreeElementPointer child
= sel
->child
;
1443 init_item_subexpr_refcount(child
);
1444 child
= child
->next
;
1450 * Initializes compiler flags for subexpressions.
1452 * \param sel Root of the selection subtree to process.
1454 static void init_item_subexpr_flags(const SelectionTreeElementPointer
& sel
)
1456 if (sel
->type
== SEL_SUBEXPR
)
1458 if (sel
->cdata
->refcount
== 1)
1460 sel
->cdata
->flags
|= SEL_CDATA_SIMPLESUBEXPR
;
1462 else if (!(sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
1464 sel
->cdata
->flags
|= SEL_CDATA_COMMONSUBEXPR
;
1467 else if (sel
->type
== SEL_SUBEXPRREF
&& (sel
->child
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
1469 /* See similar condition in init_item_staticeval(). */
1470 if ((sel
->flags
& SEL_ATOMVAL
) && (sel
->flags
& SEL_DYNAMIC
) && !(sel
->child
->flags
& SEL_DYNAMIC
))
1472 sel
->child
->cdata
->flags
|= SEL_CDATA_STATICMULTIEVALSUBEXPR
;
1476 sel
->cdata
->flags
|= SEL_CDATA_SIMPLESUBEXPR
;
1480 /* Process children, but only follow subexpression references if the
1481 * common subexpression flag needs to be propagated. */
1482 if (sel
->type
!= SEL_SUBEXPRREF
1483 || ((sel
->cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
)
1484 && !(sel
->child
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)))
1486 SelectionTreeElementPointer child
= sel
->child
;
1489 if (!(child
->cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
))
1491 if (sel
->type
!= SEL_EXPRESSION
|| (child
->flags
& SEL_ATOMVAL
))
1493 child
->cdata
->flags
|= (sel
->cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
);
1495 init_item_subexpr_flags(child
);
1497 child
= child
->next
;
1503 * Initializes the gmin and gmax fields of the compiler data structure.
1505 * \param sel Root of the selection subtree to process.
1507 static void init_item_minmax_groups(const SelectionTreeElementPointer
& sel
)
1509 /* Process children. */
1510 if (sel
->type
!= SEL_SUBEXPRREF
)
1512 SelectionTreeElementPointer child
= sel
->child
;
1515 init_item_minmax_groups(child
);
1516 child
= child
->next
;
1520 /* Initialize the minimum and maximum evaluation groups. */
1521 if (sel
->type
!= SEL_ROOT
&& sel
->v
.type
!= NO_VALUE
)
1523 if (sel
->v
.type
== GROUP_VALUE
&& (sel
->cdata
->flags
& SEL_CDATA_STATIC
))
1525 sel
->cdata
->gmin
= sel
->v
.u
.g
;
1526 sel
->cdata
->gmax
= sel
->v
.u
.g
;
1528 else if (sel
->type
== SEL_SUBEXPR
1529 && ((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
1530 || (sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
)))
1532 GMX_ASSERT(sel
->child
, "Subexpression elements should always have a child element");
1533 sel
->cdata
->gmin
= sel
->child
->cdata
->gmin
;
1534 sel
->cdata
->gmax
= sel
->child
->cdata
->gmax
;
1538 sel
->cdata
->flags
|= SEL_CDATA_MINMAXALLOC
| SEL_CDATA_DOMINMAX
;
1539 snew(sel
->cdata
->gmin
, 1);
1540 snew(sel
->cdata
->gmax
, 1);
1546 /********************************************************************
1547 * EVALUATION GROUP INITIALIZATION
1548 ********************************************************************/
1551 * Initializes evaluation groups for root items.
1553 * \param[in,out] sc Selection collection data.
1555 * The evaluation group of each \ref SEL_ROOT element corresponding to a
1556 * selection in \p sc is set to NULL. The evaluation group for \ref SEL_ROOT
1557 * elements corresponding to subexpressions that need full evaluation is set
1560 static void initialize_evalgrps(gmx_ana_selcollection_t
* sc
)
1562 SelectionTreeElementPointer root
= sc
->root
;
1565 GMX_RELEASE_ASSERT(root
->child
, "Root elements should always have a child");
1566 if (root
->child
->type
!= SEL_SUBEXPR
1567 || (root
->child
->v
.type
!= GROUP_VALUE
&& !(root
->flags
& SEL_ATOMVAL
)))
1569 gmx_ana_index_set(&root
->u
.cgrp
, -1, nullptr, 0);
1571 else if (root
->child
->cdata
->flags
& SEL_CDATA_FULLEVAL
)
1573 gmx_ana_index_set(&root
->u
.cgrp
, sc
->gall
.isize
, sc
->gall
.index
, 0);
1580 /********************************************************************
1582 ********************************************************************/
1585 * Marks a subtree completely dynamic or undoes such a change.
1587 * \param sel Selection subtree to mark.
1588 * \param[in] bDynamic If true, the \p bStatic flag of the whole
1589 * selection subtree is cleared. If false, the flag is restored to
1590 * using \ref SEL_DYNAMIC.
1592 * Does not descend into parameters of methods unless the parameters
1593 * are evaluated for each atom.
1595 static void mark_subexpr_dynamic(const SelectionTreeElementPointer
& sel
, bool bDynamic
)
1597 if (!bDynamic
&& !(sel
->flags
& SEL_DYNAMIC
))
1599 sel
->cdata
->flags
|= SEL_CDATA_STATIC
;
1603 sel
->cdata
->flags
&= ~SEL_CDATA_STATIC
;
1605 SelectionTreeElementPointer child
= sel
->child
;
1608 if (sel
->type
!= SEL_EXPRESSION
|| child
->type
!= SEL_SUBEXPRREF
1609 || (child
->u
.param
->flags
& SPAR_ATOMVAL
))
1611 mark_subexpr_dynamic(child
, bDynamic
);
1613 child
= child
->next
;
1618 * Frees memory for subexpressions that are no longer needed.
1620 * \param sel Selection subtree to check.
1622 * Checks whether the subtree rooted at \p sel refers to any \ref SEL_SUBEXPR
1623 * elements that are not referred to by anything else except their own root
1624 * element. If such elements are found, all memory allocated for them is freed
1625 * except the actual element. The element is left because otherwise a dangling
1626 * pointer would be left at the root element, which is not traversed by this
1627 * function. Later compilation passes remove the stub elements.
1629 static void release_subexpr_memory(const SelectionTreeElementPointer
& sel
)
1631 if (sel
->type
== SEL_SUBEXPRREF
)
1633 const SelectionTreeElementPointer
& subexpr
= sel
->child
;
1634 if (subexpr
.use_count() == 2)
1636 release_subexpr_memory(subexpr
);
1638 subexpr
->child
.reset();
1639 subexpr
->freeValues();
1640 subexpr
->freeExpressionData();
1641 subexpr
->freeCompilerData();
1646 SelectionTreeElementPointer child
= sel
->child
;
1649 release_subexpr_memory(child
);
1650 child
= child
->next
;
1656 * Makes an evaluated selection element static.
1658 * \param sel Selection element to make static.
1660 * The evaluated value becomes the value of the static element.
1661 * The element type is changed to SEL_CONST and the children are
1664 static void make_static(const SelectionTreeElementPointer
& sel
)
1666 /* If this is a subexpression reference and the data is stored in the
1667 * child, we transfer data ownership before doing anything else. */
1668 if (sel
->type
== SEL_SUBEXPRREF
&& (sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
1670 if (sel
->child
->child
->flags
& SEL_ALLOCDATA
)
1672 sel
->flags
|= SEL_ALLOCDATA
;
1673 sel
->child
->child
->flags
&= ~SEL_ALLOCDATA
;
1675 if (sel
->child
->child
->flags
& SEL_ALLOCVAL
)
1677 sel
->flags
|= SEL_ALLOCVAL
;
1678 sel
->v
.nalloc
= sel
->child
->child
->v
.nalloc
;
1679 sel
->child
->child
->flags
&= ~SEL_ALLOCVAL
;
1680 sel
->child
->child
->v
.nalloc
= -1;
1683 /* Free the children. */
1684 release_subexpr_memory(sel
);
1686 /* Free the expression data as it is no longer needed */
1687 sel
->freeExpressionData();
1688 /* Make the item static */
1689 sel
->type
= SEL_CONST
;
1690 sel
->evaluate
= nullptr;
1691 sel
->cdata
->evaluate
= nullptr;
1692 /* Set the group value.
1693 * freeExpressionData() frees the cgrp group, so we can just override it.
1695 if (sel
->v
.type
== GROUP_VALUE
)
1697 gmx_ana_index_set(&sel
->u
.cgrp
, sel
->v
.u
.g
->isize
, sel
->v
.u
.g
->index
, 0);
1702 * Evaluates a constant expression during analyze_static().
1704 * \param[in] data Evaluation data.
1705 * \param[in,out] sel Selection to process.
1706 * \param[in] g The evaluation group.
1707 * \returns 0 on success, a non-zero error code on error.
1709 static void process_const(gmx_sel_evaluate_t
* data
, const SelectionTreeElementPointer
& sel
, gmx_ana_index_t
* g
)
1711 if (sel
->v
.type
== GROUP_VALUE
)
1713 if (sel
->cdata
->evaluate
)
1715 sel
->cdata
->evaluate(data
, sel
, g
);
1718 /* Other constant expressions do not need evaluation */
1722 * Sets the parameter value pointer for \ref SEL_SUBEXPRREF params.
1724 * \param[in,out] sel Selection to process.
1726 * Copies the value pointer of \p sel to \c sel->u.param if one is present
1727 * and should receive the value from the compiler
1728 * (most parameter values are handled during parsing).
1729 * If \p sel is not of type \ref SEL_SUBEXPRREF, or if \c sel->u.param is NULL,
1730 * the function does nothing.
1731 * Also, if the \c sel->u.param does not have \ref SPAR_VARNUM or
1732 * \ref SPAR_ATOMVAL, the function returns immediately.
1734 static void store_param_val(const SelectionTreeElementPointer
& sel
)
1736 /* Return immediately if there is no parameter. */
1737 if (sel
->type
!= SEL_SUBEXPRREF
|| !sel
->u
.param
)
1742 /* Or if the value does not need storing. */
1743 if (!(sel
->u
.param
->flags
& (SPAR_VARNUM
| SPAR_ATOMVAL
)))
1748 if (sel
->v
.type
== INT_VALUE
|| sel
->v
.type
== REAL_VALUE
|| sel
->v
.type
== STR_VALUE
)
1750 _gmx_selvalue_setstore(&sel
->u
.param
->val
, sel
->v
.u
.ptr
);
1755 * Handles the initialization of a selection method during analyze_static() pass.
1757 * \param[in,out] sel Selection element to process.
1758 * \param[in] top Topology structure.
1759 * \param[in] isize Size of the evaluation group for the element.
1760 * \returns 0 on success, a non-zero error code on return.
1762 * Calls sel_initfunc() (and possibly sel_outinitfunc()) to initialize the
1764 * If no \ref SPAR_ATOMVAL parameters are present, multiple initialization
1765 * is prevented by using \ref SEL_METHODINIT and \ref SEL_OUTINIT flags.
1767 static void init_method(const SelectionTreeElementPointer
& sel
, const gmx_mtop_t
* top
, int isize
)
1769 /* Find out whether there are any atom-valued parameters */
1770 bool bAtomVal
= false;
1771 SelectionTreeElementPointer child
= sel
->child
;
1774 if (child
->flags
& SEL_ATOMVAL
)
1778 child
= child
->next
;
1781 /* Initialize the method */
1782 if (sel
->u
.expr
.method
->init
&& (bAtomVal
|| !(sel
->flags
& SEL_METHODINIT
)))
1784 sel
->flags
|= SEL_METHODINIT
;
1785 sel
->u
.expr
.method
->init(top
, sel
->u
.expr
.method
->nparams
, sel
->u
.expr
.method
->param
,
1788 if (bAtomVal
|| !(sel
->flags
& SEL_OUTINIT
))
1790 sel
->flags
|= SEL_OUTINIT
;
1791 if (sel
->u
.expr
.method
->outinit
)
1793 sel
->u
.expr
.method
->outinit(top
, &sel
->v
, sel
->u
.expr
.mdata
);
1794 if (sel
->v
.type
!= POS_VALUE
&& sel
->v
.type
!= GROUP_VALUE
&& !(sel
->flags
& SEL_VARNUMVAL
))
1796 alloc_selection_data(sel
, isize
, true);
1801 GMX_RELEASE_ASSERT(sel
->v
.type
!= POS_VALUE
,
1802 "Output initialization must be provided for "
1803 "position-valued selection methods");
1804 GMX_RELEASE_ASSERT(!(sel
->flags
& SEL_VARNUMVAL
),
1805 "Output initialization must be provided for "
1806 "SMETH_VARNUMVAL selection methods");
1807 alloc_selection_data(sel
, isize
, true);
1808 /* If the method is char-valued, pre-allocate the strings. */
1809 if (sel
->u
.expr
.method
->flags
& SMETH_CHARVAL
)
1813 /* A sanity check */
1814 if (sel
->v
.type
!= STR_VALUE
)
1816 GMX_THROW(gmx::InternalError(
1817 "Char-valued selection method in non-string element"));
1819 sel
->flags
|= SEL_ALLOCDATA
;
1820 for (i
= 0; i
< isize
; ++i
)
1822 if (sel
->v
.u
.s
[i
] == nullptr)
1824 snew(sel
->v
.u
.s
[i
], 2);
1833 * Evaluates the static part of a boolean expression.
1835 * \param[in] data Evaluation data.
1836 * \param[in,out] sel Boolean selection element whose children should be
1838 * \param[in] g The evaluation group.
1839 * \returns 0 on success, a non-zero error code on error.
1841 * reorder_item_static_children() should have been called.
1843 static void evaluate_boolean_static_part(gmx_sel_evaluate_t
* data
,
1844 const SelectionTreeElementPointer
& sel
,
1847 /* Find the last static subexpression */
1848 SelectionTreeElementPointer child
= sel
->child
;
1849 while (child
->next
&& (child
->next
->cdata
->flags
& SEL_CDATA_STATIC
))
1851 child
= child
->next
;
1853 if (!(child
->cdata
->flags
& SEL_CDATA_STATIC
))
1858 /* Evalute the static part if there is more than one expression */
1859 if (child
!= sel
->child
)
1861 SelectionTreeElementPointer next
= child
->next
;
1862 child
->next
.reset();
1863 sel
->cdata
->evaluate(data
, sel
, g
);
1864 /* Replace the subexpressions with the result */
1865 child
= std::make_shared
<SelectionTreeElement
>(SEL_CONST
, SelectionLocation::createEmpty());
1866 child
->flags
= SEL_FLAGSSET
| SEL_SINGLEVAL
| SEL_ALLOCVAL
| SEL_ALLOCDATA
;
1867 _gmx_selelem_set_vtype(child
, GROUP_VALUE
);
1868 child
->evaluate
= nullptr;
1869 _gmx_selvalue_reserve(&child
->v
, 1);
1870 gmx_ana_index_copy(child
->v
.u
.g
, sel
->v
.u
.g
, true);
1871 init_item_compilerdata(child
);
1872 init_item_minmax_groups(child
);
1873 child
->cdata
->flags
&= ~SEL_CDATA_STATICEVAL
;
1874 child
->cdata
->flags
|= sel
->cdata
->flags
& SEL_CDATA_STATICEVAL
;
1876 // Frees the old static subexpressions.
1879 else if (child
->evaluate
)
1881 child
->evaluate(data
, child
, g
);
1883 /* Set the evaluation function for the constant element.
1884 * We never need to evaluate the element again during compilation,
1885 * but we may need to evaluate the static part again if the
1886 * expression is not an OR with a static evaluation group.
1887 * If we reach here with a NOT expression, the NOT expression
1888 * is also static, and will be made a constant later, so don't waste
1889 * time copying the group. */
1890 child
->evaluate
= nullptr;
1891 if (sel
->u
.boolt
== BOOL_NOT
|| ((sel
->cdata
->flags
& SEL_CDATA_STATICEVAL
) && sel
->u
.boolt
== BOOL_OR
))
1893 child
->cdata
->evaluate
= nullptr;
1897 child
->cdata
->evaluate
= &_gmx_sel_evaluate_static
;
1898 /* The cgrp has only been allocated if it originated from an
1899 * external index group.
1900 * If cgrp has been set in make_static(), it is not allocated,
1901 * and hence we can overwrite it safely. */
1902 if (child
->u
.cgrp
.nalloc_index
> 0)
1904 gmx_ana_index_copy(&child
->u
.cgrp
, child
->v
.u
.g
, false);
1905 gmx_ana_index_squeeze(&child
->u
.cgrp
);
1909 gmx_ana_index_copy(&child
->u
.cgrp
, child
->v
.u
.g
, true);
1915 * Evaluates the minimum and maximum groups for a boolean expression.
1917 * \param[in] sel \ref SEL_BOOLEAN element currently being evaluated.
1918 * \param[in] g Group for which \p sel has been evaluated.
1919 * \param[out] gmin Largest subset of the possible values of \p sel.
1920 * \param[out] gmax Smallest superset of the possible values of \p sel.
1922 * This is a helper function for analyze_static() that is called for
1923 * dynamic \ref SEL_BOOLEAN elements after they have been evaluated.
1924 * It uses the minimum and maximum groups of the children to calculate
1925 * the minimum and maximum groups for \p sel, and also updates the static
1926 * part of \p sel (which is in the first child) if the children give
1929 * This function may allocate some extra memory for \p gmin and \p gmax,
1930 * but as these groups are freed at the end of analyze_static() (which is
1931 * reached shortly after this function returns), this should not be a major
1934 static void evaluate_boolean_minmax_grps(const SelectionTreeElementPointer
& sel
,
1936 gmx_ana_index_t
* gmin
,
1937 gmx_ana_index_t
* gmax
)
1939 SelectionTreeElementPointer child
;
1941 switch (sel
->u
.boolt
)
1944 GMX_ASSERT(g
!= nullptr, "Need a valid group");
1945 gmx_ana_index_reserve(gmin
, g
->isize
);
1946 gmx_ana_index_reserve(gmax
, g
->isize
);
1947 gmx_ana_index_difference(gmax
, g
, sel
->child
->cdata
->gmin
);
1948 gmx_ana_index_difference(gmin
, g
, sel
->child
->cdata
->gmax
);
1952 gmx_ana_index_copy(gmin
, sel
->child
->cdata
->gmin
, true);
1953 gmx_ana_index_copy(gmax
, sel
->child
->cdata
->gmax
, true);
1954 child
= sel
->child
->next
;
1955 while (child
&& gmax
->isize
> 0)
1957 gmx_ana_index_intersection(gmin
, gmin
, child
->cdata
->gmin
);
1958 gmx_ana_index_intersection(gmax
, gmax
, child
->cdata
->gmax
);
1959 child
= child
->next
;
1961 /* Update the static part if other expressions limit it */
1962 if ((sel
->child
->cdata
->flags
& SEL_CDATA_STATIC
) && sel
->child
->v
.u
.g
->isize
> gmax
->isize
)
1964 gmx_ana_index_copy(sel
->child
->v
.u
.g
, gmax
, false);
1965 gmx_ana_index_squeeze(sel
->child
->v
.u
.g
);
1966 if (sel
->child
->u
.cgrp
.isize
> 0)
1968 gmx_ana_index_copy(&sel
->child
->u
.cgrp
, gmax
, false);
1969 gmx_ana_index_squeeze(&sel
->child
->u
.cgrp
);
1975 /* We can assume here that the gmin of children do not overlap
1976 * because of the way _gmx_sel_evaluate_or() works. */
1977 GMX_ASSERT(g
!= nullptr, "Need a valid group");
1978 gmx_ana_index_reserve(gmin
, g
->isize
);
1979 gmx_ana_index_reserve(gmax
, g
->isize
);
1980 gmx_ana_index_copy(gmin
, sel
->child
->cdata
->gmin
, false);
1981 gmx_ana_index_copy(gmax
, sel
->child
->cdata
->gmax
, false);
1982 child
= sel
->child
->next
;
1983 while (child
&& gmin
->isize
< g
->isize
)
1985 gmx_ana_index_merge(gmin
, gmin
, child
->cdata
->gmin
);
1986 gmx_ana_index_union(gmax
, gmax
, child
->cdata
->gmax
);
1987 child
= child
->next
;
1989 /* Update the static part if other expressions have static parts
1990 * that are not included. */
1991 if ((sel
->child
->cdata
->flags
& SEL_CDATA_STATIC
) && sel
->child
->v
.u
.g
->isize
< gmin
->isize
)
1993 GMX_RELEASE_ASSERT(sel
->child
->type
== SEL_CONST
,
1994 "The first child should have already been evaluated "
1995 "to a constant expression");
1996 gmx_ana_index_reserve(sel
->child
->v
.u
.g
, gmin
->isize
);
1997 gmx_ana_index_copy(sel
->child
->v
.u
.g
, gmin
, false);
1998 if (sel
->child
->u
.cgrp
.nalloc_index
> 0)
2000 gmx_ana_index_reserve(&sel
->child
->u
.cgrp
, gmin
->isize
);
2001 gmx_ana_index_copy(&sel
->child
->u
.cgrp
, gmin
, false);
2005 GMX_RELEASE_ASSERT(sel
->child
->u
.cgrp
.index
== sel
->child
->v
.u
.g
->index
,
2006 "If not allocated, the static group should equal the value");
2007 sel
->child
->u
.cgrp
.isize
= sel
->child
->v
.u
.g
->isize
;
2012 case BOOL_XOR
: /* Should not be reached */
2013 GMX_THROW(gmx::NotImplementedError("xor expressions not implemented"));
2018 * Evaluates the static parts of \p sel and analyzes the structure.
2020 * \param[in] data Evaluation data.
2021 * \param[in,out] sel Selection currently being evaluated.
2022 * \param[in] g Group for which \p sel should be evaluated.
2023 * \returns 0 on success, a non-zero error code on error.
2025 * This function is used as the replacement for the
2026 * gmx::SelectionTreeElement::evaluate function pointer.
2027 * It does the single most complex task in the compiler: after all elements
2028 * have been processed, the \p gmin and \p gmax fields of \p t_compiler_data
2029 * have been properly initialized, enough memory has been allocated for
2030 * storing the value of each expression, and the static parts of the
2031 * expressions have been evaluated.
2032 * The above is exactly true only for elements other than subexpressions:
2033 * another pass is required for subexpressions that are referred to more than
2034 * once and whose evaluation group is not known in advance.
2036 static void analyze_static(gmx_sel_evaluate_t
* data
, const SelectionTreeElementPointer
& sel
, gmx_ana_index_t
* g
)
2040 if (sel
->type
!= SEL_ROOT
&& g
)
2042 alloc_selection_data(sel
, g
->isize
, false);
2045 bDoMinMax
= ((sel
->cdata
->flags
& SEL_CDATA_DOMINMAX
) != 0);
2046 if (sel
->type
!= SEL_SUBEXPR
&& bDoMinMax
)
2048 gmx_ana_index_deinit(sel
->cdata
->gmin
);
2049 gmx_ana_index_deinit(sel
->cdata
->gmax
);
2052 /* TODO: This switch is awfully long... */
2055 case SEL_CONST
: process_const(data
, sel
, g
); break;
2057 case SEL_EXPRESSION
:
2060 const int isize
= g
? g
->isize
: 0;
2061 _gmx_sel_evaluate_method_params(data
, sel
, g
);
2062 init_method(sel
, data
->top
, isize
);
2063 if (!(sel
->flags
& SEL_DYNAMIC
))
2065 sel
->cdata
->evaluate(data
, sel
, g
);
2066 if (sel
->cdata
->flags
& SEL_CDATA_STATIC
)
2073 /* Modifiers need to be evaluated even though they process
2074 * positions to get the modified output groups from the
2075 * maximum possible selections. */
2076 if (sel
->type
== SEL_MODIFIER
)
2078 sel
->cdata
->evaluate(data
, sel
, g
);
2082 if (sel
->v
.type
!= GROUP_VALUE
&& sel
->v
.type
!= POS_VALUE
)
2084 sel
->v
.nr
= ((sel
->flags
& SEL_SINGLEVAL
) ? 1 : isize
);
2086 // Clear the values for dynamic output to avoid
2087 // uninitialized memory.
2088 if (sel
->v
.type
== REAL_VALUE
)
2090 for (int i
= 0; i
< sel
->v
.nr
; ++i
)
2092 sel
->v
.u
.r
[i
] = 0.0;
2098 gmx_ana_index_copy(sel
->cdata
->gmax
, g
, true);
2104 if (!(sel
->flags
& SEL_DYNAMIC
))
2106 sel
->cdata
->evaluate(data
, sel
, g
);
2107 if (sel
->cdata
->flags
& SEL_CDATA_STATIC
)
2114 /* Evalute the static part if there is more than one expression */
2115 evaluate_boolean_static_part(data
, sel
, g
);
2117 /* Evaluate the selection.
2118 * If the type is boolean, we must explicitly handle the
2119 * static part evaluated in evaluate_boolean_static_part()
2120 * here because g may be larger. */
2121 if (sel
->u
.boolt
== BOOL_AND
&& sel
->child
->type
== SEL_CONST
)
2123 sel
->cdata
->evaluate(data
, sel
, sel
->child
->v
.u
.g
);
2127 sel
->cdata
->evaluate(data
, sel
, g
);
2130 /* Evaluate minimal and maximal selections */
2131 evaluate_boolean_minmax_grps(sel
, g
, sel
->cdata
->gmin
, sel
->cdata
->gmax
);
2135 case SEL_ARITHMETIC
:
2136 sel
->cdata
->evaluate(data
, sel
, g
);
2137 if (!(sel
->flags
& SEL_DYNAMIC
))
2139 if (sel
->cdata
->flags
& SEL_CDATA_STATIC
)
2146 gmx_ana_index_copy(sel
->cdata
->gmax
, g
, true);
2150 case SEL_ROOT
: sel
->cdata
->evaluate(data
, sel
, g
); break;
2153 if (((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
2154 && !(sel
->cdata
->flags
& SEL_CDATA_STATICMULTIEVALSUBEXPR
))
2155 || (sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
2157 sel
->cdata
->evaluate(data
, sel
, g
);
2158 _gmx_selvalue_setstore(&sel
->v
, sel
->child
->v
.u
.ptr
);
2160 else if (sel
->u
.cgrp
.isize
== 0)
2162 GMX_ASSERT(g
, "group cannot be null");
2163 gmx_ana_index_reserve(&sel
->u
.cgrp
, g
->isize
);
2164 sel
->cdata
->evaluate(data
, sel
, g
);
2167 gmx_ana_index_copy(sel
->cdata
->gmin
, sel
->child
->cdata
->gmin
, true);
2168 gmx_ana_index_copy(sel
->cdata
->gmax
, sel
->child
->cdata
->gmax
, true);
2173 int isize
= gmx_ana_index_difference_size(g
, &sel
->u
.cgrp
);
2176 isize
+= sel
->u
.cgrp
.isize
;
2177 gmx_ana_index_reserve(&sel
->u
.cgrp
, isize
);
2178 alloc_selection_data(sel
, isize
, false);
2180 sel
->cdata
->evaluate(data
, sel
, g
);
2181 if (isize
> 0 && bDoMinMax
)
2183 gmx_ana_index_reserve(sel
->cdata
->gmin
,
2184 sel
->cdata
->gmin
->isize
+ sel
->child
->cdata
->gmin
->isize
);
2185 gmx_ana_index_reserve(sel
->cdata
->gmax
,
2186 sel
->cdata
->gmax
->isize
+ sel
->child
->cdata
->gmax
->isize
);
2187 gmx_ana_index_merge(sel
->cdata
->gmin
, sel
->cdata
->gmin
, sel
->child
->cdata
->gmin
);
2188 gmx_ana_index_merge(sel
->cdata
->gmax
, sel
->cdata
->gmax
, sel
->child
->cdata
->gmax
);
2193 case SEL_SUBEXPRREF
:
2194 if (!g
&& !(sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
2196 /* The subexpression should have been evaluated if g is NULL
2197 * (i.e., this is a method parameter or a direct value of a
2199 if (sel
->v
.type
== POS_VALUE
)
2201 alloc_selection_pos_data(sel
);
2202 gmx_ana_pos_copy(sel
->v
.u
.p
, sel
->child
->v
.u
.p
, true);
2206 alloc_selection_data(sel
, sel
->child
->cdata
->gmax
->isize
, true);
2209 sel
->cdata
->evaluate(data
, sel
, g
);
2210 if ((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
) && (sel
->child
->child
->flags
& SEL_ALLOCVAL
))
2212 _gmx_selvalue_setstore(&sel
->v
, sel
->child
->child
->v
.u
.ptr
);
2214 /* Store the parameter value if required */
2215 store_param_val(sel
);
2216 if (!(sel
->flags
& SEL_DYNAMIC
))
2218 if (sel
->cdata
->flags
& SEL_CDATA_STATIC
)
2225 if ((sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
) || !g
)
2227 gmx_ana_index_copy(sel
->cdata
->gmin
, sel
->child
->cdata
->gmin
, true);
2228 gmx_ana_index_copy(sel
->cdata
->gmax
, sel
->child
->cdata
->gmax
, true);
2232 gmx_ana_index_reserve(sel
->cdata
->gmin
, min(g
->isize
, sel
->child
->cdata
->gmin
->isize
));
2233 gmx_ana_index_reserve(sel
->cdata
->gmax
, min(g
->isize
, sel
->child
->cdata
->gmax
->isize
));
2234 gmx_ana_index_intersection(sel
->cdata
->gmin
, sel
->child
->cdata
->gmin
, g
);
2235 gmx_ana_index_intersection(sel
->cdata
->gmax
, sel
->child
->cdata
->gmax
, g
);
2240 case SEL_GROUPREF
: /* Should not be reached */
2241 GMX_THROW(gmx::APIError("Unresolved group reference in compilation"));
2244 /* Update the minimal and maximal evaluation groups */
2247 gmx_ana_index_squeeze(sel
->cdata
->gmin
);
2248 gmx_ana_index_squeeze(sel
->cdata
->gmax
);
2251 /* Replace the result of the evaluation */
2252 /* This is not necessary for subexpressions or for boolean negations
2253 * because the evaluation function already has done it properly. */
2254 if (sel
->v
.type
== GROUP_VALUE
&& (sel
->flags
& SEL_DYNAMIC
) && sel
->type
!= SEL_SUBEXPR
2255 && !(sel
->type
== SEL_BOOLEAN
&& sel
->u
.boolt
== BOOL_NOT
))
2257 if (sel
->cdata
->flags
& SEL_CDATA_EVALMAX
)
2259 gmx_ana_index_copy(sel
->v
.u
.g
, sel
->cdata
->gmax
, false);
2263 gmx_ana_index_copy(sel
->v
.u
.g
, sel
->cdata
->gmin
, false);
2269 /********************************************************************
2270 * EVALUATION GROUP INITIALIZATION
2271 ********************************************************************/
2274 * Initializes the evaluation group for a \ref SEL_ROOT element.
2276 * \param root Root element to initialize.
2277 * \param[in] gall Group of all atoms.
2279 * Checks whether it is necessary to evaluate anything through the root
2280 * element, and either clears the evaluation function or initializes the
2283 static void init_root_item(const SelectionTreeElementPointer
& root
, gmx_ana_index_t
* gall
)
2285 const SelectionTreeElementPointer
& expr
= root
->child
;
2286 /* Subexpressions with non-static evaluation group should not be
2287 * evaluated by the root, and neither should be single-reference
2288 * subexpressions that don't evaluate for all atoms. */
2289 if (expr
->type
== SEL_SUBEXPR
2290 && (!(root
->child
->cdata
->flags
& SEL_CDATA_STATICEVAL
)
2291 || ((root
->child
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
2292 && !(root
->child
->cdata
->flags
& SEL_CDATA_FULLEVAL
))))
2294 root
->evaluate
= nullptr;
2297 root
->cdata
->evaluate
= nullptr;
2301 /* Set the evaluation group */
2304 /* Non-atom-valued non-group expressions don't care about the group, so
2305 * don't allocate any memory for it. */
2306 if ((expr
->flags
& SEL_VARNUMVAL
) || ((expr
->flags
& SEL_SINGLEVAL
) && expr
->v
.type
!= GROUP_VALUE
))
2308 gmx_ana_index_set(&root
->u
.cgrp
, -1, nullptr, 0);
2310 else if (expr
->cdata
->gmax
->isize
== gall
->isize
)
2312 /* Save some memory by only referring to the global group. */
2313 gmx_ana_index_set(&root
->u
.cgrp
, gall
->isize
, gall
->index
, 0);
2317 gmx_ana_index_copy(&root
->u
.cgrp
, expr
->cdata
->gmax
, true);
2319 /* For selections, store the maximum group for
2320 * gmx_ana_selcollection_evaluate_fin() as the value of the root
2321 * element (unused otherwise). */
2322 if (expr
->type
!= SEL_SUBEXPR
&& expr
->v
.u
.p
->m
.mapb
.a
!= nullptr)
2324 SelectionTreeElementPointer child
= expr
;
2326 /* TODO: This code is copied from parsetree.c; it would be better
2327 * to have this hardcoded only in one place. */
2328 while (child
->type
== SEL_MODIFIER
)
2330 child
= child
->child
;
2331 if (child
->type
== SEL_SUBEXPRREF
)
2333 child
= child
->child
->child
;
2336 if (child
->type
== SEL_SUBEXPRREF
)
2338 child
= child
->child
->child
;
2340 if (child
->child
->flags
& SEL_DYNAMIC
)
2343 gmx_ana_index_set(&g
, expr
->v
.u
.p
->m
.mapb
.nra
, expr
->v
.u
.p
->m
.mapb
.a
, 0);
2344 _gmx_selelem_set_vtype(root
, GROUP_VALUE
);
2345 root
->flags
|= (SEL_ALLOCVAL
| SEL_ALLOCDATA
);
2346 _gmx_selvalue_reserve(&root
->v
, 1);
2347 gmx_ana_index_copy(root
->v
.u
.g
, &g
, true);
2353 gmx_ana_index_clear(&root
->u
.cgrp
);
2358 /********************************************************************
2359 * REQUIRED ATOMS ANALYSIS
2360 ********************************************************************/
2363 * Finds the highest atom index required to evaluate a selection subtree.
2365 * \param[in] sel Root of the selection subtree to process.
2366 * \param[in,out] requiredAtoms The atoms required to evaluate the subtree.
2367 * The existing group is only added to, so multiple calls with
2368 * the same parameter will compute the union over several subtrees.
2370 * For evaluation that starts from a \ref SEL_ROOT element with a fixed group,
2371 * children will never extend the evaluation group except for method parameter
2372 * evaluation (which have their own root element), so it is sufficient to check
2373 * the root. However, children of \ref SEL_EXPRESSION elements (i.e., the
2374 * method parameters) may have been independently evaluated to a static group
2375 * that no longer has a separate root, so those need to be checked as well.
2377 * Position calculations are not considered here, but are analyzed through the
2378 * position calculation collection in the main compilation method.
2380 static void init_required_atoms(const SelectionTreeElementPointer
& sel
, gmx_ana_index_t
* requiredAtoms
)
2382 // Process children.
2383 if (sel
->type
!= SEL_SUBEXPRREF
)
2385 SelectionTreeElementPointer child
= sel
->child
;
2388 init_required_atoms(child
, requiredAtoms
);
2389 child
= child
->next
;
2393 if (sel
->type
== SEL_ROOT
|| (sel
->type
== SEL_CONST
&& sel
->v
.type
== GROUP_VALUE
))
2395 if (sel
->u
.cgrp
.isize
> 0)
2397 gmx_ana_index_union_unsorted(requiredAtoms
, requiredAtoms
, &sel
->u
.cgrp
);
2403 /********************************************************************
2404 * FINAL SUBEXPRESSION OPTIMIZATION
2405 ********************************************************************/
2408 * Optimizes subexpression evaluation.
2410 * \param sel Root of the selection subtree to process.
2412 * Optimizes away some unnecessary evaluation of subexpressions that are only
2415 static void postprocess_item_subexpressions(const SelectionTreeElementPointer
& sel
)
2417 GMX_ASSERT(!(sel
->child
== nullptr && (sel
->type
== SEL_SUBEXPRREF
|| sel
->type
== SEL_SUBEXPR
)),
2418 "Subexpression elements should always have a child element");
2420 /* Process children. */
2421 if (sel
->type
!= SEL_SUBEXPRREF
)
2423 SelectionTreeElementPointer child
= sel
->child
;
2426 postprocess_item_subexpressions(child
);
2427 child
= child
->next
;
2431 /* Replace the evaluation function of statically evaluated subexpressions
2432 * for which the static group was not known in advance. */
2433 if (sel
->type
== SEL_SUBEXPR
&& sel
->cdata
->refcount
> 1
2434 && (sel
->cdata
->flags
& SEL_CDATA_STATICEVAL
) && !(sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
2436 /* We need to free memory allocated for the group, because it is no
2437 * longer needed (and would be lost on next call to the evaluation
2439 gmx_ana_index_deinit(&sel
->u
.cgrp
);
2441 sel
->evaluate
= &_gmx_sel_evaluate_subexpr_staticeval
;
2442 sel
->cdata
->evaluate
= sel
->evaluate
;
2444 sel
->child
->freeValues();
2445 sel
->child
->mempool
= nullptr;
2446 _gmx_selvalue_setstore(&sel
->child
->v
, sel
->v
.u
.ptr
);
2447 sel
->child
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
2450 /* Adjust memory allocation flags for subexpressions that are used only
2451 * once. This is not strictly necessary, but we do it to have the memory
2452 * managed consistently for all types of subexpressions. */
2453 if (sel
->type
== SEL_SUBEXPRREF
&& (sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
))
2455 if (sel
->child
->child
->flags
& SEL_ALLOCVAL
)
2457 sel
->flags
|= SEL_ALLOCVAL
;
2458 sel
->flags
|= (sel
->child
->child
->flags
& SEL_ALLOCDATA
);
2459 sel
->v
.nalloc
= sel
->child
->child
->v
.nalloc
;
2460 sel
->child
->child
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
2461 sel
->child
->child
->v
.nalloc
= -1;
2465 /* Do the same for subexpressions that are evaluated at once for all atoms. */
2466 if (sel
->type
== SEL_SUBEXPR
&& !(sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
2467 && (sel
->cdata
->flags
& SEL_CDATA_FULLEVAL
))
2469 sel
->flags
|= SEL_ALLOCVAL
;
2470 sel
->flags
|= (sel
->child
->flags
& SEL_ALLOCDATA
);
2471 sel
->v
.nalloc
= sel
->child
->v
.nalloc
;
2472 sel
->child
->flags
&= ~(SEL_ALLOCVAL
| SEL_ALLOCDATA
);
2473 sel
->child
->v
.nalloc
= -1;
2476 /* For static subexpressions with a dynamic evaluation group, there is
2477 * no need to evaluate them again, as the SEL_SUBEXPRREF takes care of
2478 * everything during evaluation. */
2479 if (sel
->type
== SEL_SUBEXPR
&& (sel
->cdata
->flags
& SEL_CDATA_SIMPLESUBEXPR
)
2480 && (sel
->cdata
->flags
& SEL_CDATA_STATICMULTIEVALSUBEXPR
))
2482 sel
->evaluate
= nullptr;
2483 sel
->cdata
->evaluate
= nullptr;
2488 /********************************************************************
2489 * COM CALCULATION INITIALIZATION
2490 ********************************************************************/
2493 * Initializes COM/COG calculation for method expressions that require it.
2495 * \param sel Selection subtree to process.
2496 * \param[in,out] pcc Position calculation collection to use.
2497 * \param[in] type Default position calculation type.
2498 * \param[in] flags Flags for default position calculation.
2500 * Searches recursively through the selection tree for dynamic
2501 * \ref SEL_EXPRESSION elements that define the \c gmx_ana_selmethod_t::pupdate
2503 * For each such element found, position calculation is initialized
2504 * for the maximal evaluation group.
2505 * The type of the calculation is determined by \p type and \p flags.
2506 * No calculation is initialized if \p type equals \ref POS_ATOM and
2507 * the method also defines the \c gmx_ana_selmethod_t::update method.
2509 static void init_item_comg(const SelectionTreeElementPointer
& sel
,
2510 gmx::PositionCalculationCollection
* pcc
,
2514 /* Initialize COM calculation for dynamic selections now that we know the maximal evaluation group */
2515 if (sel
->type
== SEL_EXPRESSION
&& sel
->u
.expr
.method
&& sel
->u
.expr
.method
->pupdate
)
2517 if (!sel
->u
.expr
.method
->update
|| type
!= POS_ATOM
)
2519 /* Create a default calculation if one does not yet exist */
2521 if (!(sel
->cdata
->flags
& SEL_CDATA_STATICEVAL
))
2523 cflags
|= POS_DYNAMIC
;
2525 if (!sel
->u
.expr
.pc
)
2528 sel
->u
.expr
.pc
= pcc
->createCalculation(type
, cflags
);
2532 gmx_ana_poscalc_set_flags(sel
->u
.expr
.pc
, cflags
);
2534 gmx_ana_poscalc_set_maxindex(sel
->u
.expr
.pc
, sel
->cdata
->gmax
);
2535 sel
->u
.expr
.pos
= new gmx_ana_pos_t();
2536 gmx_ana_poscalc_init_pos(sel
->u
.expr
.pc
, sel
->u
.expr
.pos
);
2540 /* Call recursively for all children unless the children have already been processed */
2541 if (sel
->type
!= SEL_SUBEXPRREF
)
2543 SelectionTreeElementPointer child
= sel
->child
;
2546 init_item_comg(child
, pcc
, type
, flags
);
2547 child
= child
->next
;
2553 /********************************************************************
2554 * COMPILER DATA FREEING
2555 ********************************************************************/
2558 * Frees the allocated compiler data recursively.
2560 * \param sel Root of the selection subtree to process.
2562 * Frees the data allocated for the compilation process.
2564 static void free_item_compilerdata(const SelectionTreeElementPointer
& sel
)
2566 /* Free compilation data */
2567 sel
->freeCompilerData();
2569 /* Call recursively for all children unless the children have already been processed */
2570 if (sel
->type
!= SEL_SUBEXPRREF
)
2572 SelectionTreeElementPointer child
= sel
->child
;
2575 free_item_compilerdata(child
);
2576 child
= child
->next
;
2582 /********************************************************************
2583 * MAIN COMPILATION FUNCTION
2584 ********************************************************************/
2589 SelectionCompiler::SelectionCompiler() {}
2592 * \param[in,out] coll Selection collection to be compiled.
2593 * \returns 0 on successful compilation, a non-zero error code on error.
2595 * Before compilation, the selection collection should have been initialized
2596 * with gmx_ana_selcollection_parse_*().
2597 * The compiled selection collection can be passed to
2598 * gmx_ana_selcollection_evaluate() to evaluate the selection for a frame.
2599 * If an error occurs, \p sc is cleared.
2601 * The covered fraction information in \p sc is initialized to
2604 void SelectionCompiler::compile(SelectionCollection
* coll
)
2606 gmx_ana_selcollection_t
* sc
= &coll
->impl_
->sc_
;
2607 gmx_sel_evaluate_t evaldata
;
2608 SelectionTreeElementPointer item
;
2612 bool bDebug
= (coll
->impl_
->debugLevel_
>= 2 && coll
->impl_
->debugLevel_
!= 3);
2614 /* FIXME: Clean up the collection on exceptions */
2616 sc
->mempool
= _gmx_sel_mempool_create();
2617 _gmx_sel_evaluate_init(&evaldata
, sc
->mempool
, &sc
->gall
, sc
->top
, nullptr, nullptr);
2619 /* Clear the symbol table because it is not possible to parse anything
2620 * after compilation, and variable references in the symbol table can
2621 * also mess up the compilation and/or become invalid.
2623 coll
->impl_
->clearSymbolTable();
2625 /* Loop through selections and initialize position keyword defaults if no
2626 * other value has been provided.
2628 for (i
= 0; i
< sc
->sel
.size(); ++i
)
2630 gmx::internal::SelectionData
& sel
= *sc
->sel
[i
];
2631 init_pos_keyword_defaults(&sel
.rootElement(), coll
->impl_
->spost_
.c_str(),
2632 coll
->impl_
->rpost_
.c_str(), &sel
);
2635 /* Remove any unused variables. */
2636 sc
->root
= remove_unused_subexpressions(sc
->root
);
2637 /* Extract subexpressions into separate roots */
2638 sc
->root
= extract_subexpressions(sc
->root
);
2640 /* Initialize the evaluation callbacks and process the tree structure
2641 * to conform to the expectations of the callback functions. */
2642 /* Also, initialize and allocate the compiler data structure */
2643 // TODO: Processing the tree in reverse root order would be better,
2644 // as it would make dependency handling easier (all subexpression
2645 // references would be processed before the actual subexpression) and
2646 // could remove the need for most of these extra loops.
2650 /* Process boolean and arithmetic expressions. */
2651 optimize_boolean_expressions(item
);
2652 reorder_boolean_static_children(item
);
2653 optimize_arithmetic_expressions(item
);
2654 /* Initialize the compiler data */
2655 init_item_compilerdata(item
);
2658 // Initialize the static evaluation compiler flags.
2659 // Requires the FULLEVAL compiler flag for the whole tree.
2663 init_item_staticeval(item
);
2664 init_item_subexpr_refcount(item
);
2667 /* Initialize subexpression flags.
2668 * Requires compiler flags for the full tree. */
2672 init_item_subexpr_flags(item
);
2675 /* Initialize evaluation.
2676 * Requires subexpression flags. */
2680 init_item_evalfunc(item
);
2681 setup_memory_pooling(item
, sc
->mempool
);
2682 init_item_evaloutput(item
);
2685 /* Initialize minimum/maximum index groups.
2686 * Requires evaluation output for the full tree. */
2690 init_item_minmax_groups(item
);
2693 /* Initialize the evaluation index groups */
2694 initialize_evalgrps(sc
);
2698 fprintf(stderr
, "\nTree after initial compiler processing:\n");
2699 coll
->printTree(stderr
, false);
2702 /* Evaluate all static parts of the selection and analyze the tree
2703 * to allocate enough memory to store the value of each dynamic subtree. */
2707 if (item
->child
->cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
)
2709 mark_subexpr_dynamic(item
->child
, true);
2711 set_evaluation_function(item
, &analyze_static
);
2712 item
->evaluate(&evaldata
, item
, nullptr);
2716 /* At this point, static subexpressions no longer have references to them,
2717 * so they can be removed. */
2718 sc
->root
= remove_unused_subexpressions(sc
->root
);
2719 // Update the reference counts for consistency (only used for the
2720 // debugging output below).
2724 init_item_subexpr_refcount(item
);
2730 fprintf(stderr
, "\nTree after first analysis pass:\n");
2731 coll
->printTree(stderr
, false);
2734 /* Do a second pass to evaluate static parts of common subexpressions */
2738 if (item
->child
->cdata
->flags
& SEL_CDATA_COMMONSUBEXPR
)
2740 bool bMinMax
= (item
->child
->cdata
->flags
& SEL_CDATA_DOMINMAX
) != 0;
2742 mark_subexpr_dynamic(item
->child
, false);
2743 item
->child
->u
.cgrp
.isize
= 0;
2744 /* We won't clear item->child->v.u.g here, because it may
2745 * be static, and hence actually point to item->child->cdata->gmax,
2746 * which is used below. We could also check whether this is the
2747 * case and only clear the group otherwise, but because the value
2748 * is actually overwritten immediately in the evaluate call, we
2749 * won't, because similar problems may arise if gmax handling ever
2750 * changes and the check were not updated.
2751 * For the same reason, we clear the min/max flag so that the
2752 * evaluation group doesn't get messed up. */
2753 set_evaluation_function(item
, &analyze_static
);
2754 item
->child
->cdata
->flags
&= ~SEL_CDATA_DOMINMAX
;
2755 item
->evaluate(&evaldata
, item
->child
, item
->child
->cdata
->gmax
);
2758 item
->child
->cdata
->flags
|= SEL_CDATA_DOMINMAX
;
2764 /* We need a yet another pass of subexpression removal to remove static
2765 * subexpressions referred to by common dynamic subexpressions. */
2766 sc
->root
= remove_unused_subexpressions(sc
->root
);
2767 // Update the reference counts, used by postprocess_item_subexpressions().
2771 init_item_subexpr_refcount(item
);
2777 fprintf(stderr
, "\nTree after second analysis pass:\n");
2778 coll
->printTree(stderr
, false);
2781 // Initialize evaluation groups, position calculations for methods, perform
2782 // some final optimization, and free the memory allocated for the
2784 /* By default, use whole residues/molecules. */
2785 flags
= POS_COMPLWHOLE
;
2786 PositionCalculationCollection::typeFromEnum(coll
->impl_
->rpost_
.c_str(), &post
, &flags
);
2790 init_root_item(item
, &sc
->gall
);
2791 postprocess_item_subexpressions(item
);
2792 init_item_comg(item
, &sc
->pcc
, post
, flags
);
2793 free_item_compilerdata(item
);
2797 // Compute the atoms required for evaluating the selections.
2798 gmx_ana_index_clear(&coll
->impl_
->requiredAtoms_
);
2799 gmx_ana_index_reserve(&coll
->impl_
->requiredAtoms_
, sc
->gall
.isize
);
2800 sc
->pcc
.getRequiredAtoms(&coll
->impl_
->requiredAtoms_
);
2804 init_required_atoms(item
, &coll
->impl_
->requiredAtoms_
);
2807 gmx_ana_index_squeeze(&coll
->impl_
->requiredAtoms_
);
2809 /* Allocate memory for the evaluation memory pool. */
2810 _gmx_sel_mempool_reserve(sc
->mempool
, 0);
2812 /* Finish up by calculating total masses and charges. */
2813 for (i
= 0; i
< sc
->sel
.size(); ++i
)
2815 sc
->sel
[i
]->initializeMassesAndCharges(sc
->top
);