[FFmpeg-devel] [RFC] AVFilter Parser

[vmrsss]

Hello. I've tried to interpret all that was said in the past few days,  
and would like to make a proposal to pull it all together. This is  
essentially what Vitor said in his last email, somehow simplified,  
plus a hopefully cleaner treatment of feedback.

==1==

I am using the following syntactic elements because I find them  
intuitive, but there is nothing special about them, just a matter of  
taste:

  - comma (,) for sequential composition --
	F,G implies #outstream(F) = #instream(G)

  - star (*) for parallel composition --
	#instream(F*G) = #instreams(F) + #instream(G)
	#outstream(F*G) = #outstreams(F) + #outstream(G)

  - input naming ( ... )
  notice this is a scoping operator, (x)F names x inaccessible outside F

  - output naming  < .... >

  - feedback naming [ ... ]
	notice this is a scoping operator, [x]F names x inaccessible outside F

  - a dummy name _

==2==

In general a filter is described by a signature

	filter{par_1,...,par_k} : n ---> k

that is, its parameters (note I am using curly brackets just not to  
confuse parameters and streams), its number of input streams n, its  
number of output streams k. (Typically n and k can be easily inferred  
by looking at the code, but it's not a big pain to ask the user to  
declare them when writing a user-defined filter.)

Examples:

	crop{w,h,x,y} : 1 --->1
	picInPic{} : 2 ---> 1
	rotate{angle} : 1 ---> 1
	movie{file} : 0 ---> 1


==3==

Here are the four main syntactic categories.

OUTPUT_STREAM ::= < id_1,...,id_k >
	sequence can be empty, < x > * < y > be to read as < x y >

ATOMIC_STREAM ::= all the streams in avfilter, eg crop, vflip,  
scale, ...

USER_DEFINED ::= filter_id{par_1,...,par_k} : n ---> k = FILTER

FILTER ::=
	OUTPUT_STREAM
	ATOMIC_STREAM=val_1,...,val_k	(k = # of parameters of filter)
	USER_DEFINED=val_1,...,val_k 	(k = # of parameters of filter)
	FILTER * FILTER					(as discussed above)
	FILTER, FILTER					(as discussed above)
	(id_1 ... id_k) FILTER
	FILTER [bind_1 ... bind_k]	(bind is either the dummy id _ or a proper  
id))


==4==

Let me now give a few examples to explain the elementary constructs;  
(in fact, the only thing which is slightly different is feedback).

	copy{} = (x)< x >
	split{} = (x)< x x >
	swap{} = (x y)< y x >
	drop{} = (x) < >

	myfilter(angle): 1 ---> 1 =	
		case angle of 90 --> transpose,vflip
					180 --> hflip,vflip
					270 --> vflip,transpose
					else --> rotate_slow=angle


Something slightly more complex:

	filter(): 3 ---> 1 = (a b c) < a b >, picInPic, (t) < t c >, picInPic

where:
	(a b c) names the three inputs of the filter
	< a b > outputs to of them to go straight to picInPit
	(t) names to output of picInPic
	< t c > feeds the final picInPic stage

Note that fully parenthesised this would be:

	(a b c)  ( < a b >, picInPic , (t) (< t c >, picInPic) )

(comma is associative, so parenthesis don't matter there -- I find  
using a comma after < > clumsy though)

Notice that if you don't need to name streams for special treatment,  
you're not required to do it: all simple filter chains can be written  
just as "...,crop=...,scale=...," and so can also a number of more  
complex ones -- as long as they don't require feedback.


==5==

Time for well-formedness rules relative to naming:

(1) all ids in a well-formed filter are bound by either ( ) or [ ]
	this guarantees that a filter has got no visible names, which
	may interfere with other names unintentionally; it is however
	possible to use input/output/feedback naming to use the filter
	not trivially even if one only knows its n ---> k type.

(2) ids appear at most once in a single (...)
	this avoids non-sense like < a b >, (x x)F

(3) the number of names in input (resp output) naming determines
	n (resp k) in the type n ---> k of a filter.

There might be still something missing here, but these are the  
important ones.


==6==

Finally, we come to feedback. The treatment is similar to the one  
proposed by Michael and Vitor, the only difference is that the  
[ .... ] is a scoping operator that at the same time feedbacks output  
to inputs and the same time puts the names out of scope, while keeping  
input/output and feedback mechanisms entirely separated. The basic  
mechanism is as follows.

Let F be a filter 2 ---> 2 and suppose I want to feed its outputs back  
to its inputs. Firstly, I can name F's inputs use the form:

	G = < a b >, F  	(which is 0 --> 2)

Then G [ a b ] says: name a and b the 1st (resp 2nd) output of G to  
the a input named a (resp b). To swap the outputs (ie crop the wires)  
I would write G [ b a ]. Now G [a b] is crap (eg because it's got no  
input nor output), one would like to feedback only some of the outputs  
to some of the inputs. That is where one might use a dummy variable _,  
which is a passthrough sort of mechanism.

  	< a b > F [  _ a ] : 2nd output to 1st input, 1st output pass  
through as filter's output
  	< a b > F [  _ b ] : 2nd output to 2nd input, 1st output pass  
through as filter's output
	< a b > F [  a _ ] : 1st output to 1st input, 2nd output pass through  
as filter's output
	... etc

Importantly, [  _ a ] makes a vanish from output and input (it becomes  
a loop, with no specific name) so that it is no more accessible from  
outside. Note that is very important, as any further access to the  
loop would be wrong. So, the final term that takes F and feeds back  
its 2nd output to its 1st input would be

   	(x) (< A x > F [  _ A ] ) : 1 ---> 1

which says: name x the only input, feed it to F's 2nd input,  
temporarily name A its 1st input, pass through the 1st output and  
feedback the 2nd to A as indicated by the feedback naming [  _ A ].

To conclude, we need to constrain the occurrence of names in F  
[ ... ]. This requires some thinking as to the best way to express it,  
but essentially F must be of the form < ... > F' and: there must be as  
many names in [ ... ] as in < ... >, they must all be distinct, and  
actually appear exactly once in < ... >. The type of < ... >  
F' [ ... ] is n ---> k, where n is

==7==

A few examples with feedback:

These were proposed my Michael:

> 2<X 0<L Filter0 L<0 2>Y ; Y>0 2<L Filter1 L<2 X<0
>
>   _________
>  /         \
>  \          |
>>       /
> ---> Filter0 --->
>>       \
>  /          |
>  \____  ___/
>       \/
>   ____/\___
>  /         \
>  \          |
>>       /
> ---> Filter1 --->
>>       \
>  /          |
>  \_________/
>

(x y ) (< a x b > Filter0 * < c y d > Filter1) [ a _ c b _ d ]

the same as

( x y ) < a x b c y d > (Filter0 * Filter1) [ a _ c b _ d ]

>
> --> picInPic -> split--> split --> scale --> picInPic -->
>                 \        \            >
> /                     \        \_________/
> \_____________________/

> 1<T picInPic, split T<1, split 1>T, scale, T>1 picInPic

(If I still understand the picture)

	 (x) (  < x a > (picInPic, split)[ _ a ],  split, (u v) <u> scale,  
(t) < t v > picInPic



==8==

As a final remark, there are might be more opportunities to introduce  
notational conventions eg involving  _. For instance, the form  
(t ... ) < t ... > will occur many times, where t doesn't really  
matter, it's just continuation-passing. So one might instead write  
( _ ... ) < _ ... >. For instance the previous example would be:

	 (x) (  < x a > (picInPic, split)[ _ a ],  split,  ( _ v) < _ >  
scale, ( _ ) < _ v > picInPic

Also, one could introduce an operator >> which by default passes the  
first output as the first input of the following filter, as suggested  
by Vitor too. Then you'd write:

	 (x) (  < x a > (picInPic, split)[ _ a ],  split  >>  (v) scale  >>   
< v > picInPic

which I'd say looks solid and smooth enough.

Regards to all.
-vmrss