Just An Application

October 28, 2014

So Swift Then: More Fun With Mangled Names Continued

Function Type Encoding: A Model In Swift

Type Encoding

Encodeable

We start by defining the Encodeable protocol

    protocol Encodeable
    {
        func encode(encoder:Encoder) -> String
    }

Type

A Type must be encodeable. That’s it at the moment.

    protocol Type: Encodeable
    {
    }

Builtin Types

Built in types are represented by the enum BuiltinType

We will assume that the Encoder is responsible for knowing how built-in types are actually encoded.

    enum BuiltinType: Type
    {
        case ArrayType
        case BoolType
        case DoublgType
        case IntType
        case OptionalType
        case StringType
        case UintType
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            return encoder.encode(self)
        }
    }

Generic Types

Generic types are represented by sub-classes of GenericType.

A generic type encodes itself.

    class GenericType: Type
    {
        init(baseType:Type, parameterTypes:Type...)
        {
            self.baseType       = baseType
            self.parameterTypes = parameterTypes
        }
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            var encoding = "G"
    
            encoding += baseType.encode(encoder)
            for t in parameterTypes
            {
                encoding += t.encode(encoder)
            }
            encoding += "_"
            return encoding
        }
    
        //
    
        private let baseType        : Type
        private let parameterTypes  : [Type]
    }

Array Types

Array types are represented by instances of the class ArrayType

    final class ArrayType: GenericType
    {
        init(elementType:Type)
        {
            super.init(baseType:BuiltinType.ArrayType, parameterTypes:elementType)
        }
    }

Optional Types

Optional types are represented by instances of the class OptionalType

    final class OptionalType: GenericType
    {
        init(type:Type)
        {
            super.init(baseType:BuiltinType.OptionalType, parameterTypes:type)
        }
    }

Tuple Types

The Empty Tuple Type

The type of the empty tuple

    ()

is represented by an instance of the class EmptyTupleType

    final class EmptyTupleType: TupleType
    {
        func encode(encoder:Encoder) -> String
        {
            return "T_"
        }
    }

    typealias VoidType = EmptyTupleType

Single Element Tuple Types

The type of a tuple with a single unnamed element is represented by an instance of the class SingleElementTupleType

    final class SingleElementTupleType: TupleType
    {
        init(elementType:Type)
        {
            self.elementType = elementType
        }
        
        //

        func encode(encoder:Encoder) -> String
        {
            return elementType.encode(encoder)
        }

        //

        private let elementType: Type
    }

It encodes itself by returning the encoding of its element type.

Multi Element Tuple Types

The type of any tuple which has more than one element is represented by an instance of the class MultiElementTupleType

    final class MultiElementTupleType: TupleType
    {
        init(first:TupleElementType, second:TupleElementType, rest:[TupleElementType])
        {
            var elementTypes = [first, second]
    
            elementTypes += rest
            self.elementTypes = elementTypes
        }
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            var encoding = "T"
    
            for et in elementTypes
            {
                encoding += e.encode(encoder)
            }
            encoding += "_"
            return encoding
        }
    
        //
    
        private let elementTypes: [TupleElementType]
    }

The type of a tuple element is represented by an instance of the enum TupleElementType

    enum TupleElementType: Encodeable
    {
        case NameAndType(String, Type)
        case TypeOnly(Type)
    
        func encode(encoder:Encoder) -> String
        {
            switch self
            {
                case let .NameAndType(name, type):
    
                    var encoding = ""
    
                    encoding += encoder.encode(name)
                    encoding += type.encode(encoder)
                    return encoding
    
                case let .TypeOnly(type):
    
                    return type.encode(encoder)
            }
        }
    }
    

Function Type Encoding

The encoding of a function type is the encoding of its parameters immediately followed by the encoding of its return type.

A function’s parameters are encoded as though they comprise a tuple type.

To do this for certain function parameters we need two additional ‘synthetic’ tuple types.

Synthetic Tuple Types

Single Named Element Tuple Types

The compiler refuses to acknowledge the existence of single named element tuple types.

We need to encode a parameter with an external name as though it were one so we define the class SingleNamedElementTupleType

    final class SingleNamedElementTupleType: TupleType
    {
        init(name:String, type:Type)
        {
            self.name = name
            self.type = type
        }
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            var encoding = "T"
    
            encoding += encoder.encode(name)
            encoding += type.encode(encoder)
            encoding += "_"
            return encoding
        }
    
        //
    
        private let name:   String
        private let type:   Type
    }

Varadic Tuple Types

To represent a function’s parameters as a tuple type when that function has a varadic parameter we need a ‘varadic tuple’ type.

A ‘varadic tuple’ type is represented by an instance of the class

    final class VaradicTupleType: TupleType
    {
        init(var elementTypes:[TupleElementType])
        {
            assert(elementTypes.count != 0)
            
            var last : TupleElementType

            switch elementTypes.removeLast()
            {
                case let .NameAndType(name, type):

                    last = TupleElementType.NameAndType(
                                                name,
                                                ArrayType(
                                                    elementType:type)))

                case let .TypeOnly(type):

                    last = TupleElementType.TypeOnly(
                                                ArrayType(
                                                    elementType:type)))
            }
            elementTypes.append(last)
            self.elementTypes = elementTypes
        }

        //

        func encode(encoder:Encoder) -> String
        {
            var encoding = "t"

            for et in elementTypes
            {
                encoding += et.encode(encoder)
            }
            encoding += "_"
            return encoding
        }

        //

        private let elementTypes : [TupleElementType]
    }

Parameter Tuple Element Types

Vanilla

A vanilla parameter of type T is represented by an instance of

    TupleElementType.TypeOnly

For example

    i : Int

is represented by

    TupleElementType.TypeOnly(BuiltinType.IntType)

External Names

A parameter with an external name is represented by an instance of

    TupleElementType.NameAndType

For example

    e i : Int

is represented by

    TupleElementType.NameAndType("e", "BuiltinType.IntType)

inout

The type of an inout parameter is represented by an instance of the class ReferenceType.

    final class ReferenceType: Type
    {
        init(type:Type)
        {
            self.type = type
        }
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            return "R" + type.encode(encoder)
        }
    
        //
    
        private let type: Type
    }

If it does not have an ‘external name’ the parameter is represented by an instance of

    TupleElementType.TypeOnly

or by an instance of

    TupleElementType.NameAndType

otherwise.

Varadic

If a function has a varadic parameter then its parameters are represented by an instance of the class VaradicTupleType.

The parameter itself is represented by an instance of ArrayType.

Function Types

A function type is represented by an instance of the class FunctionType.

   final class FunctionType: Type
    {
        init(parameters:TupleType, returnType:TupleType)
        {
            self.parameters = parameters
            self.returnType = returnType
        }
    
        //
    
        func encode(encoder:Encoder) -> String
        {
            var encoding = "F"
    
            encoding += parameters.encode(encoder)
            encoding += returnType.encode(encoder)
            return encoding
        }
    
        //
    
        private let parameters: TupleType
        private let returnType: TupleType
    }

Other Types

Of the other types we have seen class, enum and struct types can all be represented by sub-classes of NamedType.

    class NamedType: Type
    {
        init(prefix:String, name:Name)
        {
            self.prefix = prefix
            self.name   = name
        }
    
        func encode(encoder:Encoder) -> String
        {
            return encoder.encode(prefix:prefix, name:name)
        }
    
        private let prefix: String
        private let name:   Name
    }

The actual encoding of the names is done by the Encoder. This makes it possible for the Encoder to replace the name of the type with a substitution pattern
when appropriate.

The type names are represented by instances of the enum Name.

    enum Name
    {
        case Local([String])
        case External([String])
        case Swift([String])
    }

The representation of the protocol type is left as an exercise for the reader.

Some Examples

Starting with the obvious one

    let encoder = Encoder()
    let builder = FunctionTypeBuilder()
    
    let ft0001 = builder.build()
    
    println(ft0001.encode(encoder))

prints

    FT_T_

So far so good.

Some return types.

An integer

    let ft0002 = builder.returnType(BuiltinType.IntType).build()
    
    println(ft0002.encode(encoder))

prints

    FT_Si

An array of integers

    let ft0003 = builder.returnType(ArrayType(elementType:BuiltinType.IntType)).build()
    
    println(ft0003.encode(encoder))

prints

    FT_GSaSi_

An optional integer

    let ft0004 = builder.optionalReturnType(BuiltinType.IntType).build()

    println(ft0004.encode(encoder))

prints

    FT_GSqSi_

A single unnamed element tuple

    let ft0005 = builder.tupleReturnType(BuiltinType.IntType).build()
    
    println(ft0005.encode(encoder))

prints

    FT_Si

A multiple element tuple

    let ft0006 = builder.tupleReturnType(BuiltinType.IntType, BuiltinType.IntType).build()
    
    println(ft0006.encode(encoder))

prints

    FT_TSiSi_

A named element tuple

    let ft0007 = builder.namedTupleReturnType((name:"x", type:BuiltinType.IntType), rest:(name:"y", type:BuiltinType.IntType)).build()
    
    println(ft0007.encode(encoder))

prints

    FT_T1xSi1ySi_

Some parameters

An integer parameter

    let ft1000 = builder.param(BuiltinType.IntType).build()

    println(ft1000.encode(encoder))

prints

    FSiT_

An integer parameter with an external name

    let ft1001 = builder.param(externalName:"e", type:BuiltinType.IntType).build()

    println(ft1001.encode(encoder))

prints

    FT1eSi_T_

Two integer parameters

    let ft1002 = builder.param(BuiltinType.IntType).param(BuiltinType.IntType).build()

    println(ft1002.encode(encoder))

prints

    FTSiSi_T_

An inout integer parameter

    let ft1003 = builder.inoutParam(BuiltinType.IntType).build()

    println(ft1003.encode(encoder))

prints

    FRSiT_

An integer parameter and an inout integer parameter

    let ft1004 = builder.param(BuiltinType.IntType).inoutParam(BuiltinType.IntType).build()

    println(ft1004.encode(encoder))

prints

    FTSiRSi_T_

A single unnamed element tuple

    let ft1005 = builder.tupleTypeParam(BuiltinType.IntType).build()

    println(ft1005.encode(encoder))

prints

    FSiT_

A multiple unnamed element tuple

    let ft1006 = builder.tupleTypeParam(BuiltinType.IntType, BuiltinType.IntType).build()

    println(ft1006.encode(encoder))

prints

    FTSiSi_T_

Conclusions

The model is based on two simple assumptions

  1. a single unnamed element tuple type is encoded as the type of its element, and

  2. a function’s parameters are encoded as though they comprised a tuple type

The resulting behaviour seems to be accurate up to and including generating the same encodings for ostensibly ‘different’ sets of function parameters.


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.

Advertisements

2 Comments »

  1. […] we have a model of how function types are encoded lets see if we can break […]

    Pingback by So Swift Then: Mangled Function Names And Function Types — Function Types Go Recursive | Just An Application — October 29, 2014 @ 4:11 pm

  2. […] have a model of how function types are encoded when function names are […]

    Pingback by The Curried Function Type Encoding Mystery | Just An Application — October 31, 2014 @ 1:29 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: