Thursday, October 30, 2008

Using F# Active Patterns to encapsulate complex conditions

In this post I'm going to show a little of example of using F# Active Patterns to encapsulate complex conditions.


While working on AbcExplorationLib I needed way to generate "friendly" labels for branch instruction destinations. According to the ActionScript Virtual Machine 2 Overview document, the branch instructions (jump,ifgt,ifeq,etc.) have a S24(signed 24 bit value) offset that specifies the destination. What I wanted to do was to modify the original instruction list to add a special(non existent ) instruction called ArtificalCodeBranchLabel which has a name which is referenced in the in the branch instruction.

Every branch instruction in the library representation has an object of type:


type JumpLabelReference =
| UnSolvedReference of int
| SolvedReference of string


Every instruction in the library is described in a big discriminated union like this:


type AbcFileInstruction =
| ArtificalCodeBranchLabel of string
| Add
| AsType of int
| BitAnd
| BitNot
| BitOr
| BitXor
...
| IfEq of JumpLabelReference
| IfFalse of JumpLabelReference
| IfGe of JumpLabelReference
| IfGt of JumpLabelReference
| IfLe of JumpLabelReference
...


Notice that essentially, every branch instruction(except for lookupswitch) have a single JumpLabelReference instance as its argument, and in order to write the process of solving the branch destination we can have to write code for each instruction.

So in order to assist the process of solving the reference the following active pattern was created:


let (|UnsolvedSingleBranchInstruction|_|)(pair:int64*AbcFileInstruction) =
let (instructionOffset,instruction) = pair in
let absoluteOffset(relativeOffset:int) = int64(3 + 1 + relativeOffset) + instructionOffset in
let result(offset,createFunction) = Some(absoluteOffset <| offset,createFunction)
in
match instruction with
| IfEq(UnSolvedReference offset) -> result(offset,fun o -> IfEq(o))
| IfFalse(UnSolvedReference offset) -> result(offset,fun o -> IfFalse(o))
| IfGe(UnSolvedReference offset) -> result(offset,fun o -> IfGe(o))
| IfGt(UnSolvedReference offset) -> result(offset,fun o -> IfGt(o))
| IfLe(UnSolvedReference offset) -> result(offset,fun o -> IfLe(o))
| IfLt(UnSolvedReference offset) -> result(offset,fun o -> IfLt(o))
| IfNGe(UnSolvedReference offset) -> result(offset,fun o -> IfNGe(o))
| IfNGt(UnSolvedReference offset) -> result(offset,fun o -> IfNGt(o))
| IfNLe(UnSolvedReference offset) -> result(offset,fun o -> IfNLe(o))
| IfNLt(UnSolvedReference offset) -> result(offset,fun o -> IfNLt(o))
| IfNE(UnSolvedReference offset) -> result(offset,fun o -> IfNE(o))
| IfStrictEq(UnSolvedReference offset) -> result(offset,fun o -> IfStrictEq(o))
| IfStrictNEq(UnSolvedReference offset) -> result(offset,fun o -> IfStrictNEq(o))
| IfTrue(UnSolvedReference offset) -> result(offset,fun o -> IfTrue(o))
| Jump(UnSolvedReference offset) -> result(offset,fun o -> Jump(o))
| _ -> None


This active pattern is used for a couple of things. First, it matches every branch instruction and provides a function to rebuild the instruction with a new destination. Also it calculates the absolute offset of the branch instruction.

Now we can use it in the process of solving the references:


member this.UpdateCodeWithDestinations(destinations:Map<int64,string>,
instructions,
resultingInstructions) =
let processedInstructions =
match instructions with
| (((offset,_) & UnsolvedSingleBranchInstruction( jumpOffset,f))::rest)
when (destinations.ContainsKey(jumpOffset)) ->
(offset,f(SolvedReference(destinations.[jumpOffset])))::rest
| _ -> instructions
in
match processedInstructions with
| ((offset,instruction)::rest) when (destinations.ContainsKey(int64(offset))) ->
this.UpdateCodeWithDestinations(destinations,
rest,
instruction::ArtificalCodeBranchLabel(destinations.[int64(offset)])::resultingInstructions)
| ((_,instruction)::rest) ->
this.UpdateCodeWithDestinations(destinations,
rest,
instruction::resultingInstructions)
| [] -> List.rev(resultingInstructions)


Although this problem could be expressed using other strategies (for example a separate class for each instruction and branch instructions inheriting from the same base class) the use of Active Patterns was very useful to write a simpler implementation of the UpdateCodeWithDestinations method.