RFC 2533
A Syntax for Describing Media Feature Sets
RFC 2533: A Syntax for Describing Media Feature Sets 💖
- RFC number: 2533
- Title: A Syntax for Describing Media Feature Sets
- Stream: Network Working Group
- Author: G. Klyne, from Content Technologies/5GM 🎀
- Category: Standards Track ✨
- Date: March 1999
- Obsoletes / Updates: the header doesn't list any obsoletes or updates 🙈
Status of this Memo ✨
Okay so this one is an Internet standards track protocol for the Internet community, and it wants discussion and suggestions for improvements 💅 Bestie, check the current edition of the "Internet Official Protocol Standards" (STD 1) for the official standardization state and status. And distribution of this memo is unlimited, so share it everywhere 🦋
Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved. 🔒
Abstract
Lots of Internet application protocols need content negotiation for the resources they interact with [1] 🌸 A framework for that negotiation is described in [2], and part of it is a way to describe the range of media features that a sender, a recipient, or a document transmission format can handle. A format for a vocabulary of individual media features, plus the procedures for registering features, is presented in [3] 📚
This document introduces a syntax for defining feature sets, which are formed from combinations and relations involving individual media features. These feature sets describe the media feature handling capabilities of message senders, recipients, and file formats. It's giving organized 💜
An algorithm for feature set matching is also described here ✨
Table of Contents
1. Introduction.............................................3
1.1 Structure of this document ...........................3
1.2 Document terminology and conventions .................4
1.3 Discussion of this document ..........................4
2. Content feature terminology and definitions..............4
3. Media feature combinations and capabilities..............5
3.1 Media features .......................................5
3.2 Media feature collections and sets ...................5
3.3 Media feature set descriptions .......................6
3.4 Media feature combination scenario ...................7
3.4.1 Data resource options............................7
3.4.2 Recipient capabilities...........................7
3.4.3 Combined options.................................7
3.5 Feature set predicates ...............................8
3.5.1 Comparison with directory search filters.........8
3.6 Describing preferences ...............................9
3.7 Combining preferences ...............................10
4. Feature set representation..............................11
4.1 Textual representation of predicates ................11
4.2 Interpretation of feature predicate syntax ..........12
4.2.1 Filter syntax...................................12
4.2.2 Feature comparison..............................13
4.2.3 Feature tags....................................13
4.2.4 Feature values..................................14
4.2.4.1 Boolean values 14
4.2.4.2 Numeric values 14
4.2.4.3 Token values 15
4.2.4.4 String values 15
4.2.5 Notational conveniences.........................15
4.3 Feature set definition example ......................16
5. Matching feature sets...................................16
5.1 Feature set matching strategy .......................18
5.2 Formulating the goal predicate ......................19
5.3 Replace set expressions .............................19
5.4 Move logical negations inwards ......................20
5.5 Replace comparisons and logical negations ...........20
5.6 Conversion to canonical form ........................21
5.7 Grouping of feature predicates ......................22
5.8 Merge single-feature constraints ....................22
5.8.1 Rules for simplifying ordered values............23
5.8.2 Rules for simplifying unordered values..........23
6. Other features and issues...............................24
6.1 Named and auxiliary predicates ......................24
6.1.1 Defining a named predicate......................24
6.1.2 Invoking named predicates.......................25
6.1.3 Auxiliary predicates in a filter................25
6.1.4 Feature matching with named predicates..........25
6.1.5 Example.........................................26
6.2 Unit designations ...................................26
6.3 Unknown feature value data types ....................27
7. Examples and additional comments........................27
7.1 Worked example ......................................27
7.2 A note on feature tag scoping .......................31
8. Security Considerations.................................34
9. Acknowledgements........................................34
10. References.............................................35
11. Author's Address.......................................36
Full Copyright Statement...................................371. Introduction 🌷
Okay so, lots of Internet application protocols need content negotiation for the resources they interact with [1]. A framework for that negotiation is described in [2]. Part of this framework is a way to describe the range of media features that can be handled by the sender, the recipient, or the document transmission format of a message 💖
Descriptions of media feature capabilities need to be based on an underlying vocabulary of individual media features. A format for that vocabulary, and the procedures for registering media features within it, are presented in [3] 📚
This document defines a syntax for describing feature sets, which are formed from combinations and relations involving individual media features. These feature sets describe the media handling capabilities of message senders, recipients, and file formats 🦋
An algorithm for feature set matching is also described here ✨
The feature set syntax is built on the idea of using feature set predicates as "mathematical relations" that define constraints on feature handling capabilities. That means one form of feature set expression can describe sender, receiver, and file format capabilities alike 👑 This is loosely modelled on the way relational databases use Boolean expressions to describe a set of result values, and it's based on LDAP search filters too 🧚
1.1 Structure of this document
The main part of this memo covers these main areas:
Section 2 introduces and references some terms that have a special meaning 🎀
Section 3 introduces the idea of describing media handling capabilities as combinations of possible media features, and the idea of using Boolean expressions to express those combinations 💅
Section 4 describes a syntax for describing feature sets, based on the Boolean expression idea introduced in Section 3 🌈
Section 5 describes an algorithm for feature set matching 🔥
Section 6 covers some additional media feature description and processing issues that can be seen as extensions to the core framework 🫶
Section 7 has a worked example of feature set matching, plus some extra explanatory comments that came out of applying this framework to facsimile transmissions 📠
1.2 Document terminology and conventions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. Those are the official vibes, so take them seriously 💀
NOTE: Comments like this provide additional nonessential information about the rationale behind this document. Such information is not needed for building a conformant implementation, but may help those who wish to understand the design in greater depth. 🧠
1.3 Discussion of this document
Discussion of this document should happen on the content negotiation and media feature registration mailing list, hosted by the Internet Mail Consortium (IMC) 💌
Send comments about this document to:
ietf-medfree@imc.orgTo subscribe to the list, send a message with the body subscribe to:
ietf-medfree-request@imc.orgTo see what went on before you joined, check the mailing list archive at:
http://www.imc.org/ietf-medfree/2. Content feature terminology and definitions 🍓
Here are some terms with special meanings in this memo 📖
Feature Collection is a collection of different media features and their associated values. You can think of it as describing one specific rendering of one specific instance of a document or resource, by one specific recipient 🎀
Feature Set is a set of zero, one, or more feature collections. ✨
NOTE: This term is used slightly differently by earlier work on Transparent Content Negotiation in HTTP [4]. 🙈
Feature set predicate is a function of an arbitrary feature collection value that returns a Boolean result. A TRUE result means that the corresponding feature collection belongs to some set of media feature handling capabilities defined by this predicate 💜
Other terms used in this memo are defined in [2] 📚
3. Media feature combinations and capabilities 🦋
3.1 Media features
This memo assumes that individual media feature values are simple atomic values 🌸
- Boolean values.
- Enumerated values.
- Text string values (treated as atomic entities, like enumerated value tokens).
- Numeric values (Integer or rational).
These values all have the property that they can be compared for equality (=), and numeric and ordered enumeration values can be compared for less-than and greater-than relationships (<=, >=). These basic comparison operations are the primitive building blocks for more comprehensive capability expressions 🧩
3.2 Media feature collections and sets
Any single media feature value can be thought of as just one component of a feature collection. That feature collection describes some instance of a resource, like a printed document or a displayed image 🖨️ A feature collection is made up of a number of media feature tags (each per [3]) and their associated feature values 🏷️
A feature set is a set containing a number of feature collections, so a feature set can describe a bunch of different data resource instances 💖 These can be different treatments of a single data resource (like different resolutions used for printing one document), a number of different data resources getting a common treatment (like the range of images that can be rendered on one display), or some combination of those. Examples are below 🌈
So a description of a feature set can describe the capabilities of a data resource, or of some entity that processes or renders a data resource 👑
Part 1 of 7 is done, bestie! Part 2 picks up with Section 3.3 next 🦋✨
3.3 Media feature set descriptions ✨
okay so a feature set can be unbounded 🌌 like, in theory there's no limit on how many different documents a printer could spit out. but to be actually useful, a feature set description has to be finite 💅
the vibe here is "start with anything is possible" 🦋 so the feature set starts out containing every possible document instance (feature collection). then you slap on constraints that kick instances out one by one. for a monochrome printer, every document that uses colour gets removed 🖤. for a document that has to be rendered at some minimum resolution, every lower-resolution instance gets tossed 📉. the tool doing the kicking is the math idea of a "relation" 🧠, aka a Boolean function (a "predicate") that takes a feature collection and returns TRUE if it describes an acceptable document instance, or FALSE if it's excluded 🚫
P(C)
P(C) = TRUE <- : -> P(C) = FALSE
:
+----------:----------+ This box represents some
| : | set of feature collections (C)
| Included : Excluded | that is constrained by the
| : | predicate P.
+----------:----------+
:so when you stack a bunch of these constraints, you end up with a smaller set of feature collections that shows what a media handling capability looks like 🎀. when each constraint is its own predicate describing some capability, the combined result is a subset of those individual capabilities, and it can be written as a predicate that's the logical-AND of all the individual constraint predicates 🔗 literally just "all of these must be true" energy 💜
3.4 Media feature combination scenario 🎬
this section is where we play with some example scenarios and get comfy with the notation. the formal version shows up in section 4 🫶
3.4.1 Data resource options 🖼️
this expression describes a data resource that can be displayed either:
- (a) as a 750x500 pixel image using 15 colours, or
- (b) at 150dpi on an A4 page.
(| (& (pix-x=750) (pix-y=500) (color=15) )
(& (dpi>=150) (papersize=iso-A4) ) )3.4.2 Recipient capabilities 🖥️
this expression describes a receiving system that has:
- (a) a screen that can show 640*480 pixels and 16 million colours (24 bits per pixel), 800*600 pixels and 64 thousand colours (16 bits per pixel), or 1024*768 pixels and 256 colours (8 bits per pixel), or
- (b) a printer that can render 300dpi on A4 paper. 🖨️
(| (& (| (& (pix-x<=640) (pix-y<=480) (color<=16777216) )
(& (pix-x<=800) (pix-y<=600) (color<=65535) )
(& (pix-x<=1024) (pix-y<=768) (color<=256) ) )
(ua-media=screen) )
(& (dpi=300)
(ua-media=stationery) (papersize=iso-A4) ) )ngl this expression says nothing about the colour or grey-scale capabilities of the printer 🙈 the scheme just presumes it's unconstrained in that respect. or, more realistically, any such constraints get handled out-of-band by whoever is sending to this recipient 📨
3.4.3 Combined options 🧩
this one shows the range of document representations you get when the resource from the first example gets sent to the recipient from the second example. it's the result of combining their capability feature sets 💖
(| (& (pix-x=750) (pix-y=500) (color=15) )
(& (dpi=300) (ua-media=stationery) (papersize=iso-A4) ) )the feature set described by this expression is the intersection of the sets described by the previous two capability expressions. main character crossover 👑
3.5 Feature set predicates 🔮
there are lots of ways to represent a predicate 🫧 the ideas in this memo were inspired by the programming language Prolog [5], and its use of predicates to describe sets of objects.
for media feature descriptions in networked application protocols, the format used for LDAP search filters [7,8] got adopted. it's a really good match for what capability identification needs, and it has a super simple structure that's easy to parse and process ✨
3.5.1 Comparison with directory search filters 📂
okay so a feature collection is basically like a directory entry 🗂️ they both consist of a collection of named values. and the way a feature set gets used to select feature collections is kinda similar to how directory entries get selected from a directory 🫶
a feature set predicate that describes media handling capabilities is implicitly applied to some feature collection. inside the predicate, members of the feature collection are identified by their feature tags and compared with known feature values. (compare that with how an LDAP search filter gets applied to a directory entry, where members are identified by attribute type names and compared with known attribute values 💅)
for example, in:
(& (dpi>=150) (papersize=iso-A4) )the tokens 'dpi' and 'papersize' are feature tags 🏷️, and '150' and 'iso-A4' are feature values. (in a matching LDAP search filter, those would be directory entry attribute types and attribute values.)
now, the differences between directory selection (per [7]) and feature set selection are:
- directory selection provides substring-, approximate- and extensible- matching for attribute values. feature set selection does not do that 🙅♀️
- directory selection can be based on the presence of an attribute without caring about its value. within the semantic framework described by this document, Boolean-valued feature tests can be used to get a similar effect ✨
- directory selection provides matching rules that test for the presence or absence of a named attribute type 🔍
- directory selection provides matching rules that depend on the declared data type of an attribute value 🧮
- feature selection provides for associating a quality value with a feature predicate, as a way of ranking the selected value collections 🏆
within the semantic framework described by this document, Boolean-valued feature tests can be used wherever presence tests would be used in a directory search filter. it's giving same energy 💜
the idea of extensible matching and matching rules that depend on data types are facets of a problem this memo doesn't address 🙃 but they don't necessarily affect the feature selection syntax. one thing that might bear on the syntax would be specifying an explicit matching rule as part of a selection expression 🔧
3.6 Describing preferences 💭
a convenient way to describe preferences is with numeric "quality values" 🌸
it's been suggested that numeric quality values can be misleading if you use them for more than just ranking options. for the purposes of this memo, ranking options is enough 🎯
numeric quality values in the range 0 to 1, with up to 3 fractional digits, get used to rank feature sets according to preference. higher values are preferred over lower values, and equal values are presumed to be equally preferred. beyond that, the actual number used has no significance defined here. arithmetic on quality values is likely to produce unpredictable results unless appropriate semantics have been defined for the context where those operations get used 🤷♀️
if no quality value is explicitly applied, a value of "1" is assumed 💯
using the notation defined later, you can attach a quality value to any feature set predicate sub-expression 🧁
(| (& (pix-x=750) (pix-y=500) (color=15) );q=0.8
(& (dpi>=150) (papersize=iso-A4) ) ;q=0.7 )section 3.7 below explains why quality values attached to sub-expressions aren't always useful 👀
NOTE: the syntax for quality values used here is taken from the one defined for HTTP 'Accept:' headers in RFC 2068 [9], section 3.9. however, the use of quality values defined here does not go as far as the one defined in RFC 2068. 🚧
3.7 Combining preferences 🤔
the general problem of describing and combining preferences among feature sets is wayyy more complex than just describing allowable feature sets 😭 for example, take these two feature sets:
(& (a1);q=0.8 (b1);q=0.7 )
(& (a2);q=0.5 (b2);q=0.9 )where: feature a1 is preferred over a2 feature b2 is preferred over b1
so which of these feature sets is preferred? 🫠 without additional information or assumptions, there's no generally satisfactory answer to that.
the proposed resolution is simply to say that no rules are provided for combining preference information. applied to the example above, any preference information about (a1) in relation to (a2), or (b1) in relation to (b2), is not presumed to convey information about the preference of (& (a1) (b1) ) in relation to (& (a2) (b2) ). no cap, that's the whole drama 🎭
in practical terms, this restricts the application of preference information to top-level predicate clauses. a top-level clause completely defines an allowable feature set, and clauses combined by logical-AND operators cannot be top-level clauses (see the canonical format for feature set predicates, described later) 🗝️
NOTE: This memo does not apply specific meaning to quality values or rules for combining them. applying such meanings and rules is not prohibited, but it's seen as an area for continuing research and experimentation 🔬
an example of a design that uses extended quality value semantics and combining operations is "Transparent Content Negotiation in HTTP" [4]. other work that also extends quality values is the content negotiation algorithm in the Apache HTTP server [14] 🌈
4. Feature set representation 🎀
the foregoing sections built a framework for defining feature sets with predicates applied to feature collections 🧱 this section is where we get into a concrete representation for feature set predicates. bestie, it's about to get real 🦋
4.1. Textual representation of predicates
okay so the text form of a feature set is based on RFC 2254 "The String Representation of LDAP Search Filters" [8] 💅 It leaves out the bits that don't matter for feature set selection (we talked about those above ✨) and adds new bits made for feature sets, like ways to attach quality values to predicates 🎀
A feature predicate is written using the filter production below. The notation and core rules come from RFC 2234 [10] 🦋
filter = "(" filtercomp ")" *( ";" parameter )
parameter = "q" "=" qvalue
/ ext-param "=" ext-value
qvalue = ( "0" [ "." 0*3DIGIT ] )
/ ( "1" [ "." 0*3("0") ] )
ext-param = ALPHA *( ALPHA / DIGIT / "-" )
ext-value = <parameter value, according to the named parameter>
filtercomp = and / or / not / item
and = "&" filterlist
or = "|" filterlist
not = "!" filter
filterlist = 1*filter
item = simple / set / ext-pred
set = attr "=" "[" setentry *( "," setentry ) "]"
setentry = value "/" range
range = value ".." value
simple = attr filtertype value
filtertype = equal / greater / less
equal = "="
greater = ">="
less = "<="
attr = ftag
value = fvalue
ftag = <Feature tag, as defined in RFC 2506 [3]>
fvalue = Boolean / number / token / string
Boolean = "TRUE" / "FALSE"
number = integer / rational
integer = [ "+" / "-" ] 1*DIGIT
rational = [ "+" / "-" ] 1*DIGIT "/" 1*DIGIT
token = ALPHA *( ALPHA / DIGIT / "-" )
string = DQUOTE *(%x20-21 / %x23-7E) DQUOTE
; quoted string of SP and VCHAR without DQUOTE
ext-pred = <Extension constraint predicate, not defined here>Depending on the protocol carrying the feature predicate, whitespace may appear between any pair of syntax elements or literals on the right-hand side of these productions 🫶
The syntax lets parameters (quality values included) sit on any filter in the predicate, not just the top-level ones 🧚 But only top-level quality values are recognized 👀 If there's no explicit quality value, 1.0 is applied 💜
NOTE: The flexible approach to quality values and other parameter values was picked for two reasons 💖 First, so separately built feature predicates are easy to combine. Second, so there's an extensible tagging mechanism for future use, like a possible future need to explicitly specify a matching rule 🔥
4.2. Interpretation of feature predicate syntax
okay, a feature set predicate is described by the syntax production for filter 🎀
4.2.1. Filter syntax
A filter is either a simple feature comparison (item, more on that below) or a composite filter (and, or, not). Either way it can be decorated with optional parameter values, including q=qvalue ✨
A composite filter is a logical combination of one or more filter values:
(& f1 f2 ... fn )is the logical-AND of the filter valuesf1,f2up tofn. It's satisfied by any feature collection that satisfies all of the predicates those filters represent 💅(| f1 f2 ... fn )is the logical-OR of the filter valuesf1,f2up tofn. It's satisfied by any feature collection that satisfies at least one of the predicates those filters represent 🦋(! f1 )is the logical negation of the filter valuef1. It's satisfied by any feature collection that does NOT satisfy the predicatef1represents 🙈
4.2.2. Feature comparison
A feature comparison is the simple option of the item production. There are three basic forms 🍓
(ftag=value)compares the feature namedftag(in some feature collection being tested) with the suppliedvalue, and matches if they're equal. This works with any type of feature value: numeric, Boolean, token or string 💖(ftag<=value)compares the numeric feature namedftagwith the suppliedvalue, and matches if the feature is less than or equal tovalue🌸(ftag>=value)compares the numeric feature namedftagwith the suppliedvalue, and matches if the feature is greater than or equal tovalue🌈
Less-than and greater-than tests can be run on non-numeric feature values too 👀 But in general they boil down to equality tests, because this specification doesn't define an ordering for non-numeric values. Specific applications may define orderings for specific feature tags, but those definitions are out of scope here and aren't needed for conformance to this specification 🧠
4.2.3. Feature tags
Feature tags follow the syntax given in "Media Feature Tag Registration Procedure" [3]. Feature tags used to describe capabilities should be registered using the procedures in that memo. Unregistered feature tags should be allocated in the "URI tree", as discussed in the media feature registration procedures memo [3] 🗂️
If an unrecognized feature tag shows up during feature set predicate processing, it should still be processed as a legitimate feature tag 🫶 The feature set matching rules are designed so new feature tags can be introduced without breaking the validity of existing capability assertions. Iconic, honestly 👑
4.2.4. Feature values
A feature may have a number, Boolean, token or string value ✨
4.2.4.1. Boolean values
A Boolean is just a token with two predefined values, TRUE and FALSE. Upper- or lower-case letters may be used in any combination 🌟
4.2.4.2. Numeric values
A numeric value is either a decimal integer, optionally preceded by a + or - sign, or a rational number 🔢
A rational number is written as n/m, optionally preceded by a + or - sign. The n and m are unsigned decimal integers, and the value of n/m is n divided by m 🧮 So all of these are valid ways to write the number 1.5:
3/2
+15/10
600/400Several rational forms can express the same value, which is kinda fun 🌸 To get the canonical form, find the highest common factor of n and m, then divide both n and m by it.
A plain integer can go anywhere a rational number can, so:
+5 is equivalent to +5/1 or +50/10, etc.
-2 is equivalent to -2/1 or -4/2, etc.Any sign in a rational number has to come before the entire number, so these are not valid rational numbers 🙅♀️
3/+2, 15/-10 (**NOT VALID**)4.2.4.3. Token values
A token value is any sequence of letters, digits and - characters that matches the token syntax above. It's a name that stands for some unspecified value 🏷️
4.2.4.4. String values
A string value is any sequence of characters in double quotes that matches the string syntax above 💬
String semantics here are the same as for a token value. But a string allows way more internal formats, and specific applications may interpret the content in ways that go beyond what's given here 🌈 Where that kind of interpretation is possible, the allowed string formats and their interpretations should be indicated in the media feature registration (per RFC 2506 [3]) 📝
4.2.5. Notational conveniences
The set option of the item production is just shorthand for some common situations that can be written with simple constructs 🍰 You can get rid of set items by applying these identities:
T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) )
(T=[R1..R2]) --> (& (T>=R1) (T<=R2) )
(T=[E]) --> (T=E)Examples time 🎀
This expression:
( paper-size=[A4,B4] )can express a capability to print documents on either A4 or B4 paper 🖨️
This expression:
( width=[4..17/2] )might express a capability to print documents anywhere between 4 and 8.5 inches wide 📏
The set construct is designed so enumerated values and ranges can be combined in one expression, like this 💅
( width=[3,4,6..17/2] )4.3. Feature set definition example
Here's an example of a feature predicate that describes a bunch of image size and resolution combinations. It assumes the registration and use of the Pix-x, Pix-y, Res-x and Res-y feature tags 📸✨
(| (& (Pix-x=1024)
(Pix-y=768)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) ) )
(& (Pix-x=800)
(Pix-y=600)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) ) ) ;q=0.9
(& (Pix-x=640)
(Pix-y=480)
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) ) ) ;q=0.8 )5. Matching feature sets ✨
okay so this section is all about taking two feature sets and figuring out if there's any feature collection that fits both of them 💖 Picking the best one from the options (using q-values or whatever) isn't covered here, bestie 🙈
Matching one feature set against one specific feature collection is lowkey super easy 🎀 You just evaluate the feature set predicate on that collection. You get TRUE or FALSE, and TRUE means the collection matches the capabilities. The quality value attached to it is what you use to pick between alternatives.
Matching a feature set against another feature set is the trickier one 😭 The question becomes: is there at least one feature collection that matches both? Like, does the capability overlap between a file format and a recipient actually exist? 🦋
This matching happens by logically manipulating the predicate expressions, which the sub-sections below walk through 🧚
For this to work reliably, the predicates have to be reduced to a canonical form. The one used here is "disjunctive normal form" 💅 The syntax looks like this:
filter = orlist
orlist = "(" "|" andlist ")" / term
andlist = "(" "&" termlist ")" / term
termlist = 1*term
term = "(" "!" simple ")" / simple"simple" is the same thing we covered back in section 4.1. So the canonical form has at most three levels: an outermost "(|...)" disjunction, full of "(&...)" conjunctions, full of possibly negated feature value tests.
NOTE: The usual canonical form for predicate expressions is "clausal form". Procedures for converting general predicate expressions are given in [5] (section 10.2), [11] (section 2.13) and [12] (section 5.3.2). Clausal form is kind of like conjunctive normal form for a proposition: an AND of ORs. The one we use, disjunctive normal form, is a bit better suited to feature set matching 🌈 It's an OR of ANDs. In this form, the goal of matching is to show that at least one of the disjunctions can be satisfied by some feature collection. Now you might be thinking, "wait, is all this canonical form stuff really needed? Aren't feature predicates just Boolean expressions?" Well, no 💀 A feature predicate is a Boolean expression full of primitive feature value tests (comparisons), which show up as 'item' in the feature predicate syntax. If every one of those tests could be assumed to be independently TRUE or FALSE, each one could be treated as an atomic proposition, and the whole predicate could be handled with the (pretty simple) rules of Propositional Calculus. But in general, the same feature tag can show up in more than one predicate 'item', so the tests aren't independent. Honestly, interdependence is needed for any meaningful feature set matching, and it's important to capture those dependencies. For example: does the set of resolutions a sender can supply overlap with the set of resolutions a recipient can handle? So we have to deal with elements of Predicate Calculus, plus some extra rules for algebraic manipulation. Both the Propositional and Predicate calculi are described in [12]. The goal here is to show that these extra rules are more unfamiliar than complicated 🫶 Building and using feature predicates actually skips some of the mess you'd get from fully generalized Predicate Calculus.
5.1 Feature set matching strategy
The overall strategy for matching feature sets goes like this, with the details expanded below ✨
- Formulate the feature set match hypothesis.
- Replace "set" expressions with equivalent comparisons.
- Move logical negations "inwards", so that they are all applied directly to feature comparisons.
- Eliminate logical negations, and express all feature comparisons in terms of just four comparison operators.
- Reduce the hypothesis to canonical disjunctive normal form (a disjunction of conjunctions).
- For each of the conjunctions, attempt to show that it can be satisfied by some feature collection.
- 6.1 Separate the feature value tests into independent feature groups, so each group contains tests involving just one feature tag. That way, no predicate in a feature group contains a feature tag that also appears in some other group.
- 6.2 For each feature group, merge the various constraints down to a minimum form. This either gives you a reduced expression for the allowable range of feature values, or an expression containing the value FALSE. FALSE means no combination of feature values can satisfy the constraints, so that conjunction can never be satisfied 💅
- If the remaining disjunction contains at least one satisfiable conjunction, then the constraints are shown to be satisfiable 🎉
The final expression from this procedure, if it's non-empty, can be used as a statement of the resulting feature set for any further matching. In other words, it's a starting point for combining with additional feature set constraint predicates, so you can figure out the feature set constrained by the capabilities of several entities along a message transfer path 🦋
NOTE: As presented, the matching process evaluates (and stores) all the conjunctions of the disjunctive normal form before it combines feature tag comparisons and gets rid of unsatisfiable conjunctions. For low-memory systems there's an alternative approach: enumerate and evaluate each normal form conjunction in turn, keeping only the satisfiable ones for further use 🧚
5.2 Formulating the goal predicate
Here's the formal version of the problem 🤓 Given two feature set predicates, '(P x)' and '(Q x)', where 'x' is some feature collection, we want to figure out whether this proposition is true:
EXISTS(x) : (P x) AND (Q x)Basically: does there exist a feature collection 'x' that satisfies both predicates, 'P' and 'Q'?
So if the feature sets being matched are described by predicates 'P' and 'Q', the problem is figuring out whether any feature set satisfies this goal predicate:
(& P Q)In other words, we're determining whether the set described this way is non-empty 👑
5.3 Replace set expressions
Next, replace all the "set" instances in the goal predicate with equivalent "simple" forms 💖
T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) )
(T=[R1..R2]) --> (& (T>=R1) (T<=R2) )
(T=[E]) --> (T=E)5.4 Move logical negations inwards
The goal of this step is to move every logical negation so it's applied directly to a feature comparison 🔥 In the next step, these negations get swapped out for alternative comparison operators.
You get there by repeatedly applying these transformation rules:
(! (& A1 A2 ... Am ) ) --> (| (! A1 ) (! A2 ) ... (! Am ) )
(! (| A1 A2 ... Am ) ) --> (& (! A1 ) (! A2 ) ... (! Am ) )
(! (! A ) ) --> AThe first two are extended forms of De Morgan's law, and the third just gets rid of double negatives 🙈
5.5 Replace comparisons and logical negations
The predicates come from the syntax we looked at earlier, and they contain the primitive value testing functions '=', '<=' and '>='. These primitive tests have a bunch of well-known properties that we can exploit to reach a useful conclusion, for example:
(A = B) & (B = C) => (A = C)
(A <= B) & (B <= C) => (A <= C)These rules are the core body of logic statements the goal predicate gets evaluated against. How they're written matters a lot if you want a predicate matching algorithm that actually works (one that doesn't loop forever or fail to find a valid result) 😭 So the first step is simplifying the framework of primitive predicates.
The primitive predicates that feature set definitions are built from are '=', '<=' and '>='. Look at it this way: for any pair of feature values, the relationship between them must be exactly one of the following:
(LT a b): 'a' is less than 'b'.(EQ a b): 'a' is equal to 'b'.(GT a b): 'a' is greater than 'b'.(NE a b): 'a' is not equal to 'b', and is not less than or greater than 'b'.
(That last case shows up when you compare two values that have no ordering relationship defined and aren't equal, like two unequal string values 🍓)
All four of those cases can be captured by a pair of primitive predicates:
(LE a b): 'a' is less than or equal to 'b'.(GE a b): 'a' is greater than or equal to 'b'.
The four cases above map onto combinations of these primitive predicate values like so:
(LE a b) (GE a b) | relationship
----------------------------------
TRUE FALSE | (LT a b)
TRUE TRUE | (EQ a b)
FALSE TRUE | (GT a b)
FALSE FALSE | (NE a b)So the original 3 primitive tests can be translated into combinations of just LE and GE, which cuts down on the extra relationships that need capturing later 💜
(a <= b) --> (LE a b)
(a >= b) --> (GE a b)
(a = b) --> (& (LE a b) (GE a b) )Logical negations of the original 3 primitive tests can also be removed by introducing 'not-greater' and 'not-less' primitives 🌸
(NG a b) == (! (GE a b) )
(NL a b) == (! (LE a b) )using these transformation rules:
(! (a = b) ) --> (| (NL a b) (NG a b) )
(! (a <= b) ) --> (NL a b)
(! (a >= b) ) --> (NG a b)And that's the whole thing! We now have rules that turn every comparison and logical negation into some combination of just 4 relational operators 🎀✨
5.6 Conversion to canonical form 💅
🫶 NOTE: Logical negations have been eliminated in the previous step.
Okay bestie, now we expand the bracketed disjunctions and flatten any bracketed conjunctions and disjunctions 🌸:
(& (| A1 A2 ... Am ) B1 B2 ... Bn )
--> (| (& A1 B1 B2 ... Bn )
(& A2 B1 B2 ... Bn )
:
(& Am B1 B2 ... Bn ) )
(& (& A1 A2 ... Am ) B1 B2 ... Bn )
--> (& A1 A2 ... Am B1 B2 ... Bn )
(| (| A1 A2 ... Am ) B1 B2 ... Bn )
--> (| A1 A2 ... Am B1 B2 ... Bn )Once that's done, the result is in "disjunctive normal form" ✨, which is a disjunction of conjunctions:
(| (& S11 S12 ... )
(& S21 S22 ... )
:
(& Sm1 Sm2 ... Smn ) )The Sij elements are simple feature comparison forms that we built back in section 5.5. 🦋 Each term inside the top-level (|...) is one possible feature set that could satisfy the goal. The order of entries inside the top-level (|...), and inside each (&...), doesn't matter at all 💜.
From here on, every conjunction (&...) gets processed on its own. Only one of them has to be satisfiable for the original goal to be satisfiable 👑.
(A textbook conversion to clausal form [5,11] uses slightly different rules and gives you a "conjunctive normal form" instead, so don't mix them up 🙈.)
5.7 Grouping of feature predicates 🎀
💅 NOTE: Remember that from here on, each conjunction is treated separately.
Every simple feature predicate has a "left-hand" feature tag and a "right-hand" feature value that it gets compared against 🍓.
To sort these into independent groups, we group the simple predicates by their left-hand feature tag (f) 🧚.
5.8 Merge single-feature constraints ✨
Inside each group, we apply the predicate simplification rules below to get rid of redundant single-feature constraints 🫧. Every single-feature predicate ends up as either an equality or a range constraint on that feature, maybe combined with a bunch of non-equality statements.
If the constraints on any feature turn out to be contradictory (meaning they resolve to FALSE under these rules), the whole conjunction is not satisfiable and can be thrown out 🗑️. Otherwise, what you're left with is the minimal form of that particular conjunction of the feature set definition 🌈.
5.8.1 Rules for simplifying ordered values 📏
These rules work when there's an ordering relationship between the values a and b 💖:
(LE f a) (LE f b) --> (LE f a), a<=b
(LE f b), otherwise
(LE f a) (GE f b) --> FALSE, a<b
(LE f a) (NL f b) --> FALSE, a<=b
(LE f a) (NG f b) --> (LE f a), a<b
(NG f b), otherwise
(GE f a) (GE f b) --> (GE f a), a>=b
(GE f b), otherwise
(GE f a) (NL f b) --> (GE f a) a>b
(NL f b), otherwise
(GE f a) (NG f b) --> FALSE, a>=b
(NL f a) (NL f b) --> (NL f a), a>=b
(NL f b), otherwise
(NL f a) (NG f b) --> FALSE, a>=b
(NG f a) (NG f b) --> (NG f a), a<=b
(NG f b), otherwise5.8.2 Rules for simplifying unordered values 🔍
These rules are for when there's no ordering relationship between the values a and b 🙃:
(LE f a) (LE f b) --> (LE f a), a=b
FALSE, otherwise
(LE f a) (GE f b) --> FALSE, a!=b
(LE f a) (NL f b) --> (LE f a) a!=b
FALSE, otherwise
(LE f a) (NG f b) --> (LE f a), a!=b
FALSE, otherwise
(GE f a) (GE f b) --> (GE f a), a=b
FALSE, otherwise
(GE f a) (NL f b) --> (GE f a) a!=b
FALSE, otherwise
(GE f a) (NG f b) --> (GE f a) a!=b
FALSE, otherwise
(NL f a) (NL f b) --> (NL f a), a=b
(NL f a) (NG f b) --> (NL f a), a=b
(NG f a) (NG f b) --> (NG f a), a=b6. Other features and issues 🌷
6.1 Named and auxiliary predicates 🧁
Named and auxiliary predicates have two jobs 💜:
- (a) making complex predicates easier to write and understand, and
- (b) providing a possible basis for naming and registering feature sets.
6.1.1 Defining a named predicate 🎀
A named predicate definition looks like this 👇:
named-pred = "(" fname *pname ")" ":-" filter
fname = ftag ; Feature predicate name
pname = token ; Formal parameter namefname is the name of the predicate ✨.
pname is the name of a formal parameter. It can show up in the predicate body, and it gets swapped out for a supplied value whenever the predicate is invoked 🦋.
filter is the predicate body. It can reference the formal parameters, and it can also reference feature tags and other values defined in the environment where the predicate gets invoked 💅. Formal parameters can go anywhere the syntax for filter allows a feature tag (ftag) 🌸.
The only specific mechanism this memo defines for bringing a named predicate into a feature set definition is the "auxiliary predicate" we'll get to later 🧚. Specific negotiating protocols or other specifications are free to define other mechanisms too 💖.
🔮 NOTE: There's been some talk about creating a registry for feature sets as well as individual feature values. That kind of registry could bring in named predicates matching those feature sets into the environment of a capability assertion. Digging into that idea further is out of scope for this memo 🙈.
6.1.2 Invoking named predicates 🚀
Once a named predicate has been brought into the environment of some other predicate, you can invoke it with an ext-pred filter, which looks like this 🌈:
ext-pred = fname *param
param = exprThe number of parameters has to match the definition of the named predicate being invoked 🔥.
6.1.3 Auxiliary predicates in a filter 🪄
An auxiliary predicate gets attached to a filter definition through this extension to the "filter" syntax ✨:
filter =/ "(" filtercomp *( ";" parameter ) ")"
"where" 1*( named-pred ) "end"The named predicates introduced by "named-pred" are visible from the body of the "filtercomp" in the filter they're attached to, but they can't see each other 👀. They all get the same environment as "filter", plus their own formal parameters. (Normal scoping rules apply, so a formal parameter with the same name as a value in the environment of "filter" hides that environment value from the body of the predicate it belongs to 🫣.)
🚫 NOTE: Recursive predicates are not permitted. The scoping rules should make sure of that.
6.1.4 Feature matching with named predicates 🧩
The procedures we already covered can be extended to handle named predicates. You just instantiate (aka substitute) the predicates everywhere they're invoked, before doing the conversion to disjunctive normal form 💖. Without recursive predicates, this procedure is guaranteed to terminate 🌸.
When you substitute the body of a predicate at its point of invocation, every instance of a formal parameter inside that body has to be replaced by the matching actual parameter from the point of invocation 🎀.
6.1.5 Example 💎
This example restates the one from section 4.3, using an auxiliary predicate named Res 🦋:
(| (& (Pix-x=1024) (Pix-y=768) (Res Res-x Res-y) )
(& (Pix-x=800) (Pix-y=600) (Res Res-x Res-y) );q=0.9
(& (Pix-x=640) (Pix-y=480) (Res Res-x Res-y) );q=0.8 )
where
(Res Res-x Res-y) :-
(| (& (Res-x=150) (Res-y=150) )
(& (Res-x=150) (Res-y=300) )
(& (Res-x=300) (Res-y=300) )
(& (Res-x=300) (Res-y=600) )
(& (Res-x=600) (Res-y=600) ) )
endNotice that the formal parameters Res, Res-x and Res-y stop the body of the named predicate from referencing feature values with similar names 🧠✨.
6.2 Unit designations 📐
Every now and then, a feature's units of measurement are conventionally different in different places 🌍. Resolution is a classic example: it's often written as dots per inch (dpi) or dots per centimetre (dpcm), depending on the application, like printing versus faxing 🖨️.
In those exceptional cases, you can tack a unit designator onto a feature value, following the conventions below (see also [3]) 💅. This only applies to features with numeric values 🔢.
Every feature tag has a standard unit of measurement. Any feature value written in that unit has no unit designation, and that's the normal case 🌸. When a value is written in some other unit, you append a unit designator to the numeric value 💖.
The registration of a feature tag tells you its standard unit of measurement, plus any alternate units and matching unit designators that can be used, according to RFC 2506 [3] 📜.
So if the standard unit for resolution is 'dpcm', then (res=200) means 200 dots-per-centimetre, and (res=72dpi) might be used to mean 72 dots-per-inch ✨.
Unit designators are added through this extension to the feature predicate syntax:
fvalue =/ number *WSP tokenWhen you're doing feature set matching, comparisons with and without unit designators, or comparisons with different unit designators, are treated as if they were different features 🙅♀️. So (res=200) won't generally match (res=200dpi) 💀.
🤓 NOTE: A protocol processor that knows specifically about the feature and its units might spot the relationship between the predicates in that example and treat them as a match. That looks natural in this simple case, but it can get messy in more general cases. So this is not considered to be required or normal behaviour 🙈. The application concerned is presumed to keep feature processing consistent by using one consistent unit for any given feature 🫶.
6.3 Unknown feature value data types 🌀
So far this memo has covered feature values with well-understood comparison properties: numbers, which have equality plus less-than and greater-than relationships, and other values that only have equality relationships 🔢.
Some feature values have comparison operations this framework doesn't cover. Strings holding multi-part version numbers like "x.y.z" are one example 🔢. Feature comparisons like those aren't covered by this memo 🙃.
Specific applications may recognize and process feature tags tied to those values 💜. Future work may define ways to introduce new feature value data types so applications without built-in knowledge of their properties can still use them 🌈.
7. Examples and additional comments ✨
7.1 Worked example 🎀
okay bestie, this one is a whole glow-up story 💅 A sender wants to send a document to a high-end black-and-white fax machine. Let's see what the fax can actually take:
(& (dpi=[200,300])
(grey=2) (color=0)
(image-coding=[MH,MR]) )Now the document. The sender has it in three possible formats: A4 high resolution, B4 low resolution, and A4 high resolution colour. Here's how each one is described:
(& (dpi=300)
(grey=2)
(image-coding=MR) )
(& (dpi=200)
(grey=2)
(image-coding=[MH,MMR]) )
(& (dpi=300) (dpi-xyratio=1)
(color<=256)
(image-coding=JPEG) )We can mash those three formats into one composite capability statement with a logical-OR (format-1 OR format-2 OR format-3) 🦋:
(| (& (dpi=300)
(grey=2)
(image-coding=MR) )
(& (dpi=200)
(grey=2)
(image-coding=[MH,MMR]) )
(& (dpi=300)
(color<=256)
(image-coding=JPEG) ) )Next, the match. We combine the receiver's capabilities with the composite document description using a logical AND ✨:
(& (& (dpi=[200,300])
(grey=2) (color=0)
(image-coding=[MH,MR]) )
(| (& (dpi=300)
(grey=2)
(image-coding=MR) )
(& (dpi=200)
(grey=2)
(image-coding=[MH,MMR]) )
(& (dpi=300)
(color<=256)
(image-coding=JPEG) ) ) )Then the simplifying starts, and it's giving a whole step-by-step makeover 🌈
Step one, expand the value-set notation:
(& (& (| (dpi=200) (dpi=300) )
(grey=2) (color=0)
(| (image-coding=MH) (image-coding=MR) ) )
(| (& (dpi=300)
(grey=2)
(image-coding=MR) )
(& (dpi=200)
(grey=2)
(| (image-coding=MH) (image-coding=MMR) ) )
(& (dpi=300)
(color<=256)
(image-coding=JPEG) ) ) )Step two, flatten the nested '(&...)':
(& (| (dpi=200) (dpi=300) )
(grey=2) (color=0)
(| (image-coding=MH) (image-coding=MR) )
(| (& (dpi=300)
(grey=2)
(image-coding=MR) )
(& (dpi=200)
(grey=2)
(| (image-coding=MH) (image-coding=MMR) ) )
(& (dpi=300)
(color<=256)
(image-coding=JPEG) ) ) )Step three, distribute '(&...)' over the inner '(|...)':
(& (| (dpi=200) (dpi=300) )
(grey=2) (color=0)
(| (image-coding=MH) (image-coding=MR) )
(| (& (dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (color<=256) (image-coding=JPEG) ) ) )Step four, keep distributing '(&...)' over '(|...)', and keep flattening nested '(&...)' and '(|...)' ...:
(| (& (dpi=200) (grey=2) (color=0) (image-coding=MH)
(| (& (dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MR)
(| (& (dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MH)
(| (& (dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MR)
(| (& (dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (color<=256) (image-coding=JPEG) ) ) ) )Keep going until we hit normal form, which is the end of the road 👑:
(| (& (dpi=200) (grey=2) (color=0) (image-coding=MH)
(dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MR)
(dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MH)
(dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MR)
(dpi=300) (grey=2) (image-coding=MR) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MH)
(dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MR)
(dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MH)
(dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MR)
(dpi=200) (grey=2) (image-coding=MH) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MH)
(dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MR)
(dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MH)
(dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MR)
(dpi=200) (grey=2) (image-coding=MMR) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MH)
(dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MR)
(dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MH)
(dpi=300) (color<=256) (image-coding=JPEG) ) ) )
(& (dpi=300) (grey=2) (color=0) (image-coding=MR)
(dpi=300) (color<=256) (image-coding=JPEG) ) )Last tidy-up: group the terms in each conjunction by feature tag:
(| (& (dpi=200) (dpi=300) (grey=2) (grey=2) (color=0)
(image-coding=MH) (image-coding=MR) )
(& (dpi=200) (dpi=300) (grey=2) (grey=2) (color=0)
(image-coding=MR) (image-coding=MR) )
:
(etc.)
:
(& (dpi=300) (dpi=300) (grey=2) (color=0) (color<=256)
(image-coding=MR) (image-coding=JPEG) ) )Then combine the feature tag comparisons and throw out the unsatisfiable conjunctions 🗑️:
(| (& (dpi=300) (grey=2) (color=0) (image-coding=MR) )
(& (dpi=200) (grey=2) (color=0) (image-coding=MH) ) )And that's the tea ☕: this combo of sender and receiver options can transfer a bi-level image, either at 300dpi using MR coding, or at 200dpi using MH coding. Lowkey iconic 🦋
A few things to note about how the feature matching went down 💖
- The colour document option got eliminated because the receiver can't handle either colour (indicated by '(color=0)') or JPEG coding. 😭
- The high resolution version of the document with '(dpi=300)' must be sent using '(image-coding=MR)', because that's the only coding of the image data the receiver can use for high resolution documents. (The available 300dpi document codings here are MMR and MH, and the receiver capabilities are MH and MR.) 🙈
7.2 A note on feature tag scoping 🎀
okay bestie, this part is extra commentary, so it doesn't extend or change anything from before 💅 it's just clearing up a spot where people get confused 🙈
The essential thing to lock in is this: within a given feature collection, each feature tag may have only one value ✨
We'll see why through the media feature framework, which describes transmitted image data 🦋
In that setting, any feature tag value has to apply to the entire image. It can't be different for different parts of one image. This comes from how feature predicates get used to describe all the possible images, like the ones a given recipient can render 💖
Here's a flawed feature set description based on the TIFF image format for Internet fax [13]:
(& (& (MRC-mode=1) (stripe-size=256) )
(| (& (image-coding=JBIG-2-LEVEL) (stripe-size=128) )
(image-coding=[MH,MR,MMR]) ) )This one is super revealing because 'stripe-size' is applied in two different ways to MRC-formatted data: once to the MRC format as a whole, and again to a JBIG image sitting inside the MRC data 👀
You might think it means a stripe size of 256 for the MRC format and 128 for the JBIG-2-LEVEL image. Nope 🙅♀️ predicates obey the normal laws of Boolean logic, so it transforms like this:
--> [flatten nested (&...)]:
(& (MRC-mode=1) (stripe-size=256)
(| (& (image-coding=JBIG-2-LEVEL) (stripe-size=128) )
(image-coding=[MH,MR,MMR]) ) )
--> [Distribute (&...) over (|...)]:
(| (& (MRC-mode=1) (stripe-size=256)
(& (image-coding=JBIG-2-LEVEL) (stripe-size=128) ) )
(& (MRC-mode=1) (stripe-size=[0..256])
(image-coding=[MH,MR,MMR]) ) )
--> [Flatten nested (&...) and group feature tags]:
(| (& (MRC-mode=1)
(stripe-size=256)
(stripe-size=128)
(image-coding=JBIG-2-LEVEL) )
(& (MRC-mode=1)
(stripe-size=256)
(image-coding=[MH,MR,MMR]) ) )Now look at that last expression. It needs both 'stripe-size=128' and 'stripe-size=256' inside the same conjunction. That's manifestly false, so the whole conjunction is false, and the entire predicate shrinks to:
(& (MRC-mode=1)
(stripe-size=256)
(image-coding=[MH,MR,MMR]) ) )So no MRC-formatted data containing a JBIG-2-LEVEL coded image is allowed in the feature set at all. That is NOT what was intended 😭
The only way to avoid this, when a characteristic has different constraints in different parts of a resource, is to use separate feature tags. Here, 'MRC-stripe-size' and 'JBIG-stripe-size' capture the intent 🧚
(& (& (MRC-mode=1) (MRC-stripe-size=256) )
(| (& (image-coding=JBIG-2-LEVEL) (JBIG-stripe-size=128) )
(image-coding=[MH,MR,MMR]) ) )which reduces to:
(| (& (MRC-mode=1)
(MRC-stripe-size=256)
(JBIG-stripe-size=128)
(image-coding=JBIG-2-LEVEL) )
(& (MRC-mode=1)
(MRC-stripe-size=256)
(image-coding=[MH,MR,MMR]) ) )The rule behind all this is the idea of a "feature collection", which (in this context) describes the feature values that apply to a single resource. Within a feature collection, each feature tag may have no more than one value 💜
A "Feature set" describes the characteristics of an image sender or receiver. Formally, it's a set of feature collections. The feature set predicate gets applied to some image feature collection to figure out whether it belongs to the set that an image receiver can handle 🌈
8. Security Considerations 🔐
Some security considerations for content negotiation are raised in [1,2,3].
Okay, now the serious part 😤 These are the primary security concerns for capability identification mechanisms:
- Unintentional disclosure of private information through the announcement of capabilities or user preferences.
- Disruption to system operation caused by accidental or malicious provision of incorrect capability information.
- Use of a capability identification mechanism might be used to probe a network (e.g. by identifying specific hosts used, and exploiting their known weaknesses).
The most contentious concerns come from mechanisms that automatically send capability identification data in response to a query from some unknown system. Directory services (based on LDAP [7], etc.) seem to be less problematic, because proper authentication mechanisms are available 🙌
Mechanisms that provide capability information when sending a message are less contentious, presumably because some intention can be inferred: the person whose details are disclosed wishes to communicate with the recipient of those details. This does not, however, solve problems of spoofed supply of incorrect capability information 💀
And the use of format converting gateways may prove problematic, because such systems would tend to defeat any message integrity and authenticity checking mechanisms that are employed 😬
9. Acknowledgements 💜
Thanks are due to Larry Masinter for demonstrating the breadth of the media feature issue and encouraging the development of some early thoughts 🫶
Many of the ideas presented derive from the "Transparent Content Negotiation in HTTP" work of Koen Holtman and Andy Mutz [4] 👑
Early discussions of ideas with the IETF HTTP and FAX working groups led to further useful inputs from Koen Holtman, Ted Hardie and Dan Wing. The debate later moved to the IETF 'conneg' working group, where Al Gilman and Koen Holtman were particularly helpful in refining the feature set algebra. Ideas for dealing with preferences and specific units were suggested by Larry Masinter 🌸
This work was supported by Content Technologies Ltd and 5th Generation Messaging Ltd. 🎀
10. References 📚
- [1] Hardie, T., "Scenarios for the Delivery of Negotiated Content", Work in Progress.
- [2] Klyne, G., "Requirements for protocol-independent content negotiation", Work in Progress.
- [3] Holtman, K., Mutz, A., and T. Hardie, "Media Feature Tag Registration Procedure", BCP 31, RFC 2506, March 1999.
- [4] Holtman, K. and A. Mutz, "Transparent Content Negotiation in HTTP", RFC 2295, March 1998.
- [5] "Programming in Prolog" (2nd edition), W. F. Clocksin and C. S. Mellish, Springer Verlag, ISBN 3-540-15011-0 / 0-387-15011-0, 1984.
- [6] Masinter, L., Holtman, K., Mutz, A., and D. Wing, "Media Features for Display, Print, and Fax", RFC 2534, March 1999.
- [7] Wahl, M., Howes, T. and S. Kille, "Lightweight Directory Access Protocol (v3)", RFC 2251, December 1997.
- [8] Howes, T., "The String Representation of LDAP Search Filters", RFC 2254, December 1997.
- [9] Fielding, R., Gettys, J., Mogul, J., Frytyk, H. and T. Berners-Lee, "Hyptertext Transfer Protocol -- HTTP/1.1", RFC 2068, January 1997.
- [10] Crocker, D., Editor, and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, November 1997.
- [11] "Logic, Algebra and Databases", Peter Gray, Ellis Horwood Series: Computers and their Applications, ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd), ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press), 1984.
- [12] "Logic and its Applications", Edmund Burk and Eric Foxley, Prentice Hall, Series in computer science, ISBN 0-13-030263-5, 1996.
- [13] McIntyre, L., Buckley, R., Venable, D., Zilles, S., Parsons, G. and J. Rafferty, "File Format for Internet Fax", RFC 2301, March 1998.
- [14] Apache content negotiation algorithm, <http://www.apache.org/docs/content-negotiation.html>
11. Author's Address 🖋️
Graham Klyne
Content Technologies Ltd. 5th Generation Messaging Ltd.
Forum 1 5 Watlington Street
Station Road Nettlebed
Theale Henley-on-Thames
Reading, RG7 4RA RG9 5AB
United Kingdom United Kingdom.
Phone: +44 118 930 1300 +44 1491 641 641
Facsimile: +44 118 930 1301 +44 1491 641 611
EMail: GK@ACM.ORGFull Copyright Statement ©
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 🌈💖
📦 where this page comes from
- ietf: rfc2533 1999-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms