class Choice(bdec.entry.Entry):
    """
    An entry that can be one of many entries.

    The first entry to decode correctly will be used.
    """

    def __init__(self, name, children, length=None):
        bdec.entry.Entry.__init__(self, name, length, children)

    def _range(self, ignore_entries):
        minimum = min(child.entry.range(ignore_entries).min for child in self.children)
        maximum = max(child.entry.range(ignore_entries).max for child in self.children)
        return bdec.entry.Range(minimum, maximum) class Equals(Constraint):
    type = '!='

    def check(self, entry, value, context):
        expected = self.limit.evaluate(context)
        if isinstance(expected, int):
            if int(value) !=  expected:
                raise ConstraintError(entry, int(value), '==', expected)
        elif isinstance(expected, Data):
            # We aren't checking the length here, only the value (for example,
            # the expected value for a variable length binary field will have
            # a different length than the actual). Only compare the bits that
            # are valid.
            length_diff = len(value) - len(expected)
            if length_diff > 0:
                # The expected value is shorter than the actual, so grow it.
                expected = Data('\x00' * (length_diff / 8 + 1), 0, length_diff) + expected
            elif length_diff < 0:
                # The expected value is longer than the actual, so shrink it.
                shorter = expected.copy()
                leading = shorter.pop(-length_diff)
                if not int(leading):
                    # We can safely pop the leading bits.
                    expected = shorter
            if value !=  expected:
                raise ConstraintError(entry, value, '==', expected)
        else:
            if value !=  expected:
                raise ConstraintError(entry, value, '==', expected)

    def range(self):
        limit = _limit(self.limit)
        return Range(limit, limit) class Maximum(Constraint):
    type = '>'

    def check(self, entry, value, context):
        expected = self.limit.evaluate(context)
        if isinstance(value, basestring):
            # It is useful to check the bounds of a text character...
            value = ord(value)
        if int(value) > expected:
            raise ConstraintError(entry, int(value), '<=', expected)

    def range(self):
        return Range(None, _limit(self.limit)) class Minimum(Constraint):
    type = '<'

    def check(self, entry, value, context):
        expected = self.limit.evaluate(context)
        if isinstance(value, basestring):
            # It is useful to check the bounds of a text character...
            value = ord(value)
        if int(value) < expected:
            raise ConstraintError(entry, int(value), '>=', expected)

    def range(self):
        return Range(_limit(self.limit), None) class Data(object):
    """
    A class to hold information about data to be decoded.
    
    The data is not actually validated to be available until it is used, at
    which stage NotEnoughDataError can be thrown.
    """
    def __init__(self, buffer="", start=None, end=None):
        """Construct a data object.

        buffer - Can be either a string or a file instance.
        start - The bit the data starts at in the buffer. Bit 0 is the most
           significant bit in the first byte. If None, the data starts at
           bit zero.
        end - The bit the data ends at. If None, the data ends at the end of
           the buffer.
        """

        # Note: We can detect the length of string and empty buffers at
        # initialisation time; it is a speed win to do so. However, that means
        # data objects behave differently depending on what they were 
        # constructed from (a source of bugs) (eg: verification of length
        # at pop time, as opposed to read time).
        if isinstance(buffer, str):
            self._buffer = _MemoryBuffer(buffer)
        elif isinstance(buffer, _ByteBuffer):
            self._buffer = buffer
        elif hasattr(buffer, 'seek'):
            # Treat the buffer as a file object.
            try:
                buffer.tell()
                self._buffer = _FileBuffer(buffer)
            except IOError:
                # This file doesn't appear to support seeking
                self._buffer = _NonSeekingFileBuffer(buffer)
        else:
            raise Exception("Unknown data source '%s'" % type(buffer)) 

        if start is None:
            start = 0

        assert end is None or start <= end
        self._start = start
        self._end = end

    def pop(self, length):
        """Return a data instance for representing the start of this data.

        The popped data will no longer be available from this instance. If not
        enough data is available, an error can either be raised now, or later
        when the popped data is used.

        length -- The length in bits to remove.
        """
        if length < 0:
            raise PoppedNegativeBitsError(length)
        if self._end is not None and length > self._end - self._start:
            raise NotEnoughDataError(length, self._end - self._start)

        result = Data(self._buffer, self._start, self._start + length)
        self._start += length
        return result

    def copy(self, klass=None):
        """Create a copy of this data instance.

        klass - The data class to use when creating the copy. If None, will
            use Data.
        """
        if not klass:
            klass = Data
        return klass(self._buffer, self._start, self._end)

    def bytes(self):
        """Return a str instance representing the bytes held by this data.

        If the data length isn't a multiple of 8 bits, a DataError will be
        raised."""
        return "".join(chr(byte) for byte in self._get_bytes())

    def text(self, encoding):
        """Return a unicode object that represents the data buffer.

        If the data length isn't a multiple of 8 bits, a DataError will be
        raised. If the data cannot be converted to the given encoding, a
        BadTextEncodingError error will be raised.
        
        encoding -- The unicode encoding the data is in. """
        try:
            return unicode(self.bytes(), encoding)
        except UnicodeDecodeError:
            raise BadTextEncodingError(self, encoding)

    def __repr__(self):
        """Return a textual representation of the data."""
        if len(self) % 8 == 0:
            return 'hex (%i bytes): %s' % (len(self) / 8, self.get_hex())
        else:
            return 'bin (%i bits): %s' % (len(self), self.get_binary_text())

    def _get_bits(self):
        """
        Get an iterator to the bits contained in this buffer.

        Can throw NotEnoughDataError if the backing store doesn't have the
        required amount of data for this instance.
        """
        i = 0
        while self._end is None or i < self._end - self._start:
            try:
                yield self._get_bit(i)
            except _OutOfDataError:
                if self._end is not None:
                    raise NotEnoughDataError(self._end - self._start, i)
                break
            i += 1

    def __eq__(self, other):
        if not isinstance(other, Data):
            return NotImplemented

        # TODO: This bit by bit comparison is slow...
        a = self._get_bits()
        b = other._get_bits()
        while 1:
            try:
                a_bit = a.next()
            except StopIteration:
                try:
                    b.next()
                    # Not equal, as 'other' is longer then we are
                    return False
                except StopIteration:
                    # Equal, as same size, same values
                    return True

            try:
                b_bit = b.next()
            except StopIteration:
                # Not equal, as we are longer than 'other'
                return False

            if a_bit != b_bit:
                return False

    def __ne__(self, other):
        if not isinstance(other, Data):
            return NotImplemented

        return not self == other

    def __len__(self):
        if self._end is None:
            end = len(self._buffer) * 8
            if end < self._start:
                raise NotEnoughDataError(0, end - self._start)
            self._end = end
        return self._end - self._start

    def __nonzero__(self):
        return not self.empty()

    def empty(self):
        """Check to see if we have data left.

        If the length of the data is known, that value will be used. If the
        length is unknown, it will see if we can read more data.
        """
        if self._end is not None:
            return self._end == self._start

        # We don't know where the data ends, so look to see if we can read
        # more of the data.
        try:
            self._get_bits().next()
            return False
        except StopIteration:
            pass
        return True

    def _get_bit(self, i):
        """
        Query the backend byte source for a given bit.

        If the backend doesn't have the data available, or we are querying
        outside of our bounds, an _OutOfDataError is raised.
        """
        i += self._start
        if self._end is not None and i >= self._end:
            raise _OutOfDataError()
        byte = i / 8
        i = i % 8
        return (self._buffer.read_byte(byte) >> (7 - i)) & 1

    def validate(self):
        """Validate that the data is available in the backing store.

        Will cause the all the data represented by this instance to be loaded
        into memory. If this data instance doesn't have a lenght, will return
        without failing.

        Will throw NotEnoughDataError if the data isn't available.
        """
        if not self._end:
            return
        length = len(self)
        if length == 0:
            return

        try:
            # We don't want to ask for the length of the backing store
            # initially, as that may cause it to be loaded into memory (ie:
            # if it's a stream that doesn't support streaming). So we instead
            # just attempt to read the last bit we want...
            self._get_bit(length-1)
        except _OutOfDataError:
            # We don't have enough data for reading this byte... determine how
            # much data we really do have.
            num_bytes = len(self._buffer)
            available_bits = num_bytes * 8 - self._start
            raise NotEnoughDataError(length, available_bits)
        
    def __int__(self):
        """
        Convert the buffer to an integer

        Conversion is big endian.
        """
        if not len(self):
            return 0

        data = self.copy()
        result = 0
        for bit in data.pop(len(data) % 8)._get_bits():
            result = (result << 1) | bit
        for byte in data._get_bytes():
            result = (result << 8) | byte
        return result

    def __add__(self, other):
        if not isinstance(other, Data):
            raise NotImplementedError()

        if not self._end:
            self._end = self._start + len(self)
        if not other._end:
            other._end = other._start + len(other)
        self.validate()
        other.validate()

        # Check for early outs
        if not self:
            return other
        if not other:
            return self

        left = self._buffer[self._start / 8:(self._end - 1) / 8 + 1]
        right = other._buffer[other._start / 8:(other._end - 1) / 8 + 1]

        # Shift the shorter data object (as the shift is relatively intensive)
        if len(self) < len(other):
            # The left hand buffer is shorter than the right, so shift it so it
            # aligns with the right
            distance = (other._start - self._end) % 8
            left_start = self._start % 8 + distance
            left >>= distance

            # It's possible we have to truncate the buffer here, as we may
            # have create an extra byte on the right that contains data we
            # don't care about.
            left = left[:(left_start + len(self) - 1) / 8 + 1]
        else:
            # The right hand buffer is shorter than the left, so shift it so it
            # aligns with the left
            distance = (self._end - other._start) % 8
            left_start = (self._start + distance) % 8
            left_start = self._start % 8
            right >>= distance
            right_start = other._start % 8 + distance
            right = right[right_start / 8:(right_start + len(other) - 1) / 8 + 1]

        if (left_start + len(self)) % 8 and len(self) and len(other):
            # The left doesn't end on a whole byte; create a joining byte to
            # connect the left & right
            merge_byte = (left_start + len(self) - 1) / 8

            overlapping_bits = (left_start + len(self)) % 8
            overlap =  left.read_byte(merge_byte) & (0xff << (8 - overlapping_bits))
            overlap |= right.read_byte(0) & (0xff >> overlapping_bits)

            left = left[:merge_byte] + _MemoryBuffer(chr(overlap))
            right = right[1:]

        return Data(left + right, left_start, left_start + len(self) + len(other))

    def _get_bytes(self):
        """
        Return an iterator to a series of byte values in the data.
        """
        if self._start % 8 == 0 and self._end is not None and self._end % 8 == 0:
            # Optimise for the case where we know the length of the data, and
            # it is byte aligned.
            for i in xrange(self._start / 8, self._end / 8):
                try:
                    yield self._buffer.read_byte(i)
                except _OutOfDataError:
                    raise NotEnoughDataError(self._end - self._start, i * 8 - self._start)
        else:
            # Read as many of the bits as possible, yielding the results.
            value = 0
            i = None
            for i, bit in enumerate(self._get_bits()):
                value = (value << 1) | bit
                if (i + 1) % 8 == 0:
                    # We have a new byte!
                    yield value
                    value = 0
            if i is not None and i % 8 != 7:
                raise ConversionNeedsBytesError(self)

    def __float__(self):
        """
        Convert the data buffer to a float that has been encoded in big endian.
        """
        if len(self) == 4 * 8:
            return struct.unpack('>f', self.bytes())[0]
        elif len(self) == 8 * 8:
            return struct.unpack('>d', self.bytes())[0]
        else:
            raise FloatLengthError(self)

    def get_litten_endian_float(self):
        """
        Convert the data buffer to a float that has been encoded in little endian.
        """
        if len(self) == 4 * 8:
            return struct.unpack('<f', self.bytes())[0]
        elif len(self) == 8 * 8:
            return struct.unpack('<d', self.bytes())[0]
        else:
            raise FloatLengthError(self)

    @staticmethod
    def from_float_little_endian(value, length):
        if length == 4 * 8:
            return Data(struct.pack('<f', value))
        elif length == 8 * 8:
            return Data(struct.pack('<d', value))
        else:
            raise FloatLengthError(self)

    @staticmethod
    def from_float_big_endian(value, length):
        if length == 4 * 8:
            return Data(struct.pack('>f', value))
        elif length == 8 * 8:
            return Data(struct.pack('>d', value))
        else:
            raise FloatLengthError(self)

    def get_little_endian_integer(self):
        """
        Get an integer that has been encoded in little endian format
        """
        result = 0
        for byte, value in enumerate(self._get_bytes()):
            result = result | (value << (8 * byte))
        return result

    def get_binary_text(self):
        """
        Get a string representing the binary data.

        eg: 001 10100000
        """
        bits = list(self._get_bits())
        bytes = []
        if len(bits) % 8 != 0:
            bytes.append(bits[0:len(bits) % 8])
        for i in range(len(bits) % 8, len(bits), 8):
            bytes.append(bits[i:i+8])

        bytes = ("".join(str(bit) for bit in byte) for byte in bytes)
        return " ".join(byte for byte in bytes)

    def get_hex(self):
        """
        Get a string representing the data in hex format.
        """
        data = self.copy()
        size = len(data)
        if size % 4 != 0:
            raise HexNeedsFourBitsError(self)

        result = ""
        if size % 8:
            result += "%x" % int(data.pop(4))

        for num in data._get_bytes():
            result += '%02x' % num

        return result

    @staticmethod
    def from_int_little_endian(value, length):
        """Create a data object from an integer.
        
        length -- The length in bits of the data buffer to create."""
        data = int(value)
        if length % 8 != 0:
            raise ConversionNeedsBytesError(self)
        chars = []
        for i in range(length / 8):
            chars.append(chr(data & 0xff))
            data >>= 8
        if data != 0:
            raise IntegerTooLongError(value, length)
        return Data("".join(chars))

    @staticmethod
    def from_int_big_endian(value, length):
        """Create a data object from an integer.
        
        length -- The length in bits of the data buffer to create."""
        data = int(value)
        chars = []
        num_bytes = length / 8
        if length % 8 != 0:
            num_bytes += 1
        for i in range(num_bytes):
            chars.append(chr(data & 0xff))
            data >>= 8
        if data != 0:
            raise IntegerTooLongError(value, length)
        chars.reverse()

        result = Data("".join(chars))
        num_leading_bits = num_bytes * 8 - length
        if num_leading_bits and 0 != int(result.pop(num_leading_bits)):
            # We have an integer that isn't a multiple of 8 bits, and we
            # couldn't quite fit it in the space available.
            raise IntegerTooLongError(value, length)
        return result

    @staticmethod
    def from_hex(hex): 
        """
        Convert a hex string to a data buffer.

        The hex entries can be seperated by whitespace, with multi-byte entries
        seperated on even characters.  For example, '0e 9a bc', or '0e9abc'.

        Entries without whitespace with an odd number of characters will be 
        treated as if it had a leading zero; eg: 'e02' will be interpreted as
        being the two byte value '0e02'.
        """
        buffer = []
        entries = hex.split()
        for entry in entries:
            if len(entry) % 2:
                entry = '0' + entry

            for i in range(len(entry) / 2):
                offset = i * 2
                value = entry[offset:offset + 2]
                for char in value:
                    if char not in _HEX_CHARACTERS:
                        raise InvalidHexTextError(hex)
                buffer.append(int(value, 16))
        return Data("".join(chr(value) for value in buffer))

    @staticmethod
    def from_binary_text(text):
        """
        Create a data object from binary text.

        eg: "001 10100000"
        """
        buffer = []
        value = 0
        length = 0
        for char in text:
            if char not in string.whitespace:
                if char not in ['0', '1']:
                    raise InvalidBinaryTextError(text)
                value <<= 1
                value |= int(char)
                length += 1

                if length == 8:
                    buffer.append(chr(value))
                    length = 0
                    value = 0
        buffer.append(chr(value << (8 - length)))
        return Data("".join(buffer), 0, len(buffer) * 8 - (8 - length)) class Child(object):
    """ A child is embedded in another entry."""
    def __init__(self, name, entry):
        self.name = name
        self.entry = entry

    def __repr__(self):
        return "'%s' %s" % (self.entry, self.name) class Field(bdec.entry.Entry):
    """A field represents data found in the binary file.

    A field can be of variable length, be non-byte aligned, be in one of many
    formats and encodings, and can reference previously decoded fields.
    """

    # Field format types
    TEXT = "text"
    INTEGER = "integer"
    HEX = "hex"
    BINARY = "binary"
    FLOAT = "float"

    _formats = [TEXT, INTEGER, HEX, BINARY, FLOAT]

    # Field 'encoding' types
    LITTLE_ENDIAN = "little endian"
    BIG_ENDIAN = "big endian"

    def __init__(self, name, length, format=BINARY, encoding=None, constraints=[]):
        bdec.entry.Entry.__init__(self, name, length, [], constraints)
        assert format in self._formats

        if encoding is None:
            if format == self.TEXT:
                encoding = "ascii"
            else:
                # We default to big endian for non text types, as little
                # endian requires data with a length of a multiple of 8
                encoding = self.BIG_ENDIAN

        self.format = format
        self.encoding = encoding

    def _get_context(self, query, context):
        try:
            result = query(context, self)
        except bdec.entry.MissingInstanceError:
            if not self.is_hidden():
                raise
            expected = self._get_expected()
            if expected is None:
                raise
            result = self.decode_value(expected)
        return result

    def __str__(self):
        result = "%s '%s'" % (self.format, self.name)
        if self.format not in [self.HEX, self.BINARY]:
            result += ' (%s)' % self.encoding
        return result

    def _decode_int(self, data):
        if self.encoding == self.LITTLE_ENDIAN:
            result = data.get_little_endian_integer()
        else:
            # If we aren't explicitly little endian, we become big endian.
            # This is because we can sometimes convert a non-integer to
            # an integer (eg: we may want to treat a string character as an
            # integer, to ensure we are in a given character range).
            result = int(data)
        return result

    def decode_value(self, data):
        """
        Get a python instance from a data object.
        """
        if self.format == self.BINARY:
            return data.copy(klass=_BinaryData)
        elif self.format == self.HEX:
            return data.copy(klass=_HexData)
        elif self.format == self.TEXT:
            result = data.text(self.encoding)
        elif self.format == self.INTEGER:
            result = self._decode_int(data)
        elif self.format == self.FLOAT:
            if self.encoding == self.LITTLE_ENDIAN:
                result = data.get_litten_endian_float()
            else:
                result = float(data)
        else:
            raise Exception("Unknown field format of '%s'!" % self.format)
        return result MAGIC_UNKNOWN_NAME = 'magic unknown param'
    IN = "in"
    OUT = "out"
