cap:
Browse Sign In

Matching

How patterns match instances, and why it's directional

What Matching Does

Matching answers a single question: does a capability satisfy a request? You have a request URN describing what you need, and a capability URN describing what something does. Matching tells you whether the capability is suitable.

Every tag in both URNs is compared independently. If all tags pass, the match succeeds. If any tag fails, the whole match fails.

Two Directions: accepts and conformsTo

Matching is directional. There are two ways to say the same thing:

  • pattern.accepts(instance) — does the pattern accept this instance?
  • instance.conformsTo(pattern) — does the instance conform to this pattern?

These are equivalent. a.conformsTo(b) always gives the same result as b.accepts(a). You pick whichever reads better in context.

The pattern is the side with the constraints. The instance is the thing being tested. When a request asks for op=extract and a capability has op=extract;format=pdf, the request is the pattern and the capability is the instance. The pattern says "I need extraction" and the instance says "I do extraction of PDFs". The instance has more tags, which is fine — extra tags don't cause a mismatch.

Per-Tag Truth Table

Each tag is evaluated by looking at what the pattern says for that key and what the instance has. Here is the full truth table:

Pattern Instance missing Instance = v Instance = x (x ≠ v)
(missing) or ? OK OK OK
K=! OK NO NO
K=* NO OK OK
K=v NO OK NO

Row 1: Missing or ? (no constraint)

When the pattern does not have a tag, or sets it to ?, there is no constraint. The instance can have any value for that key, or omit it entirely. This is the default — if you don't mention a tag, you don't care about it. 

# Pattern: cap:op=extract
# Instance: cap:format=pdf;op=extract
# The pattern has no "format" tag, so format is unconstrained.
# The instance's format=pdf is allowed. Result: OK

Row 2: K=! (must not have)

The pattern requires that the instance does NOT have this tag. If the instance has the tag with any value, the match fails. If the instance omits the tag, the match passes.

Use this when you want to exclude capabilities that have a certain property. 

# Pattern: cap:debug=!;op=extract
# Instance: cap:op=extract
# Instance lacks "debug", pattern requires it absent. Result: OK

# Instance: cap:debug=true;op=extract
# Instance has "debug", pattern forbids it. Result: NO

Row 3: K=* (must have any)

The pattern requires that the instance HAS this tag, but doesn't care what value it has. If the instance omits the tag, the match fails. If the instance has the tag with any value, the match passes.

Use this when you need a property to be present but don't care about its specific value. 

# Pattern: cap:format=*;op=extract
# (equivalently: cap:format;op=extract)

# Instance: cap:format=pdf;op=extract
# Instance has "format" (value=pdf). Result: OK

# Instance: cap:format=docx;op=extract
# Instance has "format" (value=docx). Result: OK

# Instance: cap:op=extract
# Instance lacks "format", pattern requires it. Result: NO

Row 4: K=v (exact value)

The pattern requires that the instance has this tag with exactly this value. If the instance omits the tag or has a different value, the match fails.

There is one exception: if the instance has K=*, it acts as a wildcard and matches any pattern value. This lets instances declare "I accept any value for this key". 

# Pattern: cap:format=pdf;op=extract

# Instance: cap:format=pdf;op=extract
# Exact match on format. Result: OK

# Instance: cap:format=docx;op=extract
# format=docx != format=pdf. Result: NO

# Instance: cap:op=extract
# Instance lacks "format", pattern requires it. Result: NO

# Instance: cap:format=*;op=extract
# Instance wildcard on "format" matches any pattern value. Result: OK

Match Algorithm in Pseudocode

// pattern.accepts(instance)
// equivalently: instance.conformsTo(pattern)
function accepts(pattern, instance):
    for each key in union(pattern.keys, instance.keys):
        patt = pattern[key]   // undefined if missing
        inst = instance[key]  // undefined if missing

        if patt is undefined or patt == "?":
            continue  // no constraint
        if patt == "!":
            if inst is defined: return false  // must be absent
        else if patt == "*":
            if inst is undefined: return false  // must be present
        else:
            if inst is undefined: return false
            if inst != "*" and inst != patt: return false
    return true

Worked Example: Basic Tag Matching

