1"""biplist -- a library for reading and writing binary property list files.
2
3Binary Property List (plist) files provide a faster and smaller serialization
4format for property lists on OS X. This is a library for generating binary
5plists which can be read by OS X, iOS, or other clients.
6
7The API models the plistlib API, and will call through to plistlib when
8XML serialization or deserialization is required.
9
10To generate plists with UID values, wrap the values with the Uid object. The
11value must be an int.
12
13To generate plists with NSData/CFData values, wrap the values with the
14Data object. The value must be a string.
15
16Date values can only be datetime.datetime objects.
17
18The exceptions InvalidPlistException and NotBinaryPlistException may be
19thrown to indicate that the data cannot be serialized or deserialized as
20a binary plist.
21
22Plist generation example:
23
24    from biplist import *
25    from datetime import datetime
26    plist = {'aKey':'aValue',
27             '0':1.322,
28             'now':datetime.now(),
29             'list':[1,2,3],
30             'tuple':('a','b','c')
31             }
32    try:
33        writePlist(plist, "example.plist")
34    except (InvalidPlistException, NotBinaryPlistException), e:
35        print "Something bad happened:", e
36
37Plist parsing example:
38
39    from biplist import *
40    try:
41        plist = readPlist("example.plist")
42        print plist
43    except (InvalidPlistException, NotBinaryPlistException), e:
44        print "Not a plist:", e
45"""
46
47from collections import namedtuple
48import datetime
49import io
50import math
51import plistlib
52from struct import pack, unpack, unpack_from
53from struct import error as struct_error
54import sys
55import time
56
57try:
58    unicode
59    unicodeEmpty = r''
60except NameError:
61    unicode = str
62    unicodeEmpty = ''
63try:
64    long
65except NameError:
66    long = int
67try:
68    {}.iteritems
69    iteritems = lambda x: x.iteritems()
70except AttributeError:
71    iteritems = lambda x: x.items()
72
73__all__ = [
74    'Uid', 'Data', 'readPlist', 'writePlist', 'readPlistFromString',
75    'writePlistToString', 'InvalidPlistException', 'NotBinaryPlistException'
76]
77
78# Apple uses Jan 1, 2001 as a base for all plist date/times.
79apple_reference_date = datetime.datetime.utcfromtimestamp(978307200)
80
81class Uid(object):
82    """Wrapper around integers for representing UID values. This
83       is used in keyed archiving."""
84    integer = 0
85    def __init__(self, integer):
86        self.integer = integer
87
88    def __repr__(self):
89        return "Uid(%d)" % self.integer
90
91    def __eq__(self, other):
92        if isinstance(self, Uid) and isinstance(other, Uid):
93            return self.integer == other.integer
94        return False
95
96    def __cmp__(self, other):
97        return self.integer - other.integer
98
99    def __lt__(self, other):
100        return self.integer < other.integer
101
102    def __hash__(self):
103        return self.integer
104
105    def __int__(self):
106        return int(self.integer)
107
108class Data(bytes):
109    """Wrapper around bytes to distinguish Data values."""
110
111class InvalidPlistException(Exception):
112    """Raised when the plist is incorrectly formatted."""
113
114class NotBinaryPlistException(Exception):
115    """Raised when a binary plist was expected but not encountered."""
116
117def readPlist(pathOrFile):
118    """Raises NotBinaryPlistException, InvalidPlistException"""
119    didOpen = False
120    result = None
121    if isinstance(pathOrFile, (bytes, unicode)):
122        pathOrFile = open(pathOrFile, 'rb')
123        didOpen = True
124    try:
125        reader = PlistReader(pathOrFile)
126        result = reader.parse()
127    except NotBinaryPlistException as e:
128        try:
129            pathOrFile.seek(0)
130            result = None
131            if hasattr(plistlib, 'loads'):
132                contents = None
133                if isinstance(pathOrFile, (bytes, unicode)):
134                    with open(pathOrFile, 'rb') as f:
135                        contents = f.read()
136                else:
137                    contents = pathOrFile.read()
138                result = plistlib.loads(contents)
139            else:
140                result = plistlib.readPlist(pathOrFile)
141            result = wrapDataObject(result, for_binary=True)
142        except Exception as e:
143            raise InvalidPlistException(e)
144    finally:
145        if didOpen:
146            pathOrFile.close()
147    return result
148
149def wrapDataObject(o, for_binary=False):
150    if isinstance(o, Data) and not for_binary:
151        v = sys.version_info
152        if not (v[0] >= 3 and v[1] >= 4):
153            o = plistlib.Data(o)
154    elif isinstance(o, (bytes, plistlib.Data)) and for_binary:
155        if hasattr(o, 'data'):
156            o = Data(o.data)
157    elif isinstance(o, tuple):
158        o = wrapDataObject(list(o), for_binary)
159        o = tuple(o)
160    elif isinstance(o, list):
161        for i in range(len(o)):
162            o[i] = wrapDataObject(o[i], for_binary)
163    elif isinstance(o, dict):
164        for k in o:
165            o[k] = wrapDataObject(o[k], for_binary)
166    return o
167
168def writePlist(rootObject, pathOrFile, binary=True):
169    if not binary:
170        rootObject = wrapDataObject(rootObject, binary)
171        if hasattr(plistlib, "dump"):
172            if isinstance(pathOrFile, (bytes, unicode)):
173                with open(pathOrFile, 'wb') as f:
174                    return plistlib.dump(rootObject, f)
175            else:
176                return plistlib.dump(rootObject, pathOrFile)
177        else:
178            return plistlib.writePlist(rootObject, pathOrFile)
179    else:
180        didOpen = False
181        if isinstance(pathOrFile, (bytes, unicode)):
182            pathOrFile = open(pathOrFile, 'wb')
183            didOpen = True
184        writer = PlistWriter(pathOrFile)
185        result = writer.writeRoot(rootObject)
186        if didOpen:
187            pathOrFile.close()
188        return result
189
190def readPlistFromString(data):
191    return readPlist(io.BytesIO(data))
192
193def writePlistToString(rootObject, binary=True):
194    if not binary:
195        rootObject = wrapDataObject(rootObject, binary)
196        if hasattr(plistlib, "dumps"):
197            return plistlib.dumps(rootObject)
198        elif hasattr(plistlib, "writePlistToBytes"):
199            return plistlib.writePlistToBytes(rootObject)
200        else:
201            return plistlib.writePlistToString(rootObject)
202    else:
203        ioObject = io.BytesIO()
204        writer = PlistWriter(ioObject)
205        writer.writeRoot(rootObject)
206        return ioObject.getvalue()
207
208def is_stream_binary_plist(stream):
209    stream.seek(0)
210    header = stream.read(7)
211    if header == b'bplist0':
212        return True
213    else:
214        return False
215
216PlistTrailer = namedtuple('PlistTrailer', 'offsetSize, objectRefSize, offsetCount, topLevelObjectNumber, offsetTableOffset')
217PlistByteCounts = namedtuple('PlistByteCounts', 'nullBytes, boolBytes, intBytes, realBytes, dateBytes, dataBytes, stringBytes, uidBytes, arrayBytes, setBytes, dictBytes')
218
219class PlistReader(object):
220    file = None
221    contents = ''
222    offsets = None
223    trailer = None
224    currentOffset = 0
225    # Used to detect recursive object references.
226    offsetsStack = []
227
228    def __init__(self, fileOrStream):
229        """Raises NotBinaryPlistException."""
230        self.reset()
231        self.file = fileOrStream
232
233    def parse(self):
234        return self.readRoot()
235
236    def reset(self):
237        self.trailer = None
238        self.contents = ''
239        self.offsets = []
240        self.currentOffset = 0
241        self.offsetsStack = []
242
243    def readRoot(self):
244        result = None
245        self.reset()
246        # Get the header, make sure it's a valid file.
247        if not is_stream_binary_plist(self.file):
248            raise NotBinaryPlistException()
249        self.file.seek(0)
250        self.contents = self.file.read()
251        if len(self.contents) < 32:
252            raise InvalidPlistException("File is too short.")
253        trailerContents = self.contents[-32:]
254        try:
255            self.trailer = PlistTrailer._make(unpack("!xxxxxxBBQQQ", trailerContents))
256
257            if pow(2, self.trailer.offsetSize*8) < self.trailer.offsetTableOffset:
258                raise InvalidPlistException("Offset size insufficient to reference all objects.")
259
260            if pow(2, self.trailer.objectRefSize*8) < self.trailer.offsetCount:
261                raise InvalidPlistException("Too many offsets to represent in size of object reference representation.")
262
263            offset_size = self.trailer.offsetSize * self.trailer.offsetCount
264            offset = self.trailer.offsetTableOffset
265
266            if offset + offset_size > pow(2, 64):
267                raise InvalidPlistException("Offset table is excessively long.")
268
269            if self.trailer.offsetSize > 16:
270                raise InvalidPlistException("Offset size is greater than maximum integer size.")
271
272            if self.trailer.objectRefSize == 0:
273                raise InvalidPlistException("Object reference size is zero.")
274
275            if offset >= len(self.contents) - 32:
276                raise InvalidPlistException("Offset table offset is too large.")
277
278            if offset < len("bplist00x"):
279                raise InvalidPlistException("Offset table offset is too small.")
280
281            if self.trailer.topLevelObjectNumber >= self.trailer.offsetCount:
282                raise InvalidPlistException("Top level object number is larger than the number of objects.")
283
284            offset_contents = self.contents[offset:offset+offset_size]
285            offset_i = 0
286            offset_table_length = len(offset_contents)
287
288            while offset_i < self.trailer.offsetCount:
289                begin = self.trailer.offsetSize*offset_i
290                end = begin+self.trailer.offsetSize
291                if end > offset_table_length:
292                    raise InvalidPlistException("End of object is at invalid offset %d in offset table of length %d" % (end, offset_table_length))
293                tmp_contents = offset_contents[begin:end]
294                tmp_sized = self.getSizedInteger(tmp_contents, self.trailer.offsetSize)
295                self.offsets.append(tmp_sized)
296                offset_i += 1
297            self.setCurrentOffsetToObjectNumber(self.trailer.topLevelObjectNumber)
298            result = self.readObject()
299        except TypeError as e:
300            raise InvalidPlistException(e)
301        return result
302
303    def setCurrentOffsetToObjectNumber(self, objectNumber):
304        if objectNumber > len(self.offsets) - 1:
305            raise InvalidPlistException("Invalid offset number: %d" % objectNumber)
306        self.currentOffset = self.offsets[objectNumber]
307        if self.currentOffset in self.offsetsStack:
308            raise InvalidPlistException("Recursive data structure detected in object: %d" % objectNumber)
309
310    def beginOffsetProtection(self):
311        self.offsetsStack.append(self.currentOffset)
312        return self.currentOffset
313
314    def endOffsetProtection(self, offset):
315        try:
316            index = self.offsetsStack.index(offset)
317            self.offsetsStack = self.offsetsStack[:index]
318        except ValueError as e:
319            pass
320
321    def readObject(self):
322        protection = self.beginOffsetProtection()
323        result = None
324        tmp_byte = self.contents[self.currentOffset:self.currentOffset+1]
325        if len(tmp_byte) != 1:
326            raise InvalidPlistException("No object found at offset: %d" % self.currentOffset)
327        marker_byte = unpack("!B", tmp_byte)[0]
328        format = (marker_byte >> 4) & 0x0f
329        extra = marker_byte & 0x0f
330        self.currentOffset += 1
331
332        def proc_extra(extra):
333            if extra == 0b1111:
334                extra = self.readObject()
335            return extra
336
337        # bool, null, or fill byte
338        if format == 0b0000:
339            if extra == 0b0000:
340                result = None
341            elif extra == 0b1000:
342                result = False
343            elif extra == 0b1001:
344                result = True
345            elif extra == 0b1111:
346                pass # fill byte
347            else:
348                raise InvalidPlistException("Invalid object found at offset: %d" % (self.currentOffset - 1))
349        # int
350        elif format == 0b0001:
351            result = self.readInteger(pow(2, extra))
352        # real
353        elif format == 0b0010:
354            result = self.readReal(extra)
355        # date
356        elif format == 0b0011 and extra == 0b0011:
357            result = self.readDate()
358        # data
359        elif format == 0b0100:
360            extra = proc_extra(extra)
361            result = self.readData(extra)
362        # ascii string
363        elif format == 0b0101:
364            extra = proc_extra(extra)
365            result = self.readAsciiString(extra)
366        # Unicode string
367        elif format == 0b0110:
368            extra = proc_extra(extra)
369            result = self.readUnicode(extra)
370        # uid
371        elif format == 0b1000:
372            result = self.readUid(extra)
373        # array
374        elif format == 0b1010:
375            extra = proc_extra(extra)
376            result = self.readArray(extra)
377        # set
378        elif format == 0b1100:
379            extra = proc_extra(extra)
380            result = set(self.readArray(extra))
381        # dict
382        elif format == 0b1101:
383            extra = proc_extra(extra)
384            result = self.readDict(extra)
385        else:
386            raise InvalidPlistException("Invalid object found: {format: %s, extra: %s}" % (bin(format), bin(extra)))
387        self.endOffsetProtection(protection)
388        return result
389
390    def readContents(self, length, description="Object contents"):
391        end = self.currentOffset + length
392        if end >= len(self.contents) - 32:
393            raise InvalidPlistException("%s extends into trailer" % description)
394        elif length < 0:
395            raise InvalidPlistException("%s length is less than zero" % length)
396        data = self.contents[self.currentOffset:end]
397        return data
398
399    def readInteger(self, byteSize):
400        data = self.readContents(byteSize, "Integer")
401        self.currentOffset = self.currentOffset + byteSize
402        return self.getSizedInteger(data, byteSize, as_number=True)
403
404    def readReal(self, length):
405        to_read = pow(2, length)
406        data = self.readContents(to_read, "Real")
407        if length == 2: # 4 bytes
408            result = unpack('>f', data)[0]
409        elif length == 3: # 8 bytes
410            result = unpack('>d', data)[0]
411        else:
412            raise InvalidPlistException("Unknown Real of length %d bytes" % to_read)
413        return result
414
415    def readRefs(self, count):
416        refs = []
417        i = 0
418        while i < count:
419            fragment = self.readContents(self.trailer.objectRefSize, "Object reference")
420            ref = self.getSizedInteger(fragment, len(fragment))
421            refs.append(ref)
422            self.currentOffset += self.trailer.objectRefSize
423            i += 1
424        return refs
425
426    def readArray(self, count):
427        if not isinstance(count, (int, long)):
428            raise InvalidPlistException("Count of entries in dict isn't of integer type.")
429        result = []
430        values = self.readRefs(count)
431        i = 0
432        while i < len(values):
433            self.setCurrentOffsetToObjectNumber(values[i])
434            value = self.readObject()
435            result.append(value)
436            i += 1
437        return result
438
439    def readDict(self, count):
440        if not isinstance(count, (int, long)):
441            raise InvalidPlistException("Count of keys/values in dict isn't of integer type.")
442        result = {}
443        keys = self.readRefs(count)
444        values = self.readRefs(count)
445        i = 0
446        while i < len(keys):
447            self.setCurrentOffsetToObjectNumber(keys[i])
448            key = self.readObject()
449            self.setCurrentOffsetToObjectNumber(values[i])
450            value = self.readObject()
451            result[key] = value
452            i += 1
453        return result
454
455    def readAsciiString(self, length):
456        if not isinstance(length, (int, long)):
457            raise InvalidPlistException("Length of ASCII string isn't of integer type.")
458        data = self.readContents(length, "ASCII string")
459        result = unpack("!%ds" % length, data)[0]
460        self.currentOffset += length
461        return str(result.decode('ascii'))
462
463    def readUnicode(self, length):
464        if not isinstance(length, (int, long)):
465            raise InvalidPlistException("Length of Unicode string isn't of integer type.")
466        actual_length = length*2
467        data = self.readContents(actual_length, "Unicode string")
468        self.currentOffset += actual_length
469        return data.decode('utf_16_be')
470
471    def readDate(self):
472        data = self.readContents(8, "Date")
473        x = unpack(">d", data)[0]
474        if math.isnan(x):
475            raise InvalidPlistException("Date is NaN")
476        # Use timedelta to workaround time_t size limitation on 32-bit python.
477        try:
478            result = datetime.timedelta(seconds=x) + apple_reference_date
479        except OverflowError:
480            if x > 0:
481                result = datetime.datetime.max
482            else:
483                result = datetime.datetime.min
484        self.currentOffset += 8
485        return result
486
487    def readData(self, length):
488        if not isinstance(length, (int, long)):
489            raise InvalidPlistException("Length of data isn't of integer type.")
490        result = self.readContents(length, "Data")
491        self.currentOffset += length
492        return Data(result)
493
494    def readUid(self, length):
495        if not isinstance(length, (int, long)):
496            raise InvalidPlistException("Uid length isn't of integer type.")
497        return Uid(self.readInteger(length+1))
498
499    def getSizedInteger(self, data, byteSize, as_number=False):
500        """Numbers of 8 bytes are signed integers when they refer to numbers, but unsigned otherwise."""
501        result = 0
502        if byteSize == 0:
503            raise InvalidPlistException("Encountered integer with byte size of 0.")
504        # 1, 2, and 4 byte integers are unsigned
505        elif byteSize == 1:
506            result = unpack('>B', data)[0]
507        elif byteSize == 2:
508            result = unpack('>H', data)[0]
509        elif byteSize == 4:
510            result = unpack('>L', data)[0]
511        elif byteSize == 8:
512            if as_number:
513                result = unpack('>q', data)[0]
514            else:
515                result = unpack('>Q', data)[0]
516        elif byteSize <= 16:
517            # Handle odd-sized or integers larger than 8 bytes
518            # Don't naively go over 16 bytes, in order to prevent infinite loops.
519            result = 0
520            if hasattr(int, 'from_bytes'):
521                result = int.from_bytes(data, 'big')
522            else:
523                for byte in data:
524                    if not isinstance(byte, int): # Python3.0-3.1.x return ints, 2.x return str
525                        byte = unpack_from('>B', byte)[0]
526                    result = (result << 8) | byte
527        else:
528            raise InvalidPlistException("Encountered integer longer than 16 bytes.")
529        return result
530
531class HashableWrapper(object):
532    def __init__(self, value):
533        self.value = value
534    def __repr__(self):
535        return "<HashableWrapper: %s>" % [self.value]
536
537class BoolWrapper(object):
538    def __init__(self, value):
539        self.value = value
540    def __repr__(self):
541        return "<BoolWrapper: %s>" % self.value
542
543class FloatWrapper(object):
544    _instances = {}
545    def __new__(klass, value):
546        # Ensure FloatWrapper(x) for a given float x is always the same object
547        wrapper = klass._instances.get(value)
548        if wrapper is None:
549            wrapper = object.__new__(klass)
550            wrapper.value = value
551            klass._instances[value] = wrapper
552        return wrapper
553    def __repr__(self):
554        return "<FloatWrapper: %s>" % self.value
555
556class StringWrapper(object):
557    __instances = {}
558
559    encodedValue = None
560    encoding = None
561
562    def __new__(cls, value):
563        '''Ensure we only have a only one instance for any string,
564         and that we encode ascii as 1-byte-per character when possible'''
565
566        encodedValue = None
567
568        for encoding in ('ascii', 'utf_16_be'):
569            try:
570               encodedValue = value.encode(encoding)
571            except: pass
572            if encodedValue is not None:
573                if encodedValue not in cls.__instances:
574                    cls.__instances[encodedValue] = super(StringWrapper, cls).__new__(cls)
575                    cls.__instances[encodedValue].encodedValue = encodedValue
576                    cls.__instances[encodedValue].encoding = encoding
577                return cls.__instances[encodedValue]
578
579        raise ValueError('Unable to get ascii or utf_16_be encoding for %s' % repr(value))
580
581    def __len__(self):
582        '''Return roughly the number of characters in this string (half the byte length)'''
583        if self.encoding == 'ascii':
584            return len(self.encodedValue)
585        else:
586            return len(self.encodedValue)//2
587
588    def __lt__(self, other):
589        return self.encodedValue < other.encodedValue
590
591    @property
592    def encodingMarker(self):
593        if self.encoding == 'ascii':
594            return 0b0101
595        else:
596            return 0b0110
597
598    def __repr__(self):
599        return '<StringWrapper (%s): %s>' % (self.encoding, self.encodedValue)
600
601class PlistWriter(object):
602    header = b'bplist00bybiplist1.0'
603    file = None
604    byteCounts = None
605    trailer = None
606    computedUniques = None
607    writtenReferences = None
608    referencePositions = None
609    wrappedTrue = None
610    wrappedFalse = None
611    # Used to detect recursive object references.
612    objectsStack = []
613
614    def __init__(self, file):
615        self.reset()
616        self.file = file
617        self.wrappedTrue = BoolWrapper(True)
618        self.wrappedFalse = BoolWrapper(False)
619
620    def reset(self):
621        self.byteCounts = PlistByteCounts(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
622        self.trailer = PlistTrailer(0, 0, 0, 0, 0)
623
624        # A set of all the uniques which have been computed.
625        self.computedUniques = set()
626        # A list of all the uniques which have been written.
627        self.writtenReferences = {}
628        # A dict of the positions of the written uniques.
629        self.referencePositions = {}
630
631        self.objectsStack = []
632
633    def positionOfObjectReference(self, obj):
634        """If the given object has been written already, return its
635           position in the offset table. Otherwise, return None."""
636        return self.writtenReferences.get(obj)
637
638    def writeRoot(self, root):
639        """
640        Strategy is:
641        - write header
642        - wrap root object so everything is hashable
643        - compute size of objects which will be written
644          - need to do this in order to know how large the object refs
645            will be in the list/dict/set reference lists
646        - write objects
647          - keep objects in writtenReferences
648          - keep positions of object references in referencePositions
649          - write object references with the length computed previously
650        - computer object reference length
651        - write object reference positions
652        - write trailer
653        """
654        output = self.header
655        wrapped_root = self.wrapRoot(root)
656        self.computeOffsets(wrapped_root, asReference=True, isRoot=True)
657        self.trailer = self.trailer._replace(**{'objectRefSize':self.intSize(len(self.computedUniques))})
658        self.writeObjectReference(wrapped_root, output)
659        output = self.writeObject(wrapped_root, output, setReferencePosition=True)
660
661        # output size at this point is an upper bound on how big the
662        # object reference offsets need to be.
663        self.trailer = self.trailer._replace(**{
664            'offsetSize':self.intSize(len(output)),
665            'offsetCount':len(self.computedUniques),
666            'offsetTableOffset':len(output),
667            'topLevelObjectNumber':0
668            })
669
670        output = self.writeOffsetTable(output)
671        output += pack('!xxxxxxBBQQQ', *self.trailer)
672        self.file.write(output)
673
674    def beginRecursionProtection(self, obj):
675        if not isinstance(obj, (set, dict, list, tuple)):
676            return
677        if id(obj) in self.objectsStack:
678            raise InvalidPlistException("Recursive containers are not allowed in plists.")
679        self.objectsStack.append(id(obj))
680
681    def endRecursionProtection(self, obj):
682        if not isinstance(obj, (set, dict, list, tuple)):
683            return
684        try:
685            index = self.objectsStack.index(id(obj))
686            self.objectsStack = self.objectsStack[:index]
687        except ValueError as e:
688            pass
689
690    def wrapRoot(self, root):
691        result = None
692        self.beginRecursionProtection(root)
693
694        if isinstance(root, bool):
695            if root is True:
696                result = self.wrappedTrue
697            else:
698                result = self.wrappedFalse
699        elif isinstance(root, float):
700            result = FloatWrapper(root)
701        elif isinstance(root, set):
702            n = set()
703            for value in root:
704                n.add(self.wrapRoot(value))
705            result = HashableWrapper(n)
706        elif isinstance(root, dict):
707            n = {}
708            for key, value in iteritems(root):
709                n[self.wrapRoot(key)] = self.wrapRoot(value)
710            result = HashableWrapper(n)
711        elif isinstance(root, list):
712            n = []
713            for value in root:
714                n.append(self.wrapRoot(value))
715            result = HashableWrapper(n)
716        elif isinstance(root, tuple):
717            n = tuple([self.wrapRoot(value) for value in root])
718            result = HashableWrapper(n)
719        elif isinstance(root, (str, unicode)) and not isinstance(root, Data):
720            result =  StringWrapper(root)
721        elif isinstance(root, bytes):
722            result = Data(root)
723        else:
724            result = root
725
726        self.endRecursionProtection(root)
727        return result
728
729    def incrementByteCount(self, field, incr=1):
730        self.byteCounts = self.byteCounts._replace(**{field:self.byteCounts.__getattribute__(field) + incr})
731
732    def computeOffsets(self, obj, asReference=False, isRoot=False):
733        def check_key(key):
734            if key is None:
735                raise InvalidPlistException('Dictionary keys cannot be null in plists.')
736            elif isinstance(key, Data):
737                raise InvalidPlistException('Data cannot be dictionary keys in plists.')
738            elif not isinstance(key, StringWrapper):
739                raise InvalidPlistException('Keys must be strings.')
740
741        def proc_size(size):
742            if size > 0b1110:
743                size += self.intSize(size)
744            return size
745        # If this should be a reference, then we keep a record of it in the
746        # uniques table.
747        if asReference:
748            if obj in self.computedUniques:
749                return
750            else:
751                self.computedUniques.add(obj)
752
753        if obj is None:
754            self.incrementByteCount('nullBytes')
755        elif isinstance(obj, BoolWrapper):
756            self.incrementByteCount('boolBytes')
757        elif isinstance(obj, Uid):
758            size = self.intSize(obj.integer)
759            self.incrementByteCount('uidBytes', incr=1+size)
760        elif isinstance(obj, (int, long)):
761            size = self.intSize(obj)
762            self.incrementByteCount('intBytes', incr=1+size)
763        elif isinstance(obj, FloatWrapper):
764            size = self.realSize(obj)
765            self.incrementByteCount('realBytes', incr=1+size)
766        elif isinstance(obj, datetime.datetime):
767            self.incrementByteCount('dateBytes', incr=2)
768        elif isinstance(obj, Data):
769            size = proc_size(len(obj))
770            self.incrementByteCount('dataBytes', incr=1+size)
771        elif isinstance(obj, StringWrapper):
772            size = proc_size(len(obj))
773            self.incrementByteCount('stringBytes', incr=1+size)
774        elif isinstance(obj, HashableWrapper):
775            obj = obj.value
776            if isinstance(obj, set):
777                size = proc_size(len(obj))
778                self.incrementByteCount('setBytes', incr=1+size)
779                for value in obj:
780                    self.computeOffsets(value, asReference=True)
781            elif isinstance(obj, (list, tuple)):
782                size = proc_size(len(obj))
783                self.incrementByteCount('arrayBytes', incr=1+size)
784                for value in obj:
785                    asRef = True
786                    self.computeOffsets(value, asReference=True)
787            elif isinstance(obj, dict):
788                size = proc_size(len(obj))
789                self.incrementByteCount('dictBytes', incr=1+size)
790                for key, value in iteritems(obj):
791                    check_key(key)
792                    self.computeOffsets(key, asReference=True)
793                    self.computeOffsets(value, asReference=True)
794        else:
795            raise InvalidPlistException("Unknown object type: %s (%s)" % (type(obj).__name__, repr(obj)))
796
797    def writeObjectReference(self, obj, output):
798        """Tries to write an object reference, adding it to the references
799           table. Does not write the actual object bytes or set the reference
800           position. Returns a tuple of whether the object was a new reference
801           (True if it was, False if it already was in the reference table)
802           and the new output.
803        """
804        position = self.positionOfObjectReference(obj)
805        if position is None:
806            self.writtenReferences[obj] = len(self.writtenReferences)
807            output += self.binaryInt(len(self.writtenReferences) - 1, byteSize=self.trailer.objectRefSize)
808            return (True, output)
809        else:
810            output += self.binaryInt(position, byteSize=self.trailer.objectRefSize)
811            return (False, output)
812
813    def writeObject(self, obj, output, setReferencePosition=False):
814        """Serializes the given object to the output. Returns output.
815           If setReferencePosition is True, will set the position the
816           object was written.
817        """
818        def proc_variable_length(format, length):
819            result = b''
820            if length > 0b1110:
821                result += pack('!B', (format << 4) | 0b1111)
822                result = self.writeObject(length, result)
823            else:
824                result += pack('!B', (format << 4) | length)
825            return result
826
827        def timedelta_total_seconds(td):
828            # Shim for Python 2.6 compatibility, which doesn't have total_seconds.
829            # Make one argument a float to ensure the right calculation.
830            return (td.microseconds + (td.seconds + td.days * 24 * 3600) * 10.0**6) / 10.0**6
831
832        if setReferencePosition:
833            self.referencePositions[obj] = len(output)
834
835        if obj is None:
836            output += pack('!B', 0b00000000)
837        elif isinstance(obj, BoolWrapper):
838            if obj.value is False:
839                output += pack('!B', 0b00001000)
840            else:
841                output += pack('!B', 0b00001001)
842        elif isinstance(obj, Uid):
843            size = self.intSize(obj.integer)
844            output += pack('!B', (0b1000 << 4) | size - 1)
845            output += self.binaryInt(obj.integer)
846        elif isinstance(obj, (int, long)):
847            byteSize = self.intSize(obj)
848            root = math.log(byteSize, 2)
849            output += pack('!B', (0b0001 << 4) | int(root))
850            output += self.binaryInt(obj, as_number=True)
851        elif isinstance(obj, FloatWrapper):
852            # just use doubles
853            output += pack('!B', (0b0010 << 4) | 3)
854            output += self.binaryReal(obj)
855        elif isinstance(obj, datetime.datetime):
856            try:
857                timestamp = (obj - apple_reference_date).total_seconds()
858            except AttributeError:
859                timestamp = timedelta_total_seconds(obj - apple_reference_date)
860            output += pack('!B', 0b00110011)
861            output += pack('!d', float(timestamp))
862        elif isinstance(obj, Data):
863            output += proc_variable_length(0b0100, len(obj))
864            output += obj
865        elif isinstance(obj, StringWrapper):
866            output += proc_variable_length(obj.encodingMarker, len(obj))
867            output += obj.encodedValue
868        elif isinstance(obj, bytes):
869            output += proc_variable_length(0b0101, len(obj))
870            output += obj
871        elif isinstance(obj, HashableWrapper):
872            obj = obj.value
873            if isinstance(obj, (set, list, tuple)):
874                if isinstance(obj, set):
875                    output += proc_variable_length(0b1100, len(obj))
876                else:
877                    output += proc_variable_length(0b1010, len(obj))
878
879                objectsToWrite = []
880                for objRef in sorted(obj) if isinstance(obj, set) else obj:
881                    (isNew, output) = self.writeObjectReference(objRef, output)
882                    if isNew:
883                        objectsToWrite.append(objRef)
884                for objRef in objectsToWrite:
885                    output = self.writeObject(objRef, output, setReferencePosition=True)
886            elif isinstance(obj, dict):
887                output += proc_variable_length(0b1101, len(obj))
888                keys = []
889                values = []
890                objectsToWrite = []
891                for key, value in sorted(iteritems(obj)):
892                    keys.append(key)
893                    values.append(value)
894                for key in keys:
895                    (isNew, output) = self.writeObjectReference(key, output)
896                    if isNew:
897                        objectsToWrite.append(key)
898                for value in values:
899                    (isNew, output) = self.writeObjectReference(value, output)
900                    if isNew:
901                        objectsToWrite.append(value)
902                for objRef in objectsToWrite:
903                    output = self.writeObject(objRef, output, setReferencePosition=True)
904        return output
905
906    def writeOffsetTable(self, output):
907        """Writes all of the object reference offsets."""
908        all_positions = []
909        writtenReferences = list(self.writtenReferences.items())
910        writtenReferences.sort(key=lambda x: x[1])
911        for obj,order in writtenReferences:
912            # Porting note: Elsewhere we deliberately replace empty unicdoe strings
913            # with empty binary strings, but the empty unicode string
914            # goes into writtenReferences.  This isn't an issue in Py2
915            # because u'' and b'' have the same hash; but it is in
916            # Py3, where they don't.
917            if bytes != str and obj == unicodeEmpty:
918                obj = b''
919            position = self.referencePositions.get(obj)
920            if position is None:
921                raise InvalidPlistException("Error while writing offsets table. Object not found. %s" % obj)
922            output += self.binaryInt(position, self.trailer.offsetSize)
923            all_positions.append(position)
924        return output
925
926    def binaryReal(self, obj):
927        # just use doubles
928        result = pack('>d', obj.value)
929        return result
930
931    def binaryInt(self, obj, byteSize=None, as_number=False):
932        result = b''
933        if byteSize is None:
934            byteSize = self.intSize(obj)
935        if byteSize == 1:
936            result += pack('>B', obj)
937        elif byteSize == 2:
938            result += pack('>H', obj)
939        elif byteSize == 4:
940            result += pack('>L', obj)
941        elif byteSize == 8:
942            if as_number:
943                result += pack('>q', obj)
944            else:
945                result += pack('>Q', obj)
946        elif byteSize <= 16:
947            try:
948                result = pack('>Q', 0) + pack('>Q', obj)
949            except struct_error as e:
950                raise InvalidPlistException("Unable to pack integer %d: %s" % (obj, e))
951        else:
952            raise InvalidPlistException("Core Foundation can't handle integers with size greater than 16 bytes.")
953        return result
954
955    def intSize(self, obj):
956        """Returns the number of bytes necessary to store the given integer."""
957        # SIGNED
958        if obj < 0: # Signed integer, always 8 bytes
959            return 8
960        # UNSIGNED
961        elif obj <= 0xFF: # 1 byte
962            return 1
963        elif obj <= 0xFFFF: # 2 bytes
964            return 2
965        elif obj <= 0xFFFFFFFF: # 4 bytes
966            return 4
967        # SIGNED
968        # 0x7FFFFFFFFFFFFFFF is the max.
969        elif obj <= 0x7FFFFFFFFFFFFFFF: # 8 bytes signed
970            return 8
971        elif obj <= 0xffffffffffffffff: # 8 bytes unsigned
972            return 16
973        else:
974            raise InvalidPlistException("Core Foundation can't handle integers with size greater than 8 bytes.")
975
976    def realSize(self, obj):
977        return 8
978