class BadReferenceError(bdec.DecodeError):
class BadReferenceTypeError(bdec.DecodeError):
class UnknownReferenceError(BadReferenceError):
class MissingExpressionReferenceError(BadReferenceError):
class _FailedToResolveError(Exception):
class Param(object):
class Local(object):
class _Parameters:
class EndEntryParameters(_Parameters):
class _VariableParam:
class ExpressionParameters(_Parameters):
class DataChecker:
class ResultParameters(_Parameters):
class CompoundParameters(_Parameters):
class EncodeResultParameters(_Parameters):
class EncodeExpressionParameters(_Parameters):
    def __init__(self, entry, context=[]):
    def __str__(self):
    def __init__(self, entry):
    def __str__(self):
    def __init__(self, entry, name, entries=[]):
    def __str__(self):
    def __init__(self, entry, missing):
    def __str__(self):
    def __init__(self, name):
    def __init__(self, name, direction, type):
    def __eq__(self, other):
    def __hash__(self):
    def __repr__(self):
    def __init__(self, name, type):
    def __eq__(self, other):
    def __hash__(self):
    def __repr__(self):
    def get_locals(self, entry):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def is_end_sequenceof(self, entry):
    def is_value_referenced(self, entry):
    def is_length_referenced(self, entry):
    def __init__(self, entries):
    def _populate_lookup(self, entry, intermediaries):
    def get_locals(self, entry):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def is_end_sequenceof(self, entry):
    def __init__(self, reference, direction, type):
    def __hash__(self):
    def __eq__(self, other):
    def __repr__(self):
    def get_type(self):
    def get_param(self):
    def __init__(self, entries):
    def _update_parent_tree(self, entry, parents, visited):
    def _update_recursive_input_params(self, entry, unreferenced_entries,
            param_source, visited, parents):
    def _find_child_using_param(self, entry, name):
    def _collect_references(self, expression):
    def _populate_references(self, entry, unreferenced_entries, entries_visited,
            entry_stack, recursive_entries, param_source):
    def _populate_parameter_source(self, entry, unreferenced_entries,
            param_source):
    def _populate_child_input_parameter_type(self, entry, name, param_type, visited):
    def is_output_param_used(self, entry, child, param):
    def _get_local_reference(self, entry, child, param):
    def _add_reference(self, entry, reference):
    def _add_out_params(self, entry, reference):
    def get_locals(self, entry):
    def _get_params(self, entry):
        def compare_references(left, right):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def is_value_referenced(self, entry):
    def is_length_referenced(self, entry):
    def __init__(self, entries):
    def _populate(self, entry, stack, intermediates):
    def _hide_children(self, entry):
    def contains_data(self, entry):
    def child_has_data(self, child):
    def __init__(self, entries):
    def get_locals(self, entry):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def __init__(self, parameter_queries):
    def get_locals(self, entry):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def is_end_sequenceof(self, entry):
    def is_value_referenced(self, entry):
    def is_length_referenced(self, entry):
    def __init__(self, entries):
    def get_locals(self, entry):
    def _invert(self, params):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def __init__(self, entries):
    def is_output_param_used(self, entry, child, param):
    def is_length_known(self, entry):
    def is_hidden(self, entry):
    def is_length_referenced(self, entry):
    def is_value_referenced(self, entry):
    def get_params(self, entry):
    def get_passed_variables(self, entry, child):
    def _populate_visible(self, entry, common, entries, visible=True):
    def _is_source_entry_independant(self, param_type, is_value_hidden):
    def get_locals(self, entry): class EntryType(VariableType):
    """Parameter value whose source is another entry."""
    def __init__(self, entry):
        self.entry = entry

    def __hash__(self):
        return hash(self.entry)

    def __eq__(self, other):
        if not isinstance(other, EntryType):
            return False
        return other.entry is self.entry

    def __repr__(self):
        return '(%s)&' % self.entry class IntegerType(VariableType):
    """Base class for describing the type of an integer."""
    def range(self, parameters, entries_stack=None):
        """Return a bdec.inspect.range.Range instance indicating the range of valid values."""
        raise NotImplementedError()

    def has_expected_value(self):
        """Is the value referenced by this entry constant or visible."""
        raise NotImplementedError()

    def is_reference_match(self, expression):
        """Is the bdec.expression.ReferenceExpression matching our type."""
        assert isinstance(expression, ReferenceExpression), "expected ReferenceExpression, got %s" % expression
        raise NotImplementedError() class EntryLengthType(IntegerType):
    """Parameter value whose source is the length of another entry."""
    def __init__(self, entry):
        self.entry = entry

    def __hash__(self):
        return hash(self.entry)

    def __eq__(self, other):
        return isinstance(other, EntryLengthType) and self.entry is other.entry

    def is_reference_match(self, expression):
        assert isinstance(expression, ReferenceExpression), "expected ReferenceExpression, got %s" % expression
        return isinstance(expression, LengthResult)

    def __repr__(self):
        return 'len{%s}' % self.entry

    def range(self, parameter, entries_stack=None):
        if self.entry.length is None:
            # We don't know how long this entry is.
            # TODO: We could try examining its children...
            return Range(0, None)
        return expression_range(self.entry.length, self.entry, parameter, entries_stack)

    def has_expected_value(self):
        return False class EntryValueType(IntegerType):
    """Parameter value whose source is the integer value of another entry."""
    def __init__(self, entry):
        self.entry = entry

    def __hash__(self):
        return hash(self.entry)

    def __eq__(self, other):
        return isinstance(other, EntryValueType) and self.entry is other.entry

    def range(self, parameters, entries_stack=None):
        if entries_stack is None:
            entries_stack = set()
        if self.entry in entries_stack:
            # We can't keep recursing...
            return Range()
        entries_stack.add(self.entry)
        if isinstance(self.entry, fld.Field):
            length_range = expression_range(self.entry.length, self.entry, parameters, entries_stack)
            # If our length is of a variable range, it can be very large.
            # Attempting to take a power of a large number takes a very long
            # time, is is quite meaningless; limit it to 64 bits.
            max_length = min(length_range.max, 64)
            result = Range(0, pow(2, max_length) - 1)
        elif isinstance(self.entry, seq.Sequence):
            result = expression_range(self.entry.value, self.entry, parameters, entries_stack)
        elif isinstance(self.entry, chc.Choice):
            ranges = [EntryValueType(child.entry).range(parameters, entries_stack) for child in self.entry.children]
            result = reduce(Range.union, ranges)
        else:
            raise NotImplementedError("Don't know how to query the value range of entry '%s'!'" % self.entry)
        entries_stack.remove(self.entry)

        for constraint in self.entry.constraints:
            result = result.intersect(constraint.range())
        return result

    def _is_value_known(self, entry):
        for constraint in entry.constraints:
            if isinstance(constraint, Equals):
                return True

        if isinstance(entry, seq.Sequence):
            if entry.value:
                # Check to see if the entry value is constant
                # TODO: We should examine the source parameters of this
                # value, instead of trying to execute it...
                try:
                    entry.value.evaluate({})
                    return True
                except UndecodedReferenceError:
                    pass
            return False
        elif isinstance(entry, chc.Choice):
            for child in entry.children:
                if not self._is_value_known(child.entry):
                    return False
            return True
        return False

    def has_expected_value(self):
        return self._is_value_known(self.entry)

    def is_reference_match(self, expression):
        assert isinstance(expression, ReferenceExpression), "expected ReferenceExpression, got %s" % expression
        return isinstance(expression, ValueResult)

    def __repr__(self):
        return '${%s}' % self.entry class Sequence(bdec.entry.Entry):
    """
    A sequence type protocol entry.

    A sequence protocol entry is made up of multiple other
    entry types, and they are decoded one after the other.
    All of the child protocol entries must be decoded for
    the sequence to successfully decode.

    A sequence object may be assigned a value, derived from
    the child elements. This allows techniques such as
    lookup tables, and alternate integer encoding methods.
    """

    def __init__(self, name, children, value=None, length=None, constraints=[]):
        bdec.entry.Entry.__init__(self, name, length, children, constraints)
        self.value = value

    def _range(self, ignore_entries):
        return sum((child.entry.range(ignore_entries) for child in self.children), bdec.entry.Range(0, 0)) class SequenceOf(bdec.entry.Entry):
    """
    A protocol entry representing a sequence of another protocol entry.

    The number of times the child entry will loop can be set in one of three
    ways;
     
     * It can loop for a specified amount of times
     * It can loop until a buffer is empty
     * It can loop until a child entry decodes
    """
    STOPPED = "stopped"
    ITERATING = "iterating"
    STOPPING = "stopping"

    def __init__(self, name, child, count=None, length=None, end_entries=[]):
        """
        count -- The number of times the child will repeat. If this value is
          None, the count will not be used.
        length -- The size of the buffer in bits. When the buffer is empty, the
          looping will stop. If None, the length will not be used.
        end_entries -- A list of child entries whose successful decode
          indicates the loop should stop.

        If neither count, length, or end_entries are used, the SequenceOf will
        fail to decode after using all of the available buffer.
        """
        bdec.entry.Entry.__init__(self, name, length, [child])
        if isinstance(count, int):
            count = Constant(count)
        assert count is None or isinstance(count, Expression)
        self.count = count
        self.end_entries = end_entries

    def _validate(self):
        bdec.entry.Entry._validate(self)
        for entry in self.end_entries:
            assert isinstance(entry, bdec.entry.Entry), "%s isn't an entry instance!" % str(entry) def parse(text):
    """
    Compile a length expression into an integer convertible object.

    :param name_lookup: A object to call to query a named integer 
        convertible object.
    return -- An Expression instance
    """
    from pyparsing import StringEnd, ParseException
    complete = _int_expression() + StringEnd()
    try:
        return complete.parseString(text)[0]
    except ParseException, ex:
        raise ExpressionError(ex) class ValueResult(ReferenceExpression):
    """
    Object returning the result of a entry when cast to an integer.
    """
    def param_name(self):
        return self.name

    def __repr__(self):
        return '${%s}' % self.name class Constant(Expression):
    def __init__(self, value):
        self.value = value
        
    def evaluate(self, context):
        return self.value

    def __repr__(self):
        if isinstance(self.value, dt.Data):
            value = self.value
            if len(value) % 8:
                # We can only convert bytes to hex, so added a '0' data
                # object in front.
                leading_bits = 8 - len(value) % 8
                value = dt.Data('\x00', start=0, end=leading_bits) + value
            return '0x%s' % value.get_hex()
        return str(self.value) class LengthResult(ReferenceExpression):
    """
    Object returning the length of a decoded entry.
    """
    def param_name(self):
        return self.name + ' length'

    def __repr__(self):
        return "len{%s}" % self.name class ArithmeticExpression(Expression):
    """
    Class to delay the operation of an integer operation.

    This is because some parts of an expression may not be accessible until
    the expression is used (for example, an expression object that
    references the decoded value of another field).
    """
    def __init__(self, op, left, right):
        self.op = op
        assert isinstance(left, Expression)
        assert isinstance(right, Expression)
        self.left = left
        self.right = right

    def evaluate(self, context):
        return self.op(self.left.evaluate(context), self.right.evaluate(context))

    def __repr__(self):
        lookup = {}
        for ops in _operators:
            lookup.update((op, name) for name, op in ops)
        return '(%s %s %s)' % (self.left, lookup[self.op], self.right)
