[FFmpeg-devel] [PATCH] [2/??] [3/3] Filter graphs - Parser for a graph description

[vmrsss]

Hello.

On 18 Mar 2008, at 22:18, Robert Swain wrote:
> I like your syntax and prefer it to Vitor's. I have a query about the
> second of these two examples. I assume that in the first, the input to
> filter1 and output of filter2 are individually not named and you've
> just chosen to suggest names for the output of filter1 and the input
> of filter2. That is...
>
>       ---> filter1 ---> (abc)
> (def) ---> filter2 --->
>
> The point being that with your syntax, the names of the buffers are
> irrelevant because they are intrinsically numbered and syntax is
> adjusted to match the order of the input/output streams.

Yes, exactly. That is the basic model on top of which one would  
normally use convenient abbreviations. (A common approach is to forget  
nop and swap and simply use one of the several notations for  
permutations.)

What perhaps I did not make clear enough is that the key point here is  
not the numbers, but is to keep streams unambiguously distinct when  
you compose filters. If I use implicit naming of streams by numbering,  
then I can't possibly get it wrong:

	if F : n ---> k (meaning a filter with inputs n streams, outputs k  
streams)
	and G : m ---> h, then F * G : n+m ---> k+h,
	the first n inputs fed to F, the remaining m to G.

The same effect can however be achieved using explicit names x, y,  
z... (instead of implicit numbers), with just a bit of attention:

	if F = (x)some filter(z) : 1 ---> 1 and G = (x)some other filter(z) :  
1 ---> 1,
	then F * G : 2 ---> 2, that is the x's and z's are implicitly separated

If one wants the x's to be the same will have to write explicitly  
"split, F*G", which is 1 ---> 2.

[[Notice that if on the other hand you make the design choice to  
equate the x's, that yields a very different model where you would  
have at least to: (1) provide a mechanism to make the two x's  
distinct;  (2) clarify what happens with z (the outputs of F and G  
will differ, you can't just pretend they coincide...) ]]

Under this assumption, whether you use indices or explicit names is  
very much a matter of taste, they all mean the same. (Very much like  
the definitions "h x = let y = f x in g y", "h x = g (f x)", and "h =  
g.f" give rise to exactly the same code for h in a language like, say,  
Haskell).

> The diagram for the second of the two examples might be clearer if it
> were drawn as follows:
>
>       ---> filter1 ---> (abc)
>               |
>               v
> (def) ---> filter2 --->
>
> I prefer this because the inputs are on the left and the outputs on
> the right. Please note, however, that the output of filter1 to (abc)
> would be filter1's second output looking at your diagram. The first
> output of filter1 goes to filter2 in your diagram.

Ok, let's assume that.

> We have two input streams, the input of filter1 and (def). The inputs
> of filter2 come from filter1 (or the first output of split in your
> notation) and from (def). In what order are these fed into filter2? Is
> the 'spare' input that isn't used by filter1 to be kept in a list of
> remaining input possibilities and later used by the next filter that
> doesn't have enough inputs coming from other filters in the chain?
> What takes priority - the inputs from the chain or the initial inputs
> to the graph? Is this just a case that really needs some named inputs?

Probably the easiest way to look at this is to compose blocks F, G,  
H, ... where each of the blocks is build using * so as the number of  
inputs and outputs matches at each stage. The pairing is then  
straightforward: 1st output from a block is 1st input for the  
successive block, 2nd output from a block is 2nd input for the  
successive block, etc. For instance in the case above:

    - start with F = filter1,split : 1 ---> 2 and G = filter2 : 2 --->  
1;
	then the final filter is (F * nop) , (nop * G) : 2 ---> 2.
	This is because:

    - the 2nd input (def) passes the first block untouched to be fed  
to G;
	you can do that by writing F*nop : 2 ---> 3

    - now the 1st output of F passes the second block untouched to be
	output. you can write that as nop*G : 3 ---> 2.

If for instance you want the output from filter1 to be the 2nd (rather  
than the 1st) input to filter2 you could simply replace G by  G' =  
swap,filter2. And so on: after each block, you'd rearrange your  
streams as required (but don't forget this is a rich algebra, there  
are very many equivalent ways to express the same form, some simpler,  
some harder).

For completeness, in the notation proposed later on by Michael to  
express (filter1, split)*nop , nop*filter2 you'd write something like:

	(x def)Filter =
		(x) filter1, split (k1 k2) , (k2 def) filter2

but I think here you'd still need to clarify the order of Filter's  
outputs (does the first output of Filter comes from filter1 or from  
filter2?) or you'll soon be in trouble, so perhaps his proposal should  
be refined into something like

	(x def) Filter (o1 o2) =
		(x) filter1,split (o1 k) , (k def) filter2(o2)

or perhaps

	Filter(x def) =
		let (o1 k) = ( filter1,split )(x)
			in let o2 = filter2(k def)
				in (o1 o2)

Hope this helps.
-vmrsss