Let's trace through a match step by step. 

Pattern:  cap:format=pdf;op=extract
Instance: cap:format=pdf;op=extract;target=text

The union of keys is: format, op, target.

  1. format: pattern=pdf, instance=pdf. Exact match. OK.
  2. op: pattern=extract, instance=extract. Exact match. OK.
  3. target: pattern=undefined (missing), instance=text. No constraint. OK.

All tags pass. Result: match.

Now reverse it

Pattern:  cap:format=pdf;op=extract;target=text
Instance: cap:format=pdf;op=extract
  1. format: pattern=pdf, instance=pdf. OK.
  2. op: pattern=extract, instance=extract. OK.
  3. target: pattern=text, instance=undefined (missing). Pattern requires exact value, instance lacks it. NO.

Result: no match.

This shows why matching is directional. The less constrained URN accepts the more constrained one, but not the other way around. A request for "any extractor" matches a "PDF text extractor", but a request for "PDF text extractor" does not match a generic "extractor".

Direction Specifiers

Capability URNs have two required tags: in and out. Their values are Media URNs. These tags are not compared by string equality. Instead, the matching algorithm parses each Media URN value and applies tag-level matching recursively.

The two directions use matching in opposite ways:

  • Input: cap_in.accepts(request_in) — the capability's input spec checks whether the request's input satisfies it. The capability is the pattern, the request is the instance.
  • Output: cap_out.conformsTo(request_out) — the capability's output checks whether it conforms to what the request expects. The request is the pattern, the capability is the instance.

Why the directions are asymmetric

For input, the capability defines what data it can accept. A capability that accepts media:bytes can handle any byte-based input — including media:pdf;bytes, because pdf;bytes is a subtype of bytes. The capability's input spec is the pattern (the less constrained side), and the request's input is the instance (the more constrained side).

For output, the request defines what data format it needs. A request that needs media:image;bytes is satisfied by a capability that produces media:image;png;bytes, because image;png;bytes is a subtype of image;bytes. The request's output spec is the pattern, and the capability's output is the instance.

Worked Example: Direction Matching

Cap:     cap:in="media:bytes";op=thumbnail;out="media:image;png;bytes;thumbnail"
Request: cap:in="media:pdf;bytes";op=thumbnail;out="media:image;bytes"

Step 1: Regular tags

op: cap=thumbnail, request=thumbnail. Match.

Step 2: Input direction

Test: cap_in.accepts(request_in) 

Pattern (cap input):     media:bytes
Instance (request input): media:pdf;bytes

The pattern requires bytes (must-have-any). The instance has bytes and pdf. The pattern has no constraint on pdf (missing = no constraint). All tags pass. OK.

The capability accepts any bytes, and the request offers PDF bytes. That works.

Step 3: Output direction

Test: cap_out.conformsTo(request_out) (equivalently: request_out.accepts(cap_out)) 

Pattern (request output): media:image;bytes
Instance (cap output):    media:image;png;bytes;thumbnail

The pattern requires image and bytes. The instance has image, png, bytes, and thumbnail. Extra tags (png, thumbnail) don't violate any constraint. All required tags are present. OK.

The request wants image bytes. The capability produces PNG thumbnail image bytes. That satisfies the request.

All checks pass. Result: match.

Reverse direction fails

Cap:     cap:in="media:pdf;bytes";op=thumbnail;out="media:image;bytes"
Request: cap:in="media:bytes";op=thumbnail;out="media:image;png;bytes;thumbnail"

Input: cap_in.accepts(request_in) 

Pattern (cap input):     media:pdf;bytes
Instance (request input): media:bytes

The pattern requires pdf (must-have-any). The instance lacks pdf. NO. The capability needs PDF files specifically, but the request only promises generic bytes.

Match fails at the input check. The capability can't handle the request's data.

Summary

  • Matching evaluates each tag independently against the truth table
  • All tags must pass for a match to succeed
  • Missing tags in the pattern impose no constraint
  • Extra tags in the instance are allowed
  • in and out tags use nested Media URN matching, not string comparison
  • Input: capability is the pattern (it defines what it accepts)
  • Output: request is the pattern (it defines what it needs)

When multiple capabilities match, specificity determines which one wins.