import operator
import unittest
import bdec
from bdec.choice import Choice
from bdec.constraints import Equals, Maximum, Minimum
from bdec.data import Data
from bdec.entry import Child
from bdec.field import Field
from bdec.inspect.param import EncodeExpressionParameters, Param, \
        ResultParameters, Local, ExpressionParameters, BadReferenceError, \
        BadReferenceTypeError, EndEntryParameters, ShouldEndType, DataChecker
from bdec.inspect.type import EntryType, IntegerType, EntryLengthType, EntryValueType
from bdec.sequence import Sequence
from bdec.sequenceof import SequenceOf
from bdec.expression import parse, ValueResult, Constant, LengthResult, \
        ArithmeticExpression
    def __str__(self):
        return 'integer'

class TestExpressionParameters(unittest.TestCase):
    def test_direct_children(self):
        a = Field('a', 8)
        value = ValueResult('a')
        b = Field('b', value)
        spec = Sequence('blah', [a,b])

        vars = ExpressionParameters([spec])
        self.assertEqual([Local('a', _Integer())], vars.get_locals(spec))
        self.assertTrue(vars.is_value_referenced(a))
        self.assertFalse(vars.is_value_referenced(b))
        self.assertEqual([], vars.get_locals(a))

    def test_sub_children(self):
        a2 = Field('a2', 8)
        a1 = Sequence('a1', [a2])
        a = Sequence('a', [a1])
        value = ValueResult('a.a1.a2')
        b1 = Field('b1', value)
        b = Sequence('b', [b1])
        spec = Sequence('blah', [a,b])

        vars = ExpressionParameters([spec])
        self.assertEqual([Local('a.a1.a2', _Integer())], vars.get_locals(spec))
        # Note that despite containing a referenced entry, it isn't a local (as
        # it is passed up to the parent entry).
        self.assertEqual([], vars.get_locals(a))

        # Now check what parameters are passed in and out. Note that we check
        # that the name is correct for the context of the parameter.
        self.assertEqual([], vars.get_params(spec))
        self.assertEqual([Param('a2', Param.OUT, _Integer())], vars.get_params(a2))
        self.assertEqual([Param('a2', Param.OUT, _Integer())], vars.get_params(a1))
        self.assertEqual([Param('a1.a2', Param.OUT, _Integer())], vars.get_params(a))
        self.assertEqual([Param('a1.a2', Param.OUT, _Integer())], list(vars.get_passed_variables(a, a.children[0])))
        self.assertEqual([Param('a.a1.a2', Param.IN, _Integer())], vars.get_params(b))
        self.assertEqual([Param('a.a1.a2', Param.IN, _Integer())], vars.get_params(b1))
        self.assertEqual([Param('a.a1.a2', Param.IN, _Integer())], list(vars.get_passed_variables(b, b.children[0])))

    def test_length_reference(self):
        a1 = Field('a1', 8)
        a = Sequence('a', [a1])
        b1 = Field('b1', LengthResult('a'))
        b = Sequence('b', [b1])
        spec = Sequence('blah', [a,b])

        vars = ExpressionParameters([spec])
        self.assertEqual([Local('a length', _Integer())], vars.get_locals(spec))
        self.assertFalse(vars.is_length_referenced(a1))
        self.assertTrue(vars.is_length_referenced(a))
        self.assertEqual([Param('a length', Param.OUT, EntryLengthType(a))], vars.get_params(a))
        self.assertEqual([Param('a length', Param.IN, EntryLengthType(a))], vars.get_params(b))

    def test_sequence_value(self):
        # Define an integer with a custom byte ordering
        lower = Field('lower byte', 8)
        lower_value = ValueResult('lower byte')
        ignored = Field('ignored', 8)
        upper = Field('upper byte', 8)
        upper_value = ValueResult('upper byte')
        value = ArithmeticExpression(operator.__add__, ArithmeticExpression(operator.__mul__, upper_value, Constant(256)), lower_value)
        length = Sequence('length', [lower, ignored, upper], value)
        header = Sequence('header', [length])

        int_value = ValueResult('length')
        data = Field('data', int_value)
        spec = Sequence('blah', [length, data])

        vars = ExpressionParameters([spec])
        self.assertEquals([], vars.get_params(spec))
        self.assertTrue(vars.is_value_referenced(lower))
        self.assertFalse(vars.is_value_referenced(ignored))
        self.assertTrue(vars.is_value_referenced(upper))
        self.assertEqual([Local('lower byte', _Integer()), Local('upper byte', _Integer())], vars.get_locals(length))
        self.assertEqual([Param('lower byte', Param.OUT, _Integer())], vars.get_params(lower))
        self.assertEqual([Param('upper byte', Param.OUT, _Integer())], vars.get_params(upper))
        self.assertEqual([Param('length', Param.OUT, _Integer())], vars.get_params(length))

        self.assertEqual([Local('length', _Integer())], vars.get_locals(spec))
        self.assertEqual([Param('length', Param.IN, _Integer())], vars.get_params(data))

    def test_choice_reference(self):
        """
        Test the parameter names when we have items selected under a choice.
        """
        byte = Sequence('8 bit:', [Field('id', 8, constraints=[Equals(Data('\x00'))]), Field('length', 8)])
        word = Sequence('16 bit:', [Field('id', 8, constraints=[Equals(Data('\x01'))]), Field('length', 16)])
        length = Choice('variable integer', [byte, word])
        length_value = ValueResult('variable integer.length')
        data = Field('data', length_value)
        spec = Sequence('spec', [length, data])
        vars = ExpressionParameters([spec])

        self.assertFalse(vars.is_value_referenced(byte))
        self.assertTrue(vars.is_value_referenced(byte.children[1].entry))
        self.assertFalse(vars.is_value_referenced(word))
        self.assertTrue(vars.is_value_referenced(word.children[1].entry))
        self.assertEqual([Param('length', Param.OUT, _Integer())], vars.get_params(byte))
        self.assertEqual([Param('length', Param.OUT, _Integer())], vars.get_params(word))
        self.assertEqual([Param('length', Param.OUT, _Integer())], vars.get_params(length))
        self.assertEqual([], vars.get_locals(length))
        self.assertEqual([Param('length', Param.OUT, _Integer())], list(vars.get_passed_variables(length, length.children[0])))

        self.assertEqual([Local('variable integer.length', _Integer())], vars.get_locals(spec))
        self.assertEqual([Param('variable integer.length', Param.IN, _Integer())], vars.get_params(data))

    def test_reference_outside_of_choice(self):
        """
        Test passing in a parameter into choice options.
        """
        # Note that the 'integer' option has a fixed length...
        length = Field('length:', 8)
        length_value = ValueResult('length:')
        text = Sequence('text', [
            Field('id:',  8, constraints=[Equals(Data('\x00'))]),
            Field('value', length_value, Field.TEXT)])
        integer = Sequence('integer', [

            Field('id:',  8, constraints=[Equals(Data('\x01'))]),