动手实现 NSNumber

#Original (English)

Source: https://www.mikeash.com/pyblog/friday-qa-2012-07-06-lets-build-nsnumber.html

NSNumber is a deceptively simple class with some interesting implementation details. In today’s edition of Friday Q&A, I’ll explore how to build a class that works like NSNumber, a topic suggested by Jay Tamboli.

OverviewLike many (but not all) object-oriented languages, Objective-C has a divide between objects and non-objects. Objects respond to messages, can be queried at runtime without knowing their exact type, placed in collections, compared for equality, and share a common set of behavior. Non-objects are largely compile-time constructs, with all of their type information essentially gone at runtime. In Objective-C, these non-objects are everything that comes from C, from the integer 42 to the string “Hello, world” to complicated structs.

Boxing is the process of placing these non-objects into an object so that they can be used like other objects, typically so that they can be placed in a collection. NSNumber is the Cocoa class used to box C numbers. You can’t have an NSArray of int, but you can have an NSArray of NSNumber. NSNumber shows up a lot in Cocoa programming. Just about any place a Cocoa collection is used to store a number, NSNumber is there. Among many other places, NSNumber objects are what NSUserDefaults stores and retrieves when you ask it to save a number.

InterfaceOur surrogate NSNumber will be called MANumber. Unlike the Cocoa version, which is a subclass of the more general boxing class NSValue, this one will directly subclass NSObject:

1
    @interface MANumber : NSObject

There are a lot of methods for initializing an instance. There’s one initializer for each C numeric type, plus some extra ones for types specific to Cocoa:

1
    - (id)initWithChar:(char)value;
2
    - (id)initWithUnsignedChar:(unsigned char)value;
3
    - (id)initWithShort:(short)value;
4
    - (id)initWithUnsignedShort:(unsigned short)value;
5
    - (id)initWithInt:(int)value;
6
    - (id)initWithUnsignedInt:(unsigned int)value;
7
    - (id)initWithLong:(long)value;
8
    - (id)initWithUnsignedLong:(unsigned long)value;
9
    - (id)initWithLongLong:(long long)value;
10
    - (id)initWithUnsignedLongLong:(unsigned long long)value;
11
    - (id)initWithFloat:(float)value;
12
    - (id)initWithDouble:(double)value;
13
    - (id)initWithBool:(BOOL)value;
14
    - (id)initWithInteger:(NSInteger)value;
15
    - (id)initWithUnsignedInteger:(NSUInteger)value;

There are also getters for these types:

1
    - (char)charValue;
2
    - (unsigned char)unsignedCharValue;
3
    - (short)shortValue;
4
    - (unsigned short)unsignedShortValue;
5
    - (int)intValue;
6
    - (unsigned int)unsignedIntValue;
7
    - (long)longValue;
8
    - (unsigned long)unsignedLongValue;
9
    - (long long)longLongValue;
10
    - (unsigned long long)unsignedLongLongValue;
11
    - (float)floatValue;
12
    - (double)doubleValue;
13
    - (BOOL)boolValue;
14
    - (NSInteger)integerValue;
15
    - (NSUInteger)unsignedIntegerValue;

Note that any of these getters works no matter which initializer was used. MANumber will have to perform the appropriate conversions.

Finally, there are a few other methods for string conversion and comparison:

1
    - (NSString *)stringValue;
2
    - (NSComparisonResult)compare:(MANumber *)otherNumber;
3
    - (BOOL)isEqualToNumber:(MANumber *)number;
4
    - (NSString *)descriptionWithLocale:(id)locale;

Implementation StrategyMANumber will use a union to store the underlying numeric value. union is a rarely-seen feature of standard C. It looks just like a struct, but works differently. A struct stores many values together in one spot. A union does this as well, but you can only access the last one you stored. When you store a value in a union, the value of all other fields becomes undefined.

In typical unhelpful-but-efficient C fashion, the compiler doesn’t enforce that rule, nor does it help you follow it by, say, letting you query which field was the last one set. You have to keep track of this yourself, typically with an accompanying enum.

The union could be used to hold every C numeric type, with a big enum to say which one is in use. However, this is unnecessarily complex. All we really need is three fields: the largest possible integer type, the largest possible unsigned integer type, and the largest possible floating-point type. From the types we have to handle, these are long long, unsigned long long, and double. Everything else can be converted to and from those without loss.

This implementation does not precisely match that of NSNumber, which keeps track of the specific type used to create it. However, using these three types is plenty close enough, and eliminates a lot of extra repetitive code. The fact that NSNumber precisely tracks the original type isn’t visible most of the time, and only shows up when using a method like -descriptionWithLocale: or -objCType.

