cfengine  3.15.4
About: CFEngine is a configuration management system for configuring and maintaining Unix-like computers (using an own high level policy language). Community version.
  Fossies Dox: cfengine-3.15.4.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

iteration.c
Go to the documentation of this file.
1 /*
2  Copyright 2019 Northern.tech AS
3 
4  This file is part of CFEngine 3 - written and maintained by Northern.tech AS.
5 
6  This program is free software; you can redistribute it and/or modify it
7  under the terms of the GNU General Public License as published by the
8  Free Software Foundation; version 3.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program; if not, write to the Free Software
17  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
18 
19  To the extent this program is licensed as part of the Enterprise
20  versions of CFEngine, the applicable Commercial Open Source License
21  (COSL) may apply to this file if you as a licensee so wish it. See
22  included file COSL.txt.
23 */
24 
25 
26 #include <iteration.h>
27 
28 #include <scope.h>
29 #include <vars.h>
30 #include <fncall.h>
31 #include <eval_context.h>
32 #include <misc_lib.h>
33 #include <string_lib.h>
34 #include <assoc.h>
35 #include <expand.h> /* ExpandScalar */
36 #include <conversion.h> /* DataTypeIsIterable */
37 
38 
39 
40 /**
41  * WHEELS
42  *
43  * The iteration engine for CFEngine is set up with a number of "wheels" that
44  * roll in all combinations in order to iterate over everything - like the
45  * combination lock found on suitcases. One wheel is added for each iterable
46  * variable in the promiser-promisee-constraints strings. Iterable variables
47  * are slists and containers. But wheels are created in other cases as well,
48  * like variables that don't resolve yet but might change later on and
49  * possibly become iterables.
50  *
51  * The wheels are in struct PromiseIterator_ and are added right after
52  * initialisation of it, using PromiseIteratorPrepare() that calls ProcessVar().
53  *
54  * Wheels are added in the Seq in an order that matters: variables that depend
55  * on others to expand are *on the right* of their dependencies. That means
56  * that *independent variables are on the left*.
57  *
58  * EXAMPLE reports promise:
59  * "Value of A is $(A[$(i)][$(j)]) for indexes $(i) and $(j)"
60  *
61  * One appropriate wheels Seq for that would be: i j A[$(i)][$(j)]
62  *
63  * So for that promise 3 wheels get generated, and always the dependent
64  * variables are on the right of their dependencies. The wheels sequence would
65  * be exactly the same if the reports promise was simply "$(A[$(i)][$(j)])",
66  * because there are again the same 3 variables.
67  */
68 
69 /**
70  * ITERATING
71  *
72  * We push a new iteration context for each iteration, and VariablePut() into
73  * THIS context all selected single values of the iterable variables (slists
74  * or containers) represented by the wheels.
75  *
76  * *Thus EvalContext "THIS" never contains iterables (lists or containers).*
77  *
78  * This presents a problem for absolute references like $(abs.var), since
79  * these cannot be mapped into "this" without some magic (see MANGLING).
80  *
81  * The iteration context is popped and re-pushed for each iteration, until no
82  * further combinations of the wheel variables are left to be selected.
83  */
84 
85 /**
86  * SCOPE/NAMESPACE MANGLING
87  *
88  * One important thing to notice is that the variables that are
89  * namespaced/scope need to be *mangled* in order to be added as wheels. This
90  * means that the scope separator '.' and namespace separator ':' are replaced
91  * with '#' and '*' respectively. This happens in ProcessVar(), see comments
92  * for reasoning and further info.
93  */
94 
95 
96 
97 typedef struct {
98 
99  /* The unexpanded variable name, dependent on inner expansions. This
100  * field never changes after Wheel initialisation. */
102 
103  /* Number of dependencies of varname_unexp */
104  // const size_t deps;
105 
106  /* On each iteration of the wheels, the unexpanded string is
107  * re-expanded, so the following is refilled, again and again. */
108  char *varname_exp;
109 
110  /*
111  * Values of varname_exp, to iterate on. WE DO NOT OWN THE RVALS, they
112  * belong to EvalContext, so don't free(). Only if vartype is CONTAINER do
113  * we own the strings and we must free() them.
114  *
115  * After the iteration engine has started (via PromiseIteratorNext())
116  * "values" can be NULL when a variable does not resolve, or when it's
117  * not an iterable but it's already there in EvalContext, so no need to
118  * Put() separately; this means that it has exactly one value.
119  *
120  * When the variable resolves to an empty iterable (like empty slist or
121  * container) then it's not NULL, but SeqLength(values)==0.
122  *
123  * TODO values==NULL should only be unresolved variable -
124  * non-iterable variable should be SeqLength()==1.
125  */
127 
128  /* This is the list-type of the iterable variable, and this sets the type
129  * of the elements stored in Seq values. Only possibilities are INTLIST,
130  * REALLIST, SLIST, CONTAINER, NONE (if the variable did not resolve). */
132 
133  size_t iter_index; /* current iteration index */
134 
135 } Wheel;
136 
137 
140  const Promise *pp; /* not owned by us */
141  size_t count; /* total iterations count */
142 };
143 
144 
145 /**
146  * @NOTE #varname doesn't need to be '\0'-terminated, since the length is
147  * provided.
148  */
149 static Wheel *WheelNew(const char *varname, size_t varname_len)
150 {
151  Wheel new_wheel = {
152  .varname_unexp = xstrndup(varname, varname_len),
153  .varname_exp = NULL,
154  .values = NULL,
155  .vartype = -1,
156  .iter_index = 0
157  };
158 
159  return xmemdup(&new_wheel, sizeof(new_wheel));
160 }
161 
163 {
164  if (w->values != NULL)
165  {
166  /* Only if the variable resolved to type CONTAINER do we need to free
167  * the values, since we trasformed it to a Seq of strings. */
169  {
170  size_t values_len = SeqLength(w->values);
171  for (size_t i = 0; i < values_len; i++)
172  {
173  char *value = SeqAt(w->values, i);
174  free(value);
175  }
176  }
177  SeqDestroy(w->values);
178  w->values = NULL;
179  }
180  w->vartype = -1;
181 }
182 
183 static void WheelDestroy(void *wheel)
184 {
185  Wheel *w = wheel;
186  free(w->varname_unexp);
187  free(w->varname_exp);
189  free(w);
190 }
191 
192 /* Type of this function is SeqItemComparator for use in SeqLookup(). */
193 static int WheelCompareUnexpanded(const void *wheel1, const void *wheel2,
194  void *user_data ARG_UNUSED)
195 {
196  const Wheel *w1 = wheel1;
197  const Wheel *w2 = wheel2;
198  return strcmp(w1->varname_unexp, w2->varname_unexp);
199 }
200 
202 {
203  PromiseIterator iterctx = {
204  .wheels = SeqNew(4, WheelDestroy),
205  .pp = pp,
206  .count = 0
207  };
208  return xmemdup(&iterctx, sizeof(iterctx));
209 }
210 
212 {
213  SeqDestroy(iterctx->wheels);
214  free(iterctx);
215 }
216 
217 size_t PromiseIteratorIndex(const PromiseIterator *iter_ctx)
218 {
219  return iter_ctx->count;
220 }
221 
222 
223 /**
224  * Returns offset to "$(" or "${" in the string.
225  * Reads bytes up to s[max-1], s[max] is NOT read.
226  * If a '\0' is encountered before the pattern, return offset to `\0` byte
227  * If no '\0' byte or pattern is found within max bytes, max is returned
228  */
229 static size_t FindDollarParen(const char *s, size_t max)
230 {
231  size_t i = 0;
232 
233  while (i < max && s[i] != '\0')
234  {
235  if (i+1 < max && (s[i] == '$' && (s[i+1] == '(' || s[i+1] == '{')))
236  {
237  return i;
238  }
239  i++;
240  }
241  assert(i == max || s[i] == '\0');
242  return i;
243 }
244 
245 static char opposite(char c)
246 {
247  switch (c)
248  {
249  case '(': return ')';
250  case '{': return '}';
251  default : ProgrammingError("Was expecting '(' or '{' but got: '%c'", c);
252  }
253  return 0;
254 }
255 
256 /**
257  * Find the closing parenthesis for #c in #s. #c is considered to *not* be part
258  * of #s (IOW, #s is considered to be a string after #c).
259  *
260  * @return A closing parenthesis for #c in #s or %NULL if not found
261  */
262 static char *FindClosingParen(char *s, char c)
263 {
264  char closing = opposite(c);
265  int counter = 0;
266  for (char *cur=s; *cur != '\0'; cur++)
267  {
268  if (*cur == closing)
269  {
270  if (counter == 0)
271  {
272  return cur;
273  }
274  counter--;
275  }
276  if (*cur == c)
277  {
278  counter++;
279  }
280  }
281  return NULL;
282 }
283 
284 /**
285  * Check if variable reference is mangled, while avoiding going into the inner
286  * variables that are being expanded, or into array indexes.
287  *
288  * @NOTE variable name is naked, i.e. shouldn't start with dollar-paren.
289  */
290 static bool IsMangled(const char *s)
291 {
292  assert(s != NULL);
293  size_t s_length = strlen(s);
294  size_t dollar_paren = FindDollarParen(s, s_length);
295  size_t bracket = strchrnul(s, '[') - s;
296  size_t upto = MIN(dollar_paren, bracket);
297  size_t mangled_ns = strchrnul(s, CF_MANGLED_NS) - s;
298  size_t mangled_scope = strchrnul(s, CF_MANGLED_SCOPE) - s;
299 
300  if (mangled_ns < upto ||
301  mangled_scope < upto)
302  {
303  return true;
304  }
305  else
306  {
307  return false;
308  }
309 }
310 
311 /**
312  * Mangle namespace and scope separators, up to '$(', '${', '[', '\0',
313  * whichever comes first.
314  *
315  * "this" scope is never mangled, no need to VariablePut() a mangled reference
316  * in THIS scope, since the non-manled one already exists.
317  */
318 static void MangleVarRefString(char *ref_str, size_t len)
319 {
320  // printf("MangleVarRefString: %.*s\n", (int) len, ref_str);
321 
322  size_t dollar_paren = FindDollarParen(ref_str, len);
323  size_t upto = MIN(len, dollar_paren);
324  char *bracket = memchr(ref_str, '[', upto);
325  if (bracket != NULL)
326  {
327  upto = bracket - ref_str;
328  }
329 
330  char *ns = memchr(ref_str, ':', upto);
331  char *ref_str2 = ref_str;
332  if (ns != NULL)
333  {
334  *ns = CF_MANGLED_NS;
335  ref_str2 = ns + 1;
336  upto -= (ns + 1 - ref_str);
337  assert(upto >= 0);
338  }
339 
340  bool mangled_scope = false;
341  char *scope = memchr(ref_str2, '.', upto);
342  if (scope != NULL &&
343  strncmp(ref_str2, "this", 4) != 0)
344  {
345  *scope = CF_MANGLED_SCOPE;
346  mangled_scope = true;
347  }
348 
349  if (mangled_scope || ns != NULL)
350  {
352  "Mangled namespaced/scoped variable for iterating over it: %.*s",
353  (int) len, ref_str);
354  }
355 }
356 
357 /**
358  * Lookup a variable within iteration context. Since the scoped or namespaced
359  * variable names may be mangled, we have to look them up using special
360  * separators CF_MANGLED_NS and CF_MANGLED_SCOPE.
361  */
362 static const void *IterVariableGet(const PromiseIterator *iterctx,
363  const EvalContext *evalctx,
364  const char *varname, DataType *type)
365 {
366  const void *value;
367  const Bundle *bundle = PromiseGetBundle(iterctx->pp);
368 
369  /* Equivalent to:
370  VarRefParseFromBundle(varname, PromiseGetBundle(iterctx->pp))
371 
372  but with custom namespace,scope separators. Even !IsMangled(varname) it
373  should be resolved properly since the secondary separators shouldn't
374  alter the result for an unqualified varname. */
375  VarRef *ref =
376  VarRefParseFromNamespaceAndScope(varname, bundle->ns, bundle->name,
378  value = EvalContextVariableGet(evalctx, ref, type);
379  VarRefDestroy(ref);
380 
381  if (*type == CF_DATA_TYPE_NONE) /* did not resolve */
382  {
383  assert(value == NULL);
384 
385  if (!IsMangled(varname))
386  {
387  /* Lookup with no mangling, it might be a scoped/namespaced
388  * variable that is not an iterable, so it was not mangled in
389  * ProcessVar(). */
390  VarRef *ref2 = VarRefParse(varname);
391  value = EvalContextVariableGet(evalctx, ref2, type);
392  VarRefDestroy(ref2);
393  }
394  }
395 
396  return value;
397 }
398 
399 /* TODO this is ugly!!! mapdata() needs to be refactored to put a whole slist
400  as "this.k". But how? It is executed *after* PromiseIteratorNext()! */
401 static bool VarIsSpecial(const char *s)
402 {
403  if (strcmp(s, "this") == 0 ||
404  strcmp(s, "this.k") == 0 ||
405  strcmp(s, "this.v") == 0 ||
406  strcmp(s, "this.k[1]") == 0 ||
407  strcmp(s, "this.this") == 0)
408  {
409  return true;
410  }
411  else
412  {
413  return false;
414  }
415 }
416 
417 /**
418  * Decide whether to mangle varname and add wheel to the iteration engine.
419  *
420  * If variable contains inner expansions -> mangle and add wheel
421  * (because you don't know if it will be an iterable or not - you will
422  * know after inner variable is iterated and the variable is looked up)
423  *
424  * else if it resolves to iterable -> mangle and add wheel
425  *
426  * else if it resolves to empty iterable -> mangle and add wheel
427  * (see comments in code)
428  *
429  * else if the variable name is special for some functions (this.k etc)
430  * -> mangle and add wheel
431  *
432  * else if it resolves to non-iterable -> no mangle, no wheel
433  *
434  * else if it doesn't resolve -> no mangle, no wheel
435  *
436  * @NOTE Important special scopes (e.g. "connection.ip" for cf-serverd) must
437  * not be mangled to work correctly. This is auto-OK because such
438  * variables do not resolve usually.
439  */
441  const PromiseIterator *iterctx,
442  const EvalContext *evalctx,
443  char *varname, size_t varname_len)
444 {
445  bool result;
446  /* Shorten string temporarily to the appropriate length. */
447  char tmp_c = varname[varname_len];
448  varname[varname_len] = '\0';
449 
450  VarRef *ref = VarRefParseFromBundle(varname,
451  PromiseGetBundle(iterctx->pp));
452  DataType t;
453  ARG_UNUSED const void *value = EvalContextVariableGet(evalctx, ref, &t);
454  VarRefDestroy(ref);
455 
456  size_t dollar_paren = FindDollarParen(varname, varname_len);
457  if (dollar_paren < varname_len)
458  {
459  /* Varname contains inner expansions, so maybe the variable will
460  * resolve to an iterable during the iteration - must add wheel. */
461  result = true;
462  }
463  else if (DataTypeIsIterable(t))
464  {
465  result = true;
466 
467  /* NOTE: If it is an EMPTY ITERABLE i.e. value==NULL, we are still
468  * adding an iteration wheel, but with "wheel->values" set to an empty
469  * Seq. The reason is that the iteration engine will completely *skip*
470  * all promise evaluations when one of the wheels is empty.
471  *
472  * Otherwise, if we didn't add the empty wheel, even if the promise
473  * contained no other wheels, the promise would get evaluated exactly
474  * once with "$(varname)" literally in there. */
475  }
476  else if (VarIsSpecial(varname))
477  {
478  result = true;
479  }
480  else
481  {
482  /*
483  * Either varname resolves to a non-iterable, e.g. string.
484  * Or it does not resolve.
485  *
486  * Since this variable does not contain inner expansions, this can't
487  * change during iteration of other variables. So don't add wheel -
488  * i.e. don't iterate over this variable's values, because we know
489  * there will always be only one value.
490  */
491  result = false;
492  }
493 
494  varname[varname_len] = tmp_c; /* Restore original string */
495  return result;
496 }
497 
498 /**
499  * Recursive function that adds wheels to the iteration engine, according to
500  * the variable (and possibly its inner variables) in #s.
501  *
502  * Another important thing it does, is *modify* the string #s, mangling all
503  * scoped or namespaced variable names. Mangling is done in order to iterate
504  * over foreign variables, without modifying the foreign value. For example if
505  * "test.var" is an slist, then we mangle it as "test#var" and on each
506  * iteration we just VariablePut(test#var) in the local scope.
507  * Mangling is skipped for variables that do not resolve, since they are not
508  * to be iterated over.
509  *
510  * @param s is the start of a variable name, right after "$(" or "${".
511  * @param c is the character after '$', i.e. must be either '(' or '{'.
512  * @return pointer to the closing parenthesis or brace of the variable, or
513  * if not found, returns a pointer to terminating '\0' of #s.
514  */
515 static char *ProcessVar(PromiseIterator *iterctx, const EvalContext *evalctx,
516  char *s, char c)
517 {
518  assert(s != NULL);
519  assert(c == '(' || c == '{');
520 
521  char *s_end = FindClosingParen(s, c);
522  const size_t s_max = strlen(s);
523  if (s_end == NULL)
524  {
525  /* Set s_end to the point to the NUL byte if no closing parenthesis was
526  * found. It's used for comparisons and other things below. */
527  s_end = s + s_max;
528  }
529  char *next_var = s + FindDollarParen(s, s_max);
530  size_t deps = 0;
531 
532  while (next_var < s_end) /* does it have nested variables? */
533  {
534  /* It's a dependent variable, the wheels of the dependencies must be
535  * added first. Example: "$(blah_$(dependency))" */
536 
537  assert(next_var[0] != '\0');
538  assert(next_var[1] != '\0');
539 
540  char *subvar_end = ProcessVar(iterctx, evalctx,
541  &next_var[2], next_var[1]);
542 
543  /* Was there unbalanced paren for the inner expansion? */
544  if (*subvar_end == '\0')
545  {
546  /* Despite unclosed parenthesis for the inner expansion,
547  * the outer variable might close with a brace, or not. */
548  const size_t s_end_len = strlen(s_end);
549  next_var = s_end + FindDollarParen(s_end, s_end_len);
550  /* s_end is already correct */
551  }
552  else /* inner variable processed correctly */
553  {
554  /* This variable depends on inner expansions. */
555  deps++;
556  /* We are sure (subvar_end+1) is not out of bounds. */
557  char *s_next = subvar_end + 1;
558  const size_t s_next_len = strlen(s_next);
559  s_end = FindClosingParen(s_next, c);
560  if (s_end == NULL)
561  {
562  /* Set s_end to the point to the NUL byte if no closing parenthesis was
563  * found. It's used for comparisons and other things below. */
564  s_end = s_next + s_next_len;
565  }
566  next_var = s_next + FindDollarParen(s_next, s_next_len);
567  }
568  }
569 
570  assert(s_end != NULL);
571  if (*s_end == '\0')
572  {
573  Log(LOG_LEVEL_ERR, "No closing '%c' found for variable: %s",
574  opposite(c), s);
575  return s_end;
576  }
577 
578  const size_t s_len = s_end - s;
579 
580  if (ShouldAddVariableAsIterationWheel(iterctx, evalctx, s, s_len))
581  {
582  /* Change the variable name in order to mangle namespaces and scopes. */
583  MangleVarRefString(s, s_len);
584 
585  Wheel *new_wheel = WheelNew(s, s_len);
586 
587  /* If identical variable is already inserted, it means that it has
588  * been seen before and has been inserted together with all
589  * dependencies; skip. */
590  /* It can happen if variables exist twice in a string, for example:
591  "$(i) blah $(A[$(i)])" has i variable twice. */
592 
593  bool same_var_found = (SeqLookup(iterctx->wheels, new_wheel,
595  if (same_var_found)
596  {
598  "Skipped adding iteration wheel for already existing variable: %s",
599  new_wheel->varname_unexp);
600  WheelDestroy(new_wheel);
601  }
602  else
603  {
604  /* If this variable is dependent on other variables, we've already
605  * appended the wheels of the dependencies during the recursive
606  * calls. Or it happens and this is an independent variable. So
607  * now APPEND the wheel for this variable. */
608  SeqAppend(iterctx->wheels, new_wheel);
609 
611  "Added iteration wheel %zu for variable: %s",
612  SeqLength(iterctx->wheels) - 1,
613  new_wheel->varname_unexp);
614  }
615  }
616 
617  assert(s_end != NULL);
618  assert(*s_end == opposite(c));
619  return s_end;
620 }
621 
622 /**
623  * @brief Fills up the wheels of the iterator according to the variables
624  * found in #s. Also mangles all namespaced/scoped variables in #s.
625  *
626  * @EXAMPLE Have a look in iteration_test.c:test_PromiseIteratorPrepare()
627  *
628  * @NOTE the wheel numbers can't change once iteration started, so make sure
629  * you call WheelIteratorPrepare() in advance, as many times it's
630  * needed.
631  */
633  const EvalContext *evalctx,
634  char *s)
635 {
636  assert(s != NULL);
637  LogDebug(LOG_MOD_ITERATIONS, "PromiseIteratorPrepare(\"%s\")", s);
638  const size_t s_len = strlen(s);
639  const size_t offset = FindDollarParen(s, s_len);
640 
641  assert(offset <= s_len); // FindDollarParen guarantees this
642  if (offset == s_len)
643  {
644  return; // Don't search past NULL terminator
645  }
646 
647  char *var_start = s + offset;
648  while (*var_start != '\0')
649  {
650  char paren_or_brace = var_start[1];
651  var_start += 2; /* skip dollar-paren */
652 
653  assert(paren_or_brace == '(' || paren_or_brace == '{');
654 
655  char *var_end = ProcessVar(iterctx, evalctx, var_start, paren_or_brace);
656  assert(var_end != NULL);
657  if (*var_end == '\0')
658  {
659  return; // Don't search past NULL terminator
660  }
661  char *var_next = var_end + 1;
662  const size_t var_next_len = s_len - (var_next - s);
663  const size_t var_offset = FindDollarParen(var_next, var_next_len);
664  assert(var_offset <= var_next_len);
665  if (var_offset == var_next_len)
666  {
667  return; // Don't search past NULL terminator
668  }
669  var_start = var_next + var_offset;
670  }
671 }
672 
674  const char *varname,
675  DataType listtype, void *value)
676 {
677  DataType t;
678 
679  switch (listtype)
680  {
683  case CF_DATA_TYPE_INT_LIST: t = CF_DATA_TYPE_INT; break;
684  case CF_DATA_TYPE_REAL_LIST: t = CF_DATA_TYPE_REAL; break;
685  default:
686  t = CF_DATA_TYPE_NONE; /* silence warning */
687  ProgrammingError("IterVariablePut() invalid type: %d",
688  listtype);
689  }
690 
692  varname, value,
693  t, "source=promise_iteration");
694 }
695 
696 static void SeqAppendContainerPrimitive(Seq *seq, const JsonElement *primitive)
697 {
698  assert(JsonGetElementType(primitive) == JSON_ELEMENT_TYPE_PRIMITIVE);
699 
700  switch (JsonGetPrimitiveType(primitive))
701  {
703  SeqAppend(seq, (JsonPrimitiveGetAsBool(primitive) ?
704  xstrdup("true") : xstrdup("false")));
705  break;
707  {
708  char *str = StringFromLong(JsonPrimitiveGetAsInteger(primitive));
709  SeqAppend(seq, str);
710  break;
711  }
713  {
714  char *str = StringFromDouble(JsonPrimitiveGetAsReal(primitive));
715  SeqAppend(seq, str);
716  break;
717  }
719  SeqAppend(seq, xstrdup(JsonPrimitiveGetAsString(primitive)));
720  break;
721 
723  break;
724  }
725 }
726 
727 static Seq *ContainerToSeq(const JsonElement *container)
728 {
729  Seq *seq = SeqNew(5, NULL);
730 
731  switch (JsonGetElementType(container))
732  {
734  SeqAppendContainerPrimitive(seq, container);
735  break;
736 
738  {
739  JsonIterator iter = JsonIteratorInit(container);
740  const JsonElement *child;
741 
742  while ((child = JsonIteratorNextValue(&iter)) != NULL)
743  {
745  {
746  SeqAppendContainerPrimitive(seq, child);
747  }
748  }
749  break;
750  }
751  }
752 
753  /* TODO SeqFinalise() to save space? */
754  return seq;
755 }
756 
757 static Seq *RlistToSeq(const Rlist *p)
758 {
759  Seq *seq = SeqNew(5, NULL);
760 
761  const Rlist *rlist = p;
762  while(rlist != NULL)
763  {
764  Rval val = rlist->val;
765  SeqAppend(seq, val.item);
766  rlist = rlist->next;
767  }
768 
769  /* TODO SeqFinalise() to save space? */
770  return seq;
771 }
772 
773 static Seq *IterableToSeq(const void *v, DataType t)
774 {
775  switch (t)
776  {
778  return ContainerToSeq(v);
779  break;
783  /* All lists are stored as Rlist internally. */
784  assert(DataTypeToRvalType(t) == RVAL_TYPE_LIST);
785  return RlistToSeq(v);
786 
787  default:
788  ProgrammingError("IterableToSeq() got non-iterable type: %d", t);
789  }
790 }
791 
792 /**
793  * For each of the wheels to the right of wheel_idx (including this one)
794  *
795  * 1. varname_exp = expand the variable name
796  * - if it's same with previous varname_exp, skip steps 2-4
797  * 2. values = VariableGet(varname_exp);
798  * 3. if the value is an iterable (slist/container), set the wheel size.
799  * 4. reset the wheel in order to re-iterate over all combinations.
800  * 5. Put(varname_exp:first_value) in the EvalContext
801  */
803  const PromiseIterator *iterctx,
804  EvalContext *evalctx,
805  size_t wheel_idx)
806 {
807  /* Buffer to store the expanded wheel variable name, for each wheel. */
808  Buffer *tmpbuf = BufferNew();
809 
810  size_t wheels_num = SeqLength(iterctx->wheels);
811  for (size_t i = wheel_idx; i < wheels_num; i++)
812  {
813  Wheel *wheel = SeqAt(iterctx->wheels, i);
814  BufferClear(tmpbuf);
815 
816  /* Reset wheel in order to re-iterate over all combinations. */
817  wheel->iter_index = 0;
818 
819  /* The wheel variable may depend on previous wheels, for example
820  * "B_$(k)_$(v)" is dependent on variables "k" and "v", which are
821  * wheels already set (to the left, or at lower i index). */
822  const char *varname = ExpandScalar(evalctx,
823  PromiseGetNamespace(iterctx->pp),
824  /* Use NULL as scope so that we try both "this" and "bundle" scopes. */
825  NULL,
826  wheel->varname_unexp, tmpbuf);
827 
828  /* If it expanded to something different than before. */
829  if (wheel->varname_exp == NULL
830  || strcmp(varname, wheel->varname_exp) != 0)
831  {
832  free(wheel->varname_exp); /* could be NULL */
833  wheel->varname_exp = xstrdup(varname);
834 
835  WheelValuesSeqDestroy(wheel); /* free previous values */
836 
837  /* After expanding the variable name, we have to lookup its value,
838  and set the size of the wheel if it's an slist or container. */
839  DataType value_type;
840  const void *value = IterVariableGet(iterctx, evalctx,
841  varname, &value_type);
842  wheel->vartype = value_type;
843 
844  /* Set wheel values and size according to variable type. */
845  if (DataTypeIsIterable(value_type))
846  {
847  wheel->values = IterableToSeq(value, value_type);
848 
849  if (SeqLength(wheel->values) == 0)
850  {
851  /*
852  * If this variable now expands to a 0-length list, then
853  * we should skip this iteration, no matter the
854  * other variables: "zero times whatever" multiplication
855  * always equals zero.
856  */
858  "Skipping iteration since variable '%s'"
859  " resolves to an empty list", varname);
860  }
861  else
862  {
863  assert( wheel->values != NULL);
864  assert(SeqLength(wheel->values) > 0);
865  assert( SeqAt(wheel->values, 0) != NULL);
866 
867  /* Put the first value of the iterable. */
868  IterListElementVariablePut(evalctx, varname, value_type,
869  SeqAt(wheel->values, 0));
870  }
871  }
872  /* It it's NOT AN ITERABLE BUT IT RESOLVED AND IT IS MANGLED: this
873  * is possibly a variable that was unresolvable during the
874  * Prepare() stage, but now resolves to a string etc. We still
875  * need to Put() it despite not being an iterable, since the
876  * mangled version is not in the EvalContext.
877  * The "values" Seq is left as NULL. */
878  else if (value_type != CF_DATA_TYPE_NONE && IsMangled(varname))
879  {
881  varname, value, value_type,
882  "source=promise_iteration");
883  }
884  /* It's NOT AN ITERABLE AND IT'S NOT MANGLED, which means that
885  * the variable with the correct value (the only value) is already
886  * in the EvalContext, no need to Put() it again. */
887  /* OR it doesn't resolve at all! */
888  else
889  {
890  /* DO NOTHING, everything is already set. */
891 
892  assert(!DataTypeIsIterable(value_type));
893  assert(value_type == CF_DATA_TYPE_NONE || /* var does not resolve */
894  !IsMangled(varname)); /* or is not mangled */
895  /* We don't allocate Seq for non-iterables. */
896  assert(wheel->values == NULL);
897  }
898  }
899  else /* The variable name expanded to the same name */
900  {
901  /* speedup: the variable name expanded to the same name, so the
902  * value is the same and wheel->values is already correct. So if
903  * it's an iterable, we VariablePut() the first element. */
904  if (wheel->values != NULL && SeqLength(wheel->values) > 0)
905  {
906  /* Put the first value of the iterable. */
908  wheel->varname_exp, wheel->vartype,
909  SeqAt(wheel->values, 0));
910  }
911  }
912  }
913 
914  BufferDestroy(tmpbuf);
915 }
916 
917 static bool IteratorHasEmptyWheel(const PromiseIterator *iterctx)
918 {
919  size_t wheels_num = SeqLength(iterctx->wheels);
920  for (size_t i = 0; i < wheels_num; i++)
921  {
922  Wheel *wheel = SeqAt(iterctx->wheels, i);
923  assert(wheel != NULL);
924 
925  if (VarIsSpecial(wheel->varname_unexp)) /* TODO this is ugly! */
926  {
927  return false;
928  }
929 
930  /* If variable resolves to an empty iterable or it doesn't resolve. */
931  if ((wheel->values != NULL &&
932  SeqLength(wheel->values) == 0)
933  ||
934  wheel->vartype == CF_DATA_TYPE_NONE)
935  {
936  return true;
937  }
938  }
939 
940  return false;
941 }
942 
943 /* Try incrementing the rightmost wheel first that has values left to iterate on.
944  (rightmost i.e. the most dependent variable). */
946 {
947  size_t wheels_num = SeqLength(iterctx->wheels);
948  size_t i = wheels_num;
949  Wheel *wheel;
950 
951  assert(wheels_num > 0);
952 
953  do
954  {
955  if (i == 0)
956  {
957  return (size_t) -1; /* all wheels have been iterated over */
958  }
959 
960  i--; /* move one wheel to the left */
961  wheel = SeqAt(iterctx->wheels, i);
962  wheel->iter_index++;
963 
964  /* Stop when we have found a wheel with value available at iter_index. */
965  } while (wheel->values == NULL ||
966  wheel->vartype == CF_DATA_TYPE_NONE ||
967  SeqLength(wheel->values) == 0 ||
968  wheel->iter_index >= SeqLength(wheel->values));
969 
970  return i; /* return which wheel was incremented */
971 }
972 
973 /* Nothing to iterate on, so get out after running the promise once.
974  * Because all promises, even if there are zero variables to be
975  * expanded in them, must be evaluated. */
976 static bool RunOnlyOnce(PromiseIterator *iterctx)
977 {
978  assert(SeqLength(iterctx->wheels) == 0);
979 
980  if (iterctx->count == 0)
981  {
982  iterctx->count++;
983  return true;
984  }
985  else
986  {
987  return false;
988  }
989 }
990 
992 {
993  size_t wheels_num = SeqLength(iterctx->wheels);
994 
995  if (wheels_num == 0)
996  {
997  return RunOnlyOnce(iterctx);
998  }
999 
1000  bool done = false;
1001 
1002  /* First iteration: we initialise all wheels. */
1003  if (iterctx->count == 0)
1004  {
1005  Log(LOG_LEVEL_DEBUG, "Starting iteration engine with %zu wheels"
1006  " --- ENTERING WARP SPEED",
1007  wheels_num);
1008 
1009  ExpandAndPutWheelVariablesAfter(iterctx, evalctx, 0);
1010 
1011  done = ! IteratorHasEmptyWheel(iterctx);
1012  }
1013 
1014  while (!done)
1015  {
1016  size_t i = WheelRightmostIncrement(iterctx);
1017  if (i == (size_t) -1) /* all combinations have been tried */
1018  {
1019  Log(LOG_LEVEL_DEBUG, "Iteration engine finished"
1020  " --- WARPING OUT");
1021  return false;
1022  }
1023 
1024  /*
1025  * Alright, incrementing the wheel at index "i" was successful. Now
1026  * Put() the new value of the variable in the EvalContext. This is the
1027  * *basic iteration step*, just going to the next value of the
1028  * iterable.
1029  */
1030  Wheel *wheel = SeqAt(iterctx->wheels, i);
1031  void *new_value = SeqAt(wheel->values, wheel->iter_index);
1032 
1034  evalctx, wheel->varname_exp, wheel->vartype, new_value);
1035 
1036  /* All the wheels to the right of the one we changed have to be reset
1037  * and recomputed, in order to do all possible combinations. */
1038  ExpandAndPutWheelVariablesAfter(iterctx, evalctx, i + 1);
1039 
1040  /* If any of the wheels has no values to offer, then this iteration
1041  * should be skipped completely; so the function doesn't yield any
1042  * result yet, it just loops over until it finds a meaningful one. */
1043  done = ! IteratorHasEmptyWheel(iterctx);
1044 
1045  LogDebug(LOG_MOD_ITERATIONS, "PromiseIteratorNext():"
1046  " count=%zu wheels_num=%zu current_wheel=%zd",
1047  iterctx->count, wheels_num, (ssize_t) i);
1048 
1049  /* TODO if not done, then we are re-Put()ing variables in the EvalContect,
1050  * hopefully overwriting the previous values, but possibly not! */
1051  }
1052 
1053  // Recompute `with`
1054  for (size_t i = 0; i < SeqLength(iterctx->pp->conlist); i++)
1055  {
1056  Constraint *cp = SeqAt(iterctx->pp->conlist, i);
1057  if (StringEqual(cp->lval, "with"))
1058  {
1059  Rval final = EvaluateFinalRval(evalctx, PromiseGetPolicy(iterctx->pp), NULL,
1060  "this", cp->rval, false, iterctx->pp);
1061  if (final.type == RVAL_TYPE_SCALAR && !IsCf3VarString(RvalScalarValue(final)))
1062  {
1064  "with", RvalScalarValue(final),
1066  "source=promise_iteration/with");
1067  }
1068  RvalDestroy(final);
1069  }
1070  }
1071  iterctx->count++;
1072  return true;
1073 }
char * xstrdup(const char *str)
Definition: alloc-mini.c:56
void * xmemdup(const void *data, size_t size)
Definition: alloc.c:66
char * xstrndup(const char *str, size_t n)
Definition: alloc.c:61
void BufferDestroy(Buffer *buffer)
Destroys a buffer and frees the memory associated with it.
Definition: buffer.c:72
Buffer * BufferNew(void)
Buffer initialization routine.
Definition: buffer.c:48
void BufferClear(Buffer *buffer)
Clears the buffer.
Definition: buffer.c:457
#define ARG_UNUSED
Definition: cf-net.c:47
#define CF_MANGLED_SCOPE
Definition: cf3.defs.h:115
#define CF_MANGLED_NS
Definition: cf3.defs.h:114
@ RVAL_TYPE_LIST
Definition: cf3.defs.h:607
@ RVAL_TYPE_SCALAR
Definition: cf3.defs.h:606
DataType
Definition: cf3.defs.h:368
@ CF_DATA_TYPE_NONE
Definition: cf3.defs.h:385
@ CF_DATA_TYPE_REAL
Definition: cf3.defs.h:371
@ CF_DATA_TYPE_STRING_LIST
Definition: cf3.defs.h:372
@ CF_DATA_TYPE_INT_LIST
Definition: cf3.defs.h:373
@ CF_DATA_TYPE_STRING
Definition: cf3.defs.h:369
@ CF_DATA_TYPE_INT
Definition: cf3.defs.h:370
@ CF_DATA_TYPE_CONTAINER
Definition: cf3.defs.h:384
@ CF_DATA_TYPE_REAL_LIST
Definition: cf3.defs.h:374
void free(void *)
bool DataTypeIsIterable(DataType t)
Definition: conversion.c:757
const void * EvalContextVariableGet(const EvalContext *ctx, const VarRef *ref, DataType *type_out)
bool EvalContextVariablePutSpecial(EvalContext *ctx, SpecialScope scope, const char *lval, const void *value, DataType type, const char *tags)
char * ExpandScalar(const EvalContext *ctx, const char *ns, const char *scope, const char *string, Buffer *out)
Definition: expand.c:516
Rval EvaluateFinalRval(EvalContext *ctx, const Policy *policy, const char *ns, const char *scope, Rval rval, bool forcelist, const Promise *pp)
Definition: expand.c:610
#define NULL
Definition: getopt1.c:56
static size_t WheelRightmostIncrement(PromiseIterator *iterctx)
Definition: iteration.c:945
static Seq * RlistToSeq(const Rlist *p)
Definition: iteration.c:757
static bool VarIsSpecial(const char *s)
Definition: iteration.c:401
static bool IsMangled(const char *s)
Definition: iteration.c:290
static void WheelDestroy(void *wheel)
Definition: iteration.c:183
static char * ProcessVar(PromiseIterator *iterctx, const EvalContext *evalctx, char *s, char c)
Definition: iteration.c:515
static int WheelCompareUnexpanded(const void *wheel1, const void *wheel2, void *user_data)
Definition: iteration.c:193
static char * FindClosingParen(char *s, char c)
Definition: iteration.c:262
static char opposite(char c)
Definition: iteration.c:245
void PromiseIteratorPrepare(PromiseIterator *iterctx, const EvalContext *evalctx, char *s)
Fills up the wheels of the iterator according to the variables found in #s. Also mangles all namespac...
Definition: iteration.c:632
static void WheelValuesSeqDestroy(Wheel *w)
Definition: iteration.c:162
static const void * IterVariableGet(const PromiseIterator *iterctx, const EvalContext *evalctx, const char *varname, DataType *type)
Definition: iteration.c:362
static bool RunOnlyOnce(PromiseIterator *iterctx)
Definition: iteration.c:976
static void SeqAppendContainerPrimitive(Seq *seq, const JsonElement *primitive)
Definition: iteration.c:696
static void IterListElementVariablePut(EvalContext *evalctx, const char *varname, DataType listtype, void *value)
Definition: iteration.c:673
static Seq * ContainerToSeq(const JsonElement *container)
Definition: iteration.c:727
static bool ShouldAddVariableAsIterationWheel(const PromiseIterator *iterctx, const EvalContext *evalctx, char *varname, size_t varname_len)
Definition: iteration.c:440
static Wheel * WheelNew(const char *varname, size_t varname_len)
Definition: iteration.c:149
static Seq * IterableToSeq(const void *v, DataType t)
Definition: iteration.c:773
static size_t FindDollarParen(const char *s, size_t max)
Definition: iteration.c:229
static void MangleVarRefString(char *ref_str, size_t len)
Definition: iteration.c:318
bool PromiseIteratorNext(PromiseIterator *iterctx, EvalContext *evalctx)
Definition: iteration.c:991
static bool IteratorHasEmptyWheel(const PromiseIterator *iterctx)
Definition: iteration.c:917
PromiseIterator * PromiseIteratorNew(const Promise *pp)
Definition: iteration.c:201
static void ExpandAndPutWheelVariablesAfter(const PromiseIterator *iterctx, EvalContext *evalctx, size_t wheel_idx)
Definition: iteration.c:802
size_t PromiseIteratorIndex(const PromiseIterator *iter_ctx)
Definition: iteration.c:217
void PromiseIteratorDestroy(PromiseIterator *iterctx)
Definition: iteration.c:211
bool JsonPrimitiveGetAsBool(const JsonElement *const primitive)
Definition: json.c:741
JsonElementType JsonGetElementType(const JsonElement *const element)
Definition: json.c:667
JsonIterator JsonIteratorInit(const JsonElement *const container)
Definition: json.c:549
JsonElement * JsonIteratorNextValue(JsonIterator *const iter)
Definition: json.c:568
JsonPrimitiveType JsonGetPrimitiveType(const JsonElement *const primitive)
Definition: json.c:693
double JsonPrimitiveGetAsReal(const JsonElement *const primitive)
Definition: json.c:787
const char * JsonPrimitiveGetAsString(const JsonElement *const primitive)
Definition: json.c:701
long JsonPrimitiveGetAsInteger(const JsonElement *const primitive)
Definition: json.c:750
@ JSON_PRIMITIVE_TYPE_REAL
Definition: json.h:66
@ JSON_PRIMITIVE_TYPE_INTEGER
Definition: json.h:65
@ JSON_PRIMITIVE_TYPE_NULL
Definition: json.h:68
@ JSON_PRIMITIVE_TYPE_STRING
Definition: json.h:64
@ JSON_PRIMITIVE_TYPE_BOOL
Definition: json.h:67
@ JSON_ELEMENT_TYPE_PRIMITIVE
Definition: json.h:53
@ JSON_ELEMENT_TYPE_CONTAINER
Definition: json.h:52
@ LogDebug
Definition: log.h:34
void Log(LogLevel level, const char *fmt,...)
Definition: logging.c:409
@ LOG_MOD_ITERATIONS
Definition: logging.h:60
@ LOG_LEVEL_ERR
Definition: logging.h:42
@ LOG_LEVEL_DEBUG
Definition: logging.h:47
@ LOG_LEVEL_VERBOSE
Definition: logging.h:46
#define ProgrammingError(...)
Definition: misc_lib.h:33
#define MIN(a, b)
Definition: platform.h:478
const char * PromiseGetNamespace(const Promise *pp)
Definition: policy.c:2666
const Policy * PromiseGetPolicy(const Promise *pp)
Definition: policy.c:2676
const Bundle * PromiseGetBundle(const Promise *pp)
Definition: policy.c:2671
char * RvalScalarValue(Rval rval)
Definition: rlist.c:129
RvalType DataTypeToRvalType(DataType datatype)
Definition: rlist.c:44
void RvalDestroy(Rval rval)
Definition: rlist.c:940
@ SPECIAL_SCOPE_THIS
Definition: scope.h:39
size_t SeqLength(const Seq *seq)
Length of the sequence.
Definition: sequence.c:354
Seq * SeqNew(size_t initialCapacity, void(ItemDestroy)(void *item))
Definition: sequence.c:31
void * SeqLookup(Seq *seq, const void *key, SeqItemComparator Compare)
Linearly searches through the sequence and return the first item considered equal to the specified ke...
Definition: sequence.c:161
void SeqDestroy(Seq *seq)
Destroy an existing Sequence.
Definition: sequence.c:60
void SeqAppend(Seq *seq, void *item)
Append a new item to the Sequence.
Definition: sequence.c:104
static void * SeqAt(const Seq *seq, int i)
Definition: sequence.h:57
char * strchrnul(const char *s, int c)
Definition: strchrnul.c:9
char * StringFromDouble(double number)
Definition: string_lib.c:741
bool StringEqual(const char *const a, const char *const b)
Definition: string_lib.c:256
char * StringFromLong(long number)
Definition: string_lib.c:720
Definition: buffer.h:50
Definition: policy.h:70
char * name
Definition: policy.h:74
char * ns
Definition: policy.h:75
Rval rval
Definition: policy.h:133
char * lval
Definition: policy.h:132
const Promise * pp
Definition: iteration.c:140
Seq * conlist
Definition: policy.h:117
Definition: rlist.h:35
Rval val
Definition: rlist.h:36
Rlist * next
Definition: rlist.h:37
Definition: cf3.defs.h:614
void * item
Definition: cf3.defs.h:615
Sequence data-structure.
Definition: sequence.h:50
char * varname_exp
Definition: iteration.c:108
Seq * values
Definition: iteration.c:126
DataType vartype
Definition: iteration.c:131
size_t iter_index
Definition: iteration.c:133
char * varname_unexp
Definition: iteration.c:101
VarRef * VarRefParse(const char *var_ref_string)
void VarRefDestroy(VarRef *ref)
VarRef * VarRefParseFromBundle(const char *var_ref_string, const Bundle *bundle)
Parse the variable reference in the context of a bundle. This means that the VarRef will inherit scop...
VarRef * VarRefParseFromNamespaceAndScope(const char *qualified_name, const char *_ns, const char *_scope, char ns_separator, char scope_separator)
bool IsCf3VarString(const char *str)
Definition: vars.c:123