Feature request: Allow overlapping ranges in range expressions.

[ddneilson]

Use Case

In a part of a guide on creating job templates we want to talk about how you can "prechunk" your frame range to create tasks that render more than one frame at a time. The ideal way to be doing this is with some range expressions like so:

    parameterSpace:
      taskParameterDefinitions:
        - name: RangeStart
          type: INT
          range: "{{Param.FrameStart}}-{{Param.FrameEnd}}:{{Param.FramesPerTask}}"
        - name: RangeEnd
          type: INT
          range: "{{Param.FramesPerTask}}-{{Param.FrameEnd}}:{{Param.FramesPerTask}},{{Param.FrameEnd}}"
      combination: "(RangeStart,RangeEnd)"

This is pretty generic and can be used for a variety of inputs. The alternative is to programmatically generate the template instead and use an array of strings for the frame ranges ("1-10", "11-20", ... and so on), but that is not a great experience and requires that the template be uniquely generated for each input.

This way of using range expressions is not currently supported by the implementation in this library; though the specification allows it.

Proposed Solution

The limitation originates here. This initial implementation accepted a simplistic overlap check for the ranges just to get something working, but it can be enhanced. The main constraint is that the solution cannot be linear time in the number of elements of a range.

For example, the following is perfectly valid input and would result in a potential denial of service if validated naively by generating the sets of values for each component of the range and checking for overlap:

range: "-99999999999999 - 99999999999999:2,-99999999999998 - 99999999999999:2"

So, the solution needs to be closed form. After a little bit of digging, the solution seems to be related to solutions of Linear Diophantine equations (math stackexchange refs: here, and here).

Basically, denoting a range by the triple $(s,e,t)$ with $s$ being the starting value of the range, $e$ the ending value of the range, and $t$ the step; $s$, $e$, and $t$ all integers. The values in the range are:

$$\{s\}\cup\{s+mt: m\in\mathbb{Z}^+, s+mt\leq e\textrm{ if }t>0, s+mt\geq e\textrm{ if }t<0\}$$

We have two ranges, that we'll denote by $(s_1, e_1, t_1)$ and $(s_2, e_2, t_2)$ and the problem is to determine whether there are integer values of $0&lt; i&lt; \lfloor \frac{e_1-s_1}{t_1} \rfloor$ and $0&lt; j&lt; \lfloor \frac{e_2-s_2}{t_2} \rfloor$ such that

$$s_1 + i t_1 = s2 + j t_2$$

which is equivalent to determining the lattice points of the line on the $(i,j)$ plane:

$$t_1 i + (-t_2) j + (s_1 - s_2) = 0$$

If any such $i$ and $j$ exist (we don't care what they are, just that they exist) then the ranges define at least some of the same values and the validation check should return an error.

Notes:

• Python has a gcd function: math.gcd()
• The multiplicative inverse of $n (mod m)$ can be calculated in Python as pow(n, -1, m)