StorageHere are the instance variables:

1
    @implementation MANumber {
2
        enum { INT, UINT, DOUBLE } _type;
3
        union {
4
            long long i;
5
            unsigned long long u;
6
            double d;
7
        } _value;
8
    }

The _type variable holds an anonymous enum saying whether the value is an INT (long long), UINT (unsigned long long), or DOUBLE (guess). The _value variable then holds the actual number, using a union so that it only ends up storing one.

The code will set _type and the corresponding _value in the initializers. The getters can then check the _type and extract the value accordingly.

InitializersThere’s a ton of boilerplate to deal with all of the different types. All of the signed integer types just call through to initWithLongLong:, and the unsigned types call through to initWithUnsignedLongLong:

1
    - (id)initWithChar:(char)value
2
    {
3
        return [self initWithLongLong: value];
4
    }
5

6
    - (id)initWithUnsignedChar:(unsigned char)value
7
    {
8
        return [self initWithUnsignedLongLong: value];
9
    }
10

11
    - (id)initWithShort:(short)value
12
    {
13
        return [self initWithLongLong: value];
14
    }
15

16
    - (id)initWithUnsignedShort:(unsigned short)value
17
    {
18
        return [self initWithUnsignedLongLong: value];
19
    }
20

21
    - (id)initWithInt:(int)value
22
    {
23
        return [self initWithLongLong: value];
24
    }
25

26
    - (id)initWithUnsignedInt:(unsigned int)value
27
    {
28
        return [self initWithUnsignedLongLong: value];
29
    }
30

31
    - (id)initWithLong:(long)value
32
    {
33
        return [self initWithLongLong: value];
34
    }
35

36
    - (id)initWithUnsignedLong:(unsigned long)value
37
    {
38
        return [self initWithUnsignedLongLong: value];
39
    }
40

41
    - (id)initWithBool:(BOOL)value
42
    {
43
        return [self initWithLongLong: value];
44
    }
45

46
    - (id)initWithInteger:(NSInteger)value
47
    {
48
        return [self initWithLongLong: value];
49
    }
50

51
    - (id)initWithUnsignedInteger:(NSUInteger)value
52
    {
53
        return [self initWithUnsignedLongLong: value];
54
    }

Those initialisers then simply set the _type, _value, and return self. (Note that I’m leaving out the traditional call to [super init] for brevity, as it’s not strictly necessary when your superclass is NSObject, although still a good idea.)

1
    - (id)initWithLongLong:(long long)value
2
    {
3
        _type = INT;
4
        _value.i = value;
5
        return self;
6
    }
7

8
    - (id)initWithUnsignedLongLong:(unsigned long long)value
9
    {
10
        _type = UINT;
11
        _value.u = value;
12
        return self;
13
    }

The floating-point initializers are similar. The one for float just calls through to initWithDouble:, and that one just sets _type and _value appropriately:

1
    - (id)initWithFloat:(float)value
2
    {
3
        return [self initWithDouble: value];
4
    }
5

6
    - (id)initWithDouble:(double)value
7
    {
8
        _type = DOUBLE;
9
        _value.d = value;
10
        return self;
11
    }

GettersThe getters are even more similar then the initializers. They all check the _type, then return the appropriate field of _value. The compiler will handle the final conversion from the active field of _value to the requested return type.

Since these methods all contain the same code, this is a perfect candidate for a macro to encapsulate the identical bits. Here’s a macro that checks _type and then returns the corresponding field of _value:

1
    #define RETURN() do { \
2
            if(_type == INT) \
3
                return _value.i; \
4
            else if(_type == UINT) \
5
                return _value.u; \
6
            else \
7
                return _value.d; \
8
        } while(0)

With that macro, the getters pretty much write themselves:

1
    - (char)charValue
2
    {
3
        RETURN();
4
    }
5

6
    - (unsigned char)unsignedCharValue
7
    {
8
        RETURN();
9
    }
10

11
    - (short)shortValue
12
    {
13
        RETURN();
14
    }
15

16
    - (unsigned short)unsignedShortValue
17
    {
18
        RETURN();
19
    }
20

21
    - (int)intValue
22
    {
23
        RETURN();
24
    }
25

26
    - (unsigned int)unsignedIntValue
27
    {
28
        RETURN();
29
    }
30

31
    - (long)longValue
32
    {
33
        RETURN();
34
    }
35

