17Pattern matching

Pattern matching tests whether a value has a particular shape and, when it does, gives names to the parts you need. It replaces the error-prone two-step habit of "check the tag, then pull out the payload" with one construct that cannot read a payload under the wrong tag. It works on structs, tagged unions, tuples, and literals. This chapter covers §11 "Pattern matching" of the BSV Language Reference Guide: constants, pattern variables and wildcards, nested struct and tagged-union patterns, case ... matches with &&& filters, pattern tests in if conditions and rule guards, and match declarations.

Before you start. You need structs, tagged unions, and tuples from User-defined types, the ordinary case and if from Selection, case, and the don't-care value, and bit selection from Bool, Bit and pure functions, which this chapter uses in filters.

Everything in this chapter is combinational logic. A case ... matches compiles to comparators and multiplexers that are evaluated in the cycle where they are used; no state is involved.

1. Pattern building blocks

1.1 Three kinds of leaves

A pattern is written in the same shape as the value it tests. At its leaves are three kinds of items.

Syntax

expression matches pattern

if (packet matches tagged Data .request)
  $display("payload %h", request.payload);

1.2 Rules for pattern variables

• The position decides the type. .value in a Bit#(8) field has type Bit#(8). You do not declare it.
• Names in one pattern must differ. The reference guide requires it, because a repeated name would suggest an equality test that patterns do not perform.
• A name exists only where the match succeeded: the selected case item, or the then branch of a successful if.

Caution. Current bsc does not enforce distinct names everywhere. match {.a, .a} = t; compiles, and a silently takes the second member. Keep names distinct yourself.

1.3 Literal patterns with ? digits

On a Bit#(n) value, a literal pattern compares bit by bit. A ? digit in the literal matches either value.

case (instruction) matches
  8'b1010_????: return 1;   // any byte whose upper nibble is 1010
  default: return 0;
endcase

2. Struct and tagged-union patterns

2.1 Tagged-union patterns

A tagged-union pattern first checks the active tag. Only if the tag matches is the nested pattern applied to the payload.

Syntax

tagged MemberName
tagged MemberName pattern

A member with a void payload, such as Flush below, is matched with the tag alone.

2.2 Struct patterns

A struct pattern names the fields it wants to test or bind. Field order does not matter, and fields you leave out are not checked.

Syntax

StructName { field1: pattern1, field2: pattern2 }

tagged Data (Request { payload: .value })   // bind only payload
tagged Data (Request { channel: 1, payload: .value })   // also require channel 1

Nesting follows the type: the outer pattern checks the tag, the inner one looks inside the payload.

2.3 Example: from the outer tag to the inner field

In NestedPattern.bsv, a Packet is either Data, carrying a Request struct, or Flush, carrying nothing. Read the two types first, then the two items of payloadOrZero.

