Repository: opencv
Issue: G-API feature proposal: endless loops detection for GAPI_TRANSFORM-related logic
Labels: RFC,category: g-api / gapi

### Introduction

Recently I have been thinking about endless loops detection logic in `GCompiler` with regards to introduced graph transformations support. I have come up with an idea how we should be able to detect all (?) sorts of endless loops at the time of `GCompiler` constructor call by applying somewhat standard ideas.
I suggest this issue to be a discussion point for my idea where we could also share general thoughts on this feature's design.

related to #15313

**Disclaimer**: This is more of a feature request/design proposal for existing functionality rather than a bug or anything of the kind. Not finding any better place to discuss the idea, I decided to create this issue

### Problem statement

Having transformation logic in G-API graphs can introduce potential problem of looping endlessly applying graph transformations defined with `GAPI_TRANSFORM`: mainly, due to the fact that some transformations can "recurse" into each other.

Simple example:
```cpp
GAPI_TRANSFORM(EndlessLoopTransform, <cv::GMat(cv::GMat)>, "pattern in substitute")
{
    static cv::GMat pattern(const cv::GMat& in)
    {
        return cv::gapi::resize(in, cv::Size(100, 100), 0, 0, cv::INTER_LINEAR);
    }

    static cv::GMat substitute(const cv::GMat& in)
    {
        cv::GMat b, g, r;
        std::tie(b, g, r) = cv::gapi::split3(in);
        auto resize = std::bind(&cv::gapi::resize,
            std::placeholders::_1, cv::Size(100, 100), 0, 0, cv::INTER_LINEAR);
        cv::GMat out = cv::gapi::merge3(resize(b), resize(g), resize(r));
        return out;
    }
};
```
Needless to say, in the presence of the example transformation, applying transformations for "as long as it is possible" can cause us serious troubles. The problem is, however, that there are more complex, non-straightforward transformation dependencies that can cause similar issues but are much harder to detect.

### Solution

In this section potential solution (algorithm) is proposed to address the problem stated.

#### Idea
Looking at patterns and substitutes and how they're handled within `GCompiler` reminds me of function calls:
- Imagine the following: compiler finds pattern `p_1` in original graph and substitutes it with `s_1`.  Now, on the next iteration, pattern `p_2` is discovered being a part of newly substituted piece `s_1`
- In a sense, we can symbolically write this logic as `p_1 => s_1 => p_2 => s_2 => ...` sequence
- We don't really need to know about substitutes (`s_1`, `s_2`), but we do want to know about `p_1` and `p_2` and how they relate to each other. If the relation exists (as shown above), let's say that `p_1` "calls" `p_2`: so we end up having `p_1 => p_2 => ...` sequence
- For each pattern `p_i` within transformation `t_i`, we would love to know which patterns { `p_j` | `j = 0,...,transforms_num` } are "called" by `p_i` directly
- Well, now this resembles a concept of a call graph
- **It seems that finding loops in a call graph of `p_i` would automatically find loops in transformations with regards to `t_i`**

#### Algorithm

Input: array of transformations (with patterns and substitutes), length N
Output: exception throw/return "false" if loop detected, nothing/return "true" otherwise

```
// 1. Call graph construction phase
call_graph - map<pattern*, vector<pattern*>>;
* - pattern is uniquely identified by an _index_ in an array of transformations,
    so we can simply use indices instead of actual patterns as key/values for call_graph

for (i in transformations)
  create new call_graph element: {pattern_i, {}}

  for (j in transformations)
    if (pattern_j is found in substitute_i)
      add new entry: call_graph[pattern_i].add(pattern_j)

// 2. Searching for loops
// we now have at most N graph components
for (i in range(0, N))
  traverse the graph starting from call_graph[i]:
    call_graph[i].key - "parent" node
    call_graph[i].value - "child" nodes
    at each iteration remember visited node
    __if "children" contain visited node, we have found a loop__
```

### Concerns

- The algorithm is really a draft, I think it should work in principle but it might have some hidden flaws. Also it seems reasonable to think about some optimizations along to reduce the number of overall iterations
- Unsure if all possible loops are covered by such approach but it feels like that
- There were some concerns about __the order__ of how transformations are applied. Unfortunately, I do not remember the details, but I think that anything concerning the order might be addressed at phase 1 - "call graph construction"