36
    - (unsigned long)unsignedLongValue
37
    {
38
        RETURN();
39
    }
40

41
    - (long long)longLongValue
42
    {
43
        RETURN();
44
    }
45

46
    - (unsigned long long)unsignedLongLongValue
47
    {
48
        RETURN();
49
    }
50

51
    - (float)floatValue
52
    {
53
        RETURN();
54
    }
55

56
    - (double)doubleValue
57
    {
58
        RETURN();
59
    }
60

61
    - (NSInteger)integerValue
62
    {
63
        RETURN();
64
    }
65

66
    - (NSUInteger)unsignedIntegerValue
67
    {
68
        RETURN();
69
    }

That’s a lot of boring and ugly code.

The one exception to this uniform sea of macro invocations is the -boolValue method. Since BOOL pretends to be a real boolean value, this method should always return YES for any non-zero value stored in the MANumber object. The compiler’s built-in conversion won’t do this. For example, the integer 256 will return NO if converted to a BOOL, since BOOL is just a signed char, which is an 8-bit integer. Because of that, -boolValue replicates the macro logic, but with an explicit check for zero:

1
    - (BOOL)boolValue
2
    {
3
        if(_type == INT)
4
            return _value.i != 0;
5
        else if(_type == UINT)
6
            return _value.u != 0;
7
        else
8
            return _value.d != 0;
9
    }

String ConversionThere are two string conversion methods: -stringValue and -descriptionWithLocale:. -stringValue simply calls -descriptionWithLocale: with a nil parameter:

1
    - (NSString *)stringValue
2
    {
3
        return [self descriptionWithLocale: nil];
4
    }

-descriptionWithLocale: then uses -[NSString initWithFormat:locale:] to build the string. There’s no fancy way to deal with the different numeric types here, so it simply checks _type and uses a different format string for each case:

1
    - (NSString *)descriptionWithLocale:(id)locale
2
    {
3
        if(_type == INT)
4
            return [[NSString alloc] initWithFormat: @"%lld" locale: locale, _value.i];
5
        else if(_type == UINT)
6
            return [[NSString alloc] initWithFormat: @"%llu" locale: locale, _value.u];
7
        else
8
            return [[NSString alloc] initWithFormat: @"%f" locale: locale, _value.d];
9
    }

Note that I’m using ARC, which is why there are no autorelease calls here.

ComparisonThe comparison methods get interesting, because they need to work between MANumber objects of different types. For example, the double value -1.1 should compare less than the unsigned integer value 99999.

There are nine permutations of the types, so nine different cases to handle. This can be reduced to only six cases by enforcing an order. If the two objects have types INT and UINT, the two cases for that can be reduced to one by only handling the case where self is INT and the other object is UINT, and swapping the two objects if they show up the other way around.

To help with comparison between the different types, I wrote a simple macro that takes two numbers and returns the appropriate NSComparisonResult. All it does is take two arguments, save them into temporary variables to avoid multiple evaluation, then return the appropriate constant depending on how they’re ordered. There’s also a bit of floating-point trickery here. With floating-point numbers, NAN (not a number) never compares equal to anything, and all comparisons with it are false. Since NSComparisonResult has no way to represent an ordering which means, “this number is not equal to anything, not even itself,” I arbitrarily decide to make NAN equal to itself and less than any other number, for the purposes of MANumber comparison:

1
    #define COMPARE(a, b) do { \
2
            __typeof__(a) __a_local = a; \
3
            __typeof__(b) __b_local = b; \
4
            BOOL __a_isnan = isnan(__a_local); \
5
            BOOL __b_isnan = isnan(__b_local); \
6
            if(__a_isnan && __b_isnan) \
7
                return NSOrderedSame; \
8
            else if(__a_isnan) \
9
                return NSOrderedAscending; \
10
            else if(__b_isnan) \
11
                return NSOrderedDescending; \
12
            else if(__a_local > __b_local) \
13
                return NSOrderedDescending; \
14
            else if(__a_local < __b_local) \
15
                return NSOrderedAscending; \
16
            else \
17
                return NSOrderedSame; \
18
        } while(0)

The first thing the comparison method itself does is extract the types of the two objects to compare:

1
    - (NSComparisonResult)compare:(MANumber *)otherNumber
