Dale,
A very interesting analysis.
A lot of this hinges on what it means to "process" or "handle" a part.
In the case of parts that are not "by-reference" I suppose the meaning
of handling the part should be included in the definition of the
content-disposition. (This is currently better for some dispositions
than others. Its really weak for "render".)
And "by-reference" isn't really different - it needs to define what
handling means for it too. We need to sharpen that up. And how we do
that impacts your analysis.
Specifically, if we define "by-reference" to mean that processing it is
just a matter of making it accessible to be processed by a reference
then things are ok. In that case it is ok if a reference to it is never
processed. The only failure is if a reference containing a cid: is
processed and the referent can't be found because it or some container
of it was not processed.
Does that help?
Paul
[EMAIL PROTECTED] wrote:
> From: Paul Kyzivat <[EMAIL PROTECTED]>
>
> Can you explain more about how you reached this conclusion?
>
> It started when I was thinking that what this draft needs (IMHO) is to
> have a statement of "what the rules are", that is, the rules for
> interpreting or deciding whether to accept a body, with all the rules
> written in one place, so we can stare at them and see if anything is
> missing. (So far, we've been writing text to explain ambiguous points
> in the previous texts, but a textual structure like that makes it hard
> to see if you've really covered all the cases.)
>
> I then started to outline in my head how I would organize such a
> statement:
> defaulting rules for Content-Disposition
> scoping and validity of 'cid'
> assumptions about accepting and processing non-multipart types
> accepting and processing rules for each multipart type
>
> At that point, I noticed that there could be interdependencies between
> accepting one part and accepting another part. That is usually the
> signal that the problem in question is NP-complete. (In practice,
> meaning that deciding what to do could take an amount of time which is
> the exponential of the number of body parts to be considered, and that
> the decision algorithm requires backtracking.)
>
> So I then attempted to prove that the problem was NP-complete by the
> process of reducing the problem "3-satisfiability" to the problem of
> determining if a body is acceptable. And it turns out that is fairly
> simple.
>
> In order to make this construction work, I needed to assume the
> following features of our body-part scheme, all of which seem to be
> accepted as requirements:
>
> If all parts of a multipart/mixed are marked handling=required,
> then the body can be processed only if all the parts can be
> processed.
>
> A multipart/alternative with 2 parts can be processed if either
> part can be processed, and one part must be chosen for processing,
> leaving the other part un-processed.
>
> A part can contain 'cid' URLs, which cause the referenced parts to
> be processed.
>
> A part marked "Content-Disposition: by-reference; handling=required"
> can only be processed if a previous component referencing it via a
> 'cid' URL is processed.
>
> What makes this situation problematic is not that deciding whether and
> how to process a complex body make take exponential time (since that
> will generally happen only in pathological cases), but rather that
> most straightforward algorithms for making the decision will have to
> implement backtracking (which will sometimes be required even in
> non-pathological cases).
>
> (Here beginneth the technical part.)
>
> The reduction is as follows:
>
> http://en.wikipedia.org/wiki/NP-complete
> http://en.wikipedia.org/wiki/Reduction_%28complexity%29
> http://en.wikipedia.org/wiki/3-satisfiability#3-satisfiability
>
> Choose an instance of the 3-satisfiability problem, that is: a set of
> boolean variables A, B, C, etc. and a formula composed of:
> a series of "clauses" joined by AND, consisting of
> a series of variables and their negations joined by OR.
> The problem is to determine if there is any assignment of truth values
> to the variables which makes the formula true, that is, which makes
> true one of the variables or negations in each of the clauses.
>
> For example, choose 4 variables A, B, C, and D, and the formula
>
> (A OR B OR C) AND (B OR NOT-C OR D) AND (NOT-A OR NOT-B OR NOT-D)
>
> This can be satisfied by setting A=TRUE, B=FALSE, C=TRUE, and D=FALSE.
>
> Construct a multipart/mixed with each component labeled
> handling=required. Within that, for each variable, have a part which
> is multipart/alternate with 2 parts. If processing chooses the first
> part of the part corresponding to a variable, that will model the
> variable being TRUE. If processing chooses the second part of the
> part corresponding to a variable, that will model the variable being
> FALSE.
>
> For example, our body starts:
>
> multipart/mixed
> multipart/alternative;handling=required
> first part corresponding to A (not yet specified)
> second part corresponding to NOT-A
> multipart/alternative;handling=required
> first part corresponding to B
> second part corresponding to NOT-B
> multipart/alternative;handling=required
> first part corresponding to C
> second part corresponding to NOT-C
> multipart/alternative;handling=required
> first part corresponding to D
> second part corresponding to NOT-D
>
> For each clause of the formula, add an additional body part, marked
> "Content-Disposition: by-reference; handling=required". Give the part
> a 'cid' URL. The ability of the recipient to successfully process
> this part will model making the corresponding clause TRUE.
>
> For example, our body is now:
>
> multipart/mixed
> multipart/alternative;handling=required
> first part corresponding to A (not yet specified)
> second part corresponding to NOT-A
> multipart/alternative;handling=required
> first part corresponding to B
> second part corresponding to NOT-B
> multipart/alternative;handling=required
> first part corresponding to C
> second part corresponding to NOT-C
> multipart/alternative;handling=required
> first part corresponding to D
> second part corresponding to NOT-D
> part (not otherwise
> specified);by-reference;handling=required;cid=clause1
> part (not otherwise
> specified);by-reference;handling=required;cid=clause2
> part (not otherwise
> specified);by-reference;handling=required;cid=clause3
>
> We now want to arrange things so that one of the last 3 parts can be
> successfully processed only if we choose for processing one of the
> earlier parts that corresponds to a variable value that will make the
> corresponding clause true. This is done by embedding forward
> references in the variable-corresponding parts that refer to the
> clause-corresponding parts.
>
> For example:
>
> multipart/mixed
> multipart/alternative;handling=required
> first part corresponding to A
> references cid:clause1
> second part corresponding to NOT-A
> references cid:clause3
> multipart/alternative;handling=required
> first part corresponding to B
> references cid:clause1
> references cid:clause2
> second part corresponding to NOT-B
> references cid:clause3
> multipart/alternative;handling=required
> first part corresponding to C
> references cid:clause1
> second part corresponding to NOT-C
> references cid:clause2
> multipart/alternative;handling=required
> first part corresponding to D
> references cid:clause2
> second part corresponding to NOT-D
> references cid:clause3
> part;by-reference;handling=required;cid=clause1
> part;by-reference;handling=required;cid=clause2
> part;by-reference;handling=required;cid=clause3
>
> In order to process this body, the recipient must choose exactly one
> of each pair of bodies in the multipart/alternative body parts. This
> choice is equivalent to choosing a set of values for the variables.
> The references embedded in the chosen parts refer to the body parts
> that correspond to the clauses which are made true by the
> corresponding variable's value. In order to successfully process the
> final body parts, the recipient must have chosen a set of variable
> values that makes all of the clauses true.
>
> Dale
> _______________________________________________
> Sip mailing list https://www.ietf.org/mailman/listinfo/sip
> This list is for NEW development of the core SIP Protocol
> Use [EMAIL PROTECTED] for questions on current sip
> Use [EMAIL PROTECTED] for new developments on the application of sip
>
_______________________________________________
Sip mailing list https://www.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [EMAIL PROTECTED] for questions on current sip
Use [EMAIL PROTECTED] for new developments on the application of sip