mkTop builds Request { channel: 2, payload: 8'ha5 }.

1. tagged Data request enters the case. The first item checks the tag: Data, success. It moves into the payload: a Request struct, success. The field list names only payload, so value is bound to 8'ha5, and channel is never looked at. The item returns 8'ha5.
2. tagged Flush fails the first item at the tag check, before any payload is examined. The second item matches Flush and returns 0.

Predict before you run.

1. Which two hexadecimal values are printed?
2. Does the channel value 2 affect either result?

package NestedPattern;

typedef struct {
  Bit#(2) channel;
  Bit#(8) payload;
} Request deriving (Bits, Eq, FShow);

typedef union tagged {
  Request Data;
  void Flush;
} Packet deriving (Bits, Eq, FShow);

function Bit#(8) payloadOrZero(Packet packet);
  // The nested struct pattern binds only the field this function needs.
  case (packet) matches
    tagged Data (Request { payload: .value }): return value;
    tagged Flush: return 0;
  endcase
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    Request request = Request { channel: 2, payload: 8'ha5 };
    $display("data=%02h flush=%02h",
             payloadOrZero(tagged Data request),
             payloadOrZero(tagged Flush));
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

Try it yourself.

1. Change the first pattern to Request { channel: 1, payload: .value }. The request still has channel: 2, so the Data packet now matches neither item. The printed byte is not guaranteed to be 0: the function reaches the end of a case with no matching item, bsc compiles this without an error, and the result is whatever the generated hardware happens to produce. Adding a default: return 0; item makes the result defined.

2. Replace .value with .* and return a constant instead. The pattern still checks the tag and the struct but binds nothing.

3. Pattern-matching case

3.1 case ... matches and the first match

case (expression) matches treats each item as a pattern. Items are tried from top to bottom, and the first one that matches wins.

Syntax

case (expression) matches
  pattern1: statement
  pattern2 &&& condition: statement
  default: statement
endcase

3.2 Filters with &&&

A filter after &&& is evaluated only when the pattern has already matched, so it may use the names the pattern bound and the original expression. If the filter is false, matching continues with the next item.

Because patterns overlap, order matters. Put a specific item above a broader item that would accept the same values; otherwise the broad item takes those values first and the specific item never runs.

3.3 Example: pattern success versus filter failure

FilteredCase.bsv decodes an instruction byte. Read the one filtered item, then the default item, then the three calls in show. The literal 8'b1010_???? fixes the upper nibble to 1010 and ignores the lower nibble.

Predict before you run.

1. Which of small, large, and other comes from the filtered item?
2. large and other print the same number. Why is the reason different?

package FilteredCase;

function Bit#(4) decodeSmall(Bit#(8) instruction);
  // The literal wildcard matches every instruction with a 1010 prefix.
  case (instruction) matches
    // The filter runs only after the literal pattern succeeds.
    8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];
    default: return 0;
  endcase
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    $display("small=%0d large=%0d other=%0d",
             decodeSmall(8'ha7), decodeSmall(8'hac), decodeSmall(8'h37));
    $finish(0);
  endrule
endmodule

endpackage

Check the result. Only small=7 came from the filtered item. large=0 came from a pattern that matched and a filter that rejected it; other=0 came from a pattern that failed. The output cannot tell those two zeros apart, which is why the trace table above is worth writing down.

Try it yourself.

1. Change the filter bound from 10 to 13. Only 8'hac changes items, so large becomes 12 while small and other stay 7 and 0.
2. Keep the bound at 10 and insert a broad item 8'b1010_????: return 4'hf; above the filtered item. Both 8'ha7 and 8'hac stop there and print 15, so the filtered item is shadowed. Moving the broad item below the filtered item restores small=7 and sends only 8'hac to 15.

3.4 case expressions

A pattern-matching case can also be an expression that yields a value. Each item then ends with an expression instead of a statement.

Bit#(8) size = case (packet) matches
                 tagged Data .request: request.payload;
                 tagged Flush: 0;
               endcase;

Neither form checks that the items cover every input. As the nested-pattern variation showed, bsc accepts an incomplete set of items and produces an undefined value when nothing matches. End each case with default, or with items that together cover every member.

Read this function and decide which input it leaves without a result.

typedef union tagged { void Idle; Bit#(8) Load; Bit#(8) Store; } Op deriving (Bits, Eq);

function Bit#(8) opData(Op op);
  case (op) matches
    tagged Idle: return 0;
    tagged Load .v: return v;
  endcase
endfunction

4. Pattern tests in conditions

4.1 matches in if and in rule guards

if statements, conditional expressions, rule guards, and method guards accept a pattern test, optionally followed by more conditions joined with &&&.

Syntax

if (expression matches pattern &&& condition) statement
rule name (expression matches pattern &&& condition);

if (request matches tagged Write .address &&& address < 16)
  accept(address);

The terms are evaluated from left to right, and each one only after every earlier one succeeded. When address < 16 is evaluated, the tag is known to be Write and address has a value. The bound name is visible in the then branch, but not in the else branch, where the match may have failed; using it there is error T0004, "Unbound variable".

4.2 Why && cannot replace &&&

Plain && combines two Bool values that both already exist. It cannot make a pattern variable available to its right-hand side. The grammar enforces this: && directly after a matches pattern is parse error P0005, "Unexpected &&'; expected &&&' or )'". Inside a filter, after the &&&, plain &&` is fine.

5. match declarations

5.1 Taking apart a value whose shape is known

match pattern = expression; binds the pattern's variables for the rest of the block. Use it when the type already guarantees the shape, as with tuples and structs. There is nothing to choose between, so a case would only add noise.

Syntax

match pattern = expression;

match {.quotient, .remainder} = divide(a, b);   // tuple: by position
match Pair { lo: .x, hi: .y } = p;              // struct: by field name

5.2 Example: binding by position

MatchAssignment.bsv splits a Tuple2 into two four-bit names and joins them again. Read the type of fields, then the match line, then the concatenation that follows.

tuple2(4'ha, 4'h5) arrives as fields. The pattern {.upper, .lower} binds by position: the first member, 4'ha, becomes upper, and the second, 4'h5, becomes lower. Both have type Bit#(4) because their positions do. { upper, lower } places upper in bits 7 to 4.

Predict before you run.

1. Which byte is printed?
2. Were tpl_1 or tpl_2 needed to reach the members?

package MatchAssignment;

function Bit#(8) joinFields(Tuple2#(Bit#(4), Bit#(4)) fields);
  // Match assignment introduces both tuple fields for later statements.
  match {.upper, .lower} = fields;
  return { upper, lower };
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    $display("joined=%02h", joinFields(tuple2(4'ha, 4'h5)));
    $finish(0);
  endrule
endmodule

endpackage

Check the result. joined=a5 confirms that the first tuple member landed in the high nibble. No tpl_1 or tpl_2 call was needed, and both names kept their four-bit types in the next statement.

Try it yourself.

1. Swap the names in the pattern to {.lower, .upper} and leave the concatenation alone. The result becomes 5a: tuple patterns bind by position, so the names are labels for positions, not keys.
2. For contrast, a struct pattern such as Pair { lo: .x, hi: .y } binds by field name, so reordering its entries changes nothing.

6. Common mistakes

6.1 A broad item above a specific one

// Wrong: the filtered item is never reached
8'b1010_????: return 4'hf;
8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];

// Right: specific item first
8'b1010_???? &&& (instruction[3:0] < 10): return instruction[3:0];
8'b1010_????: return 4'hf;

The first item that matches wins. A broad item above a specific one takes every input the specific item was meant for, and bsc does not warn.

6.2 Missing a fallback item

// Wrong: a Data packet with channel 2 matches nothing
case (packet) matches
  tagged Data (Request { channel: 1, payload: .value }): return value;
  tagged Flush: return 0;
endcase

// Right: state the result for every other input
case (packet) matches
  tagged Data (Request { channel: 1, payload: .value }): return value;
  default: return 0;
endcase

Coverage is not checked. Without a fallback, the result for unmatched inputs is undefined.

6.3 Using && after a pattern

// Wrong: parse error P0005
if (request matches tagged Write .address && address < 16) ...

// Right: sequence the condition after the match
if (request matches tagged Write .address &&& address < 16) ...

address exists only after the match has succeeded, and only &&& waits for that.

6.4 Using a bound name in else

// Wrong: address is unbound in else (T0004)
if (request matches tagged Write .address) accept(address);
else log(address);

// Right: use only names that exist on that path
if (request matches tagged Write .address) accept(address);
else log(0);

In the else branch the request may not be a Write, so address has no value there.

6.5 Reusing a name in one pattern

// Wrong: compiles, but a holds the second member
match {.a, .a} = pair;

// Right: one name per position
match {.first, .second} = pair;

Current bsc accepts the wrong version. The later binding wins, and the pattern does not test whether the two members are equal.

7. Summary

8. Check your understanding

1. In payloadOrZero, what happens to the channel field, and why is no wildcard needed for it?

   Show answer

   It is never examined. A struct pattern checks only the fields it names, so leaving channel out is enough.

2. Two inputs print 0 in the filtered-case example. Which one matched the pattern?

   Show answer

   8'hac matched the pattern 8'b1010_????, but its filter 12 < 10 was false. 8'h37 failed the pattern itself. Both then reached default.

3. Where must a broad item go relative to a filtered item, and what happens if it goes the other way?

   Show answer

   Below it. If the broad item is above, it matches every input the filtered item would have accepted, and the filtered item never runs.

4. Why can address < 16 use address after &&&, and what happens with &&?

   Show answer

   &&& evaluates its right side only after the match has succeeded and bound address. With &&, bsc stops with parse error P0005, expecting &&&.

5. When is a match declaration a better choice than case ... matches?

   Show answer

   When the type already guarantees the shape, as with a tuple or a struct. There is no alternative to choose, so the declaration only names the parts.