2
    {
3
        int selfType = _type;
4
        int otherType = otherNumber->_type;

If the two types aren’t in order, we reverse the comparison by calling compare: again with the arguments reversed, and returning the inverse of the result. Since NSComparisonResult is just -1, 0, or 1, we can invert its meaning by negating it:

1
        if(selfType > otherType)
2
            return -[otherNumber compare: self];

Now we’re left with sorted types. There are six cases. If selfType is INT, then otherType could be anything. If selfType is UINT, then otherType can only be UINT or DOUBLE. If selfType is DOUBLE, then otherType must be DOUBLE as well.

Let’s look at the cases where selfType is INT. If both values are INT, the code is easy:

1
        if(selfType == INT)
2
        {
3
            if(otherType == INT)
4
            {
5
                COMPARE([self longLongValue], [otherNumber longLongValue]);
6
            }

If otherType is UINT, there’s a bit of extra work. Directly comparing with [otherNumber unsignedLongLongValue] won’t work. C will promote [self longLongValue] to unsigned before the comparison, turning negative numbers into positive numbers and wrecking the comparison. -1 will compare greater than 1 because of this. To prevent that, we make a special check for negative numbers, then compare their unsigned values if both are known to be positive:

1
            else if(otherType == UINT)
2
            {
3
                if([self longLongValue] < 0)
4
                    return NSOrderedAscending;
5
                else
6
                    COMPARE([self unsignedLongLongValue], [otherNumber unsignedLongLongValue]);
7
            }

Next comes the case for DOUBLE. This gets pretty complicated, because floating-point numbers work fairly differently from integers. There are several different subcases here, which I’ll take one by one. However, the first thing it does is extract the doubleValue from the other number to make it more convenient to work with:

1
            else
2
            {
3
                double other = [otherNumber doubleValue];

double can hold a much larger range than long long. The first subcase is to figure out the largest possible number a long long can hold, and see if other is beyond it. If it is, it’s obviously larger than self, since self is a long long.

The built-in macro LLONG_MAX gives us the largest number a long long can hold. However, we can’t directly convert this to a double. That number is equal to 263-1, which can’t be represented in a double. Due to the internal format of double, it can only represent even numbers when it gets beyond 254. To perform the comparison accurately, we calculate one number beyond the largest long long, careful to use an unsigned one when adding, and compare against that:

1
                double longLongMaxPlusOne = LLONG_MAX + 1ULL;
2
                if(other >= longLongMaxPlusOne)
3
                    return NSOrderedAscending;

We also check in the negative direction. This is a bit easier, as the smallest possible long long can be directly represented in a double:

1
                if(other < LLONG_MIN)
2
                    return NSOrderedDescending;

If we’re still running at this point, then the double is within the range of a long long and they need to be compared directly. However, we can’t just whip out the > operator, because there are a lot of doubles that can’t be represented in long long (e.g. 1.5), and there are a lot of long longs that can’t be represented as a double (e.g. any odd number above a threshold, as mentioned above).

Beyond a certain threshold, double can only represent integer values, as the magnitude of the value exceeds the precision of the representation. When beyond that threshold, and below the maximum possible long long, the double can safely be converted to a long long with no loss of precision. The two values can then be compared as long longs. Below that threshold, double can represent any integer, and so the long long can safely be converted to a double with no loss of precision, and the two values compared as doubles.

The location of that threshold is actually fairly easy to figure out. C provides a macro, DBL_MANT_DIG, which gives the precision of the double type. By raising that to a power of two (since double is a binary representation), we get the threshold:

1
                double pureIntegerStart = 1LL << DBL_MANT_DIG;

Then we simply compare based on where other lies relative to that. Note that the threshold applies equally for negative numbers, so we must check it in both directions:

1
                if(other >= pureIntegerStart || other <= -pureIntegerStart)
2
                    COMPARE([self longLongValue], (long long)other);
3
                else
4
                    COMPARE([self doubleValue], other);
5
            }
6
        }

Next up comes the case where selfType is UINT. As before, when otherType is also UINT, the code is easy:

1
        else if(selfType == UINT)
2
        {
3
            if(otherType == UINT)
4
            {
5
                COMPARE([self unsignedLongLongValue], [otherNumber unsignedLongLongValue]);
6
            }

Note that we don’t have to handle INT, due to the type sorting performed above. We move on to DOUBLE, which is once again complicated. As before, we fetch the value of otherNumber into a local variable:

1
            else
2
            {
3
                double other = [otherNumber doubleValue];

The first thing we do is see if other is negative. If it is, then we know the order, as self is unsigned (and thus either zero or positive):

1
                if(other < 0)
2
                    return NSOrderedDescending;

Otherwise, we do the same basic threshold calculations as before. This time we have to compare other against the largest possible unsigned long long. Doing this is a bit tricky. Just like with long long, we have to add 1 to get a number that works as a double. However, we can’t represent anything greater than the largest possible unsigned long long as an integer, since unsigned long long is the largest integer type we have. Instead, we calculate (LLONG_MAX + 1) * 2, which gives one greater than the largest unsigned long long, carefully doing so with all the right types to avoid overflow or imprecision:

1
                double unsignedLongLongMaxPlusOne = (double)(LLONG_MAX + 1ULL) * 2.0;
2
                if(other >= unsignedLongLongMaxPlusOne)
3
                    return NSOrderedAscending;

At this point, we know that both numbers are within each type’s range, and so we use the same pureIntegerStart strategy as before to compare them directly:

1
                double pureIntegerStart = 1LL << DBL_MANT_DIG;
2
                if(other >= pureIntegerStart)
3
                    COMPARE([self unsignedLongLongValue], (unsigned long long)other);
4
                else
5
                    COMPARE([self doubleValue], other);
6
            }
7
        }

All that’s left now is the DOUBLE case, which is actually really easy. Due to the type sorting, the only possible case here is when they’re both DOUBLE, so we can just directly compare them:

1
        else
2
        {
3
            COMPARE([self doubleValue], [otherNumber doubleValue]);
4
        }
5
    }

Now that compare: implemented, equality checking is trivial:

1
    - (BOOL)isEqualToNumber:(MANumber *)number
2
    {
3
        return [self compare: number] == NSOrderedSame;
4
    }

We also want isEqual: from NSObject. This can simply check the class of the other object, then leverage isEqualToNumber:

1
    - (BOOL)isEqual: (id)other
2
    {
3
        if(![other isKindOfClass: [MANumber class]])
4
            return NO;
5

6
        return [self isEqualToNumber: other];
7
    }

Finally, since we override isEqual:, we must also override hash. The implementation of hash gets mildly tricky due to the semantics of floating-point numbers. For non-floats, we can simply return the straight integer value as the hash:

1
    - (NSUInteger)hash
2
    {
3
        if(_type != DOUBLE)
4
            return [self unsignedIntegerValue];

For floats that are integer values, we want to do the same thing. Since our isEqual: considers an integer-valued DOUBLE equal to an INT or UINT of the same value, we must return the same hash as the INT and UINT equivalent. To accomplish this, we check to see if the DOUBLE value is actually an integer, and return the integer value if so:

1
        if(_value.d == floor(_value.d))
2
            return [self unsignedIntegerValue];

Beyond this, we have non-integer values. The ultimate goal is to simply return the bit pattern of the double, which will give a nice hash. However, this only works for numbers where bit pattern equality implies isEqual:. This is not true for all doubles. First is NAN, which we made compare equal to itself, but which has many different possible bit representations. To handle that, we check for NAN explicitly and return a constant hash for it:

1
        if(isnan(_value.d))
2
            return 0;

The other special case is a bit weirder. IEEE 754 floats (the kind used by just about any modern CPU) have two possible values for zero: positive and negative. These are typically indistinguishable, as they compare equal and produce the same results for most calculations. However, they have different bit patterns, so we have to special-case them. I take advantage of the fact that negative zero compares equal to positive zero to make a simple check and return a constant hash for both zeroes:

1
        if(_value.d == 0.0)
2
            return 0;

Having ruled out all the special cases, if the code reaches this point then the number must be one where numerical equality is the same as bit pattern equality. Thus we simply return the bit pattern for the hash. We do this by returning the u field of the union:

1
        return _value.u;
2
    }

But wait! Previously I said that you’re not allowed to access any field in a union besides the one that was last set, so this is clearly not allowed. While technically correct according to the language spec, C compilers have generally settled on allowing it and simply reinterpreting the existing value. This code takes the double that’s stored in the union and reinterprets its bits as an unsigned long long, which is exactly what we want. Technically this relies on undefined behavior, but it’s officially blessed by the compilers we’re actually using.

ConclusionNSNumber is a conceptually simple class which mainly exists so that we can stuff numeric values into Cocoa collections, but its flexibility implies a fair amount of underlying complication. By implementing a workalike MANumber class, we can see what kinds of things NSNumber has to be doing on the inside. Automatic conversion to different integer types requires a fair amount of boilerplate code, and reliable conversion between number of different types can get pretty complicated.

That’s it for today. Come back next time for yet another Friday Q&A. As always, Friday Q&A is driven by reader suggestions, so if you have a topic you’d like to see covered, please send it in!