Repository: holoviz/datashader (language: python)

Issue:
Remove dependency on `datashape`
[`datashape`](https://github.com/blaze/datashape) is unmaintained and hasn't had a release since the end of 2016. At this point it would probably be better to vendor the necessary parts. 


Discussion / hints:
Thanks, @dhirschfeld. Can't imagine it's a big job but I suspect none of us core developers has the time to tackle this in a short- to medium-scale timeframe.
Fair enough. Since it appears none of the deps specify a maximum version bound it probably doesn't hurt to keep it around for now. I'll let you decide if you want to close or keep this issue open...
I'd say definitely keep it open, never know when someone does have the time or some outside contributor (maybe you? 😄) wants to tackle it.

Fix patch:
diff --git a/datashader/datashape/__init__.py b/datashader/datashape/__init__.py
new file mode 100644
index 000000000..beb8c0f57
--- /dev/null
+++ b/datashader/datashape/__init__.py
@@ -0,0 +1,12 @@
+from __future__ import absolute_import
+
+from . import lexer, parser              # noqa (API import)
+from .coretypes import *                 # noqa (API import)
+from .predicates import *                # noqa (API import)
+from .typesets import *                  # noqa (API import)
+from .user import *                      # noqa (API import)
+from .type_symbol_table import *         # noqa (API import)
+from .discovery import discover          # noqa (API import)
+from .util import *                      # noqa (API import)
+from .promote import promote, optionify  # noqa (API import)
+from .error import DataShapeSyntaxError  # noqa (API import)
diff --git a/datashader/datashape/coretypes.py b/datashader/datashape/coretypes.py
new file mode 100644
index 000000000..eaf4d2a35
--- /dev/null
+++ b/datashader/datashape/coretypes.py
@@ -0,0 +1,1407 @@
+from __future__ import print_function, division, absolute_import
+
+"""
+This defines the DataShape type system, with unified
+shape and data type.
+"""
+
+import ctypes
+import operator
+
+from collections import OrderedDict
+from math import ceil
+
+from datashader import datashape
+
+import numpy as np
+
+from .py2help import (
+    _inttypes,
+    _strtypes,
+)
+from .internal_utils import IndexCallable, isidentifier
+
+
+# Classes of unit types.
+DIMENSION = 1
+MEASURE = 2
+
+
+class Type(type):
+    _registry = {}
+
+    def __new__(meta, name, bases, dct):
+        cls = super(Type, meta).__new__(meta, name, bases, dct)
+        # Don't register abstract classes
+        if not dct.get('abstract'):
+            Type._registry[name] = cls
+        return cls
+
+    @classmethod
+    def register(cls, name, type):
+        # Don't clobber existing types.
+        if name in cls._registry:
+            raise TypeError('There is another type registered with name %s'
+                            % name)
+
+        cls._registry[name] = type
+
+    @classmethod
+    def lookup_type(cls, name):
+        return cls._registry[name]
+
+
+class Mono(metaclass=Type):
+
+    """
+    Monotype are unqualified 0 parameters.
+
+    Each type must be reconstructable using its parameters:
+
+        type(datashape_type)(*type.parameters)
+    """
+
+    composite = False
+
+    def __init__(self, *params):
+        self._parameters = params
+
+    @property
+    def _slotted(self):
+        return hasattr(self, '__slots__')
+
+    @property
+    def parameters(self):
+        if self._slotted:
+            return tuple(getattr(self, slot) for slot in self.__slots__)
+        else:
+            return self._parameters
+
+    def info(self):
+        return type(self), self.parameters
+
+    def __eq__(self, other):
+        return (isinstance(other, Mono) and
+                self.shape == other.shape and
+                self.measure.info() == other.measure.info())
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __hash__(self):
+        try:
+            h = self._hash
+        except AttributeError:
+            h = self._hash = hash(self.shape) ^ hash(self.measure.info())
+        return h
+
+    @property
+    def shape(self):
+        return ()
+
+    def __len__(self):
+        return 1
+
+    def __getitem__(self, key):
+        return [self][key]
+
+    def __repr__(self):
+        return '%s(%s)' % (
+            type(self).__name__,
+            ', '.join(
+                (
+                    '%s=%r' % (slot, getattr(self, slot))
+                    for slot in self.__slots__
+                ) if self._slotted else
+                map(repr, self.parameters),
+            ),
+        )
+
+    # Monotypes are their own measure
+    @property
+    def measure(self):
+        return self
+
+    def subarray(self, leading):
+        """Returns a data shape object of the subarray with 'leading'
+        dimensions removed. In the case of a measure such as CType,
+        'leading' must be 0, and self is returned.
+        """
+        if leading >= 1:
+            raise IndexError(('Not enough dimensions in data shape '
+                              'to remove %d leading dimensions.') % leading)
+        else:
+            return self
+
+    def __mul__(self, other):
+        if isinstance(other, _strtypes):
+            from datashader import datashape
+            return datashape.dshape(other).__rmul__(self)
+        if isinstance(other, _inttypes):
+            other = Fixed(other)
+        if isinstance(other, DataShape):
+            return other.__rmul__(self)
+
+        return DataShape(self, other)
+
+    def __rmul__(self, other):
+        if isinstance(other, _strtypes):
+            from datashader import datashape
+            return self * datashape.dshape(other)
+        if isinstance(other, _inttypes):
+            other = Fixed(other)
+
+        return DataShape(other, self)
+
+    def __getstate__(self):
+        return self.parameters
+
+    def __setstate__(self, state):
+        if self._slotted:
+            for slot, val in zip(self.__slots__, state):
+                setattr(self, slot, val)
+        else:
+            self._parameters = state
+
+    def to_numpy_dtype(self):
+        raise TypeError('DataShape %s is not NumPy-compatible' % self)
+
+
+class Unit(Mono):
+
+    """
+    Unit type that does not need to be reconstructed.
+    """
+
+    def __str__(self):
+        return type(self).__name__.lower()
+
+
+class Ellipsis(Mono):
+
+    """Ellipsis (...). Used to indicate a variable number of dimensions.
+
+    E.g.:
+
+        ... * float32    # float32 array w/ any number of dimensions
+        A... * float32   # float32 array w/ any number of dimensions,
+                        # associated with type variable A
+    """
+    __slots__ = 'typevar',
+
+    def __init__(self, typevar=None):
+        self.typevar = typevar
+
+    def __str__(self):
+        return str(self.typevar) + '...' if self.typevar else '...'
+
+    def __repr__(self):
+        return '%s(%r)' % (type(self).__name__, str(self))
+
+
+class Null(Unit):
+
+    """The null datashape."""
+    pass
+
+
+class Date(Unit):
+
+    """ Date type """
+    cls = MEASURE
+    __slots__ = ()
+
+    def to_numpy_dtype(self):
+        return np.dtype('datetime64[D]')
+
+
+class Time(Unit):
+
+    """ Time type """
+    cls = MEASURE
+    __slots__ = 'tz',
+
+    def __init__(self, tz=None):
+        if tz is not None and not isinstance(tz, _strtypes):
+            raise TypeError('tz parameter to time datashape must be a string')
+        # TODO validate against Olson tz database
+        self.tz = tz
+
+    def __str__(self):
+        basename = super(Time, self).__str__()
+        if self.tz is None:
+            return basename
+        else:
+            return '%s[tz=%r]' % (basename, str(self.tz))
+
+
+class DateTime(Unit):
+
+    """ DateTime type """
+    cls = MEASURE
+    __slots__ = 'tz',
+
+    def __init__(self, tz=None):
+        if tz is not None and not isinstance(tz, _strtypes):
+            raise TypeError('tz parameter to datetime datashape must be a '
+                            'string')
+        # TODO validate against Olson tz database
+        self.tz = tz
+
+    def __str__(self):
+        basename = super(DateTime, self).__str__()
+        if self.tz is None:
+            return basename
+        else:
+            return '%s[tz=%r]' % (basename, str(self.tz))
+
+    def to_numpy_dtype(self):
+        return np.dtype('datetime64[us]')
+
+
+_units = set(['ns', 'us', 'ms', 's', 'm', 'h', 'D', 'W', 'M', 'Y'])
+
+
+_unit_aliases = {
+    'year': 'Y',
+    'week': 'W',
+    'day': 'D',
+    'date': 'D',
+    'hour': 'h',
+    'second': 's',
+    'millisecond': 'ms',
+    'microsecond': 'us',
+    'nanosecond': 'ns'
+}
+
+
+def normalize_time_unit(s):
+    """ Normalize time input to one of 'year', 'second', 'millisecond', etc..
+    Example
+    -------
+    >>> normalize_time_unit('milliseconds')
+    'ms'
+    >>> normalize_time_unit('ms')
+    'ms'
+    >>> normalize_time_unit('nanoseconds')
+    'ns'
+    >>> normalize_time_unit('nanosecond')
+    'ns'
+    """
+    s = s.strip()
+    if s in _units:
+        return s
+    if s in _unit_aliases:
+        return _unit_aliases[s]
+    if s[-1] == 's' and len(s) > 2:
+        return normalize_time_unit(s.rstrip('s'))
+
+    raise ValueError("Do not understand time unit %s" % s)
+
+
+class TimeDelta(Unit):
+    cls = MEASURE
+    __slots__ = 'unit',
+
+    def __init__(self, unit='us'):
+        self.unit = normalize_time_unit(str(unit))
+
+    def __str__(self):
+        return 'timedelta[unit=%r]' % self.unit
+
+    def to_numpy_dtype(self):
+        return np.dtype('timedelta64[%s]' % self.unit)
+
+
+class Units(Unit):
+    """ Units type for values with physical units """
+    cls = MEASURE
+    __slots__ = 'unit', 'tp'
+
+    def __init__(self, unit, tp=None):
+        if not isinstance(unit, _strtypes):
+            raise TypeError('unit parameter to units datashape must be a '
+                            'string')
+        if tp is None:
+            tp = DataShape(float64)
+        elif not isinstance(tp, DataShape):
+            raise TypeError('tp parameter to units datashape must be a '
+                            'datashape type')
+        self.unit = unit
+        self.tp = tp
+
+    def __str__(self):
+        if self.tp == DataShape(float64):
+            return 'units[%r]' % (self.unit)
+        else:
+            return 'units[%r, %s]' % (self.unit, self.tp)
+
+
+class Bytes(Unit):
+
+    """ Bytes type """
+    cls = MEASURE
+    __slots__ = ()
+
+
+_canonical_string_encodings = {
+    u'A': u'A',
+    u'ascii': u'A',
+    u'U8': u'U8',
+    u'utf-8': u'U8',
+    u'utf_8': u'U8',
+    u'utf8': u'U8',
+    u'U16': u'U16',
+    u'utf-16': u'U16',
+    u'utf_16': u'U16',
+    u'utf16': u'U16',
+    u'U32': u'U32',
+    u'utf-32': u'U32',
+    u'utf_32': u'U32',
+    u'utf32': u'U32',
+}
+
+
+class String(Unit):
+
+    """ String container
+
+    >>> String()
+    ctype("string")
+    >>> String(10, 'ascii')
+    ctype("string[10, 'A']")
+    """
+    cls = MEASURE
+    __slots__ = 'fixlen', 'encoding'
+
+    def __init__(self, *args):
+        if len(args) == 0:
+            fixlen, encoding = None, None
+        if len(args) == 1:
+            if isinstance(args[0], _strtypes):
+                fixlen, encoding = None, args[0]
+            if isinstance(args[0], _inttypes):
+                fixlen, encoding = args[0], None
+        if len(args) == 2:
+            fixlen, encoding = args
+
+        encoding = encoding or 'U8'
+        if isinstance(encoding, str):
+            encoding = str(encoding)
+        try:
+            encoding = _canonical_string_encodings[encoding]
+        except KeyError:
+            raise ValueError('Unsupported string encoding %s' %
+                             repr(encoding))
+
+        self.encoding = encoding
+        self.fixlen = fixlen
+
+        # Put it in a canonical form
+
+    def __str__(self):
+        if self.fixlen is None and self.encoding == 'U8':
+            return 'string'
+        elif self.fixlen is not None and self.encoding == 'U8':
+            return 'string[%i]' % self.fixlen
+        elif self.fixlen is None and self.encoding != 'U8':
+            return 'string[%s]' % repr(self.encoding).strip('u')
+        else:
+            return 'string[%i, %s]' % (self.fixlen,
+                                       repr(self.encoding).strip('u'))
+
+    def __repr__(self):
+        s = str(self)
+        return 'ctype("%s")' % s.encode('unicode_escape').decode('ascii')
+
+    def to_numpy_dtype(self):
+        """
+        >>> String().to_numpy_dtype()
+        dtype('O')
+        >>> String(30).to_numpy_dtype()
+        dtype('<U30')
+        >>> String(30, 'A').to_numpy_dtype()
+        dtype('S30')
+        """
+        if self.fixlen:
+            if self.encoding == 'A':
+                return np.dtype('S%d' % self.fixlen)
+            else:
+                return np.dtype('U%d' % self.fixlen)
+
+        # Create a dtype with metadata indicating it's
+        # a string in the same style as the h5py special_dtype
+        return np.dtype('O', metadata={'vlen': str})
+
+
+class Decimal(Unit):
+
+    """Decimal type corresponding to SQL Decimal/Numeric types.
+
+    The first parameter passed specifies the number of digits of precision that
+    the Decimal contains. If an additional parameter is given, it represents
+    the scale, or number of digits of precision that are after the decimal
+    point.
+
+    The Decimal type makes no requirement of how it is to be stored in memory,
+    therefore, the number of bytes needed to store a Decimal for a given
+    precision will vary based on the platform where it is used.
+
+    Examples
+    --------
+    >>> Decimal(18)
+    Decimal(precision=18, scale=0)
+    >>> Decimal(7, 4)
+    Decimal(precision=7, scale=4)
+    >>> Decimal(precision=11, scale=2)
+    Decimal(precision=11, scale=2)
+    """
+
+    cls = MEASURE
+    __slots__ = 'precision', 'scale'
+
+    def __init__(self, precision, scale=0):
+        self.precision = precision
+        self.scale = scale
+
+    def __str__(self):
+        return 'decimal[precision={precision}, scale={scale}]'.format(
+            precision=self.precision, scale=self.scale
+        )
+
+    def to_numpy_dtype(self):
+        """Convert a decimal datashape to a NumPy dtype.
+
+        Note that floating-point (scale > 0) precision will be lost converting
+        to NumPy floats.
+
+        Examples
+        --------
+        >>> Decimal(18).to_numpy_dtype()
+        dtype('int64')
+        >>> Decimal(7,4).to_numpy_dtype()
+        dtype('float64')
+        """
+
+        if self.scale == 0:
+            if self.precision <= 2:
+                return np.dtype(np.int8)
+            elif self.precision <= 4:
+                return np.dtype(np.int16)
+            elif self.precision <= 9:
+                return np.dtype(np.int32)
+            elif self.precision <= 18:
+                return np.dtype(np.int64)
+            else:
+                raise TypeError(
+                    'Integer Decimal precision > 18 is not NumPy-compatible')
+        else:
+            return np.dtype(np.float64)
+
+
+class DataShape(Mono):
+
+    """
+    Composite container for datashape elements.
+
+    Elements of a datashape like ``Fixed(3)``, ``Var()`` or ``int32`` are on,
+    on their own, valid datashapes.  These elements are collected together into
+    a composite ``DataShape`` to be complete.
+
+    This class is not intended to be used directly.  Instead, use the utility
+    ``dshape`` function to create datashapes from strings or datashape
+    elements.
+
+    Examples
+    --------
+
+    >>> from datashader.datashape import Fixed, int32, DataShape, dshape
+
+    >>> DataShape(Fixed(5), int32)  # Rare to DataShape directly
+    dshape("5 * int32")
+
+    >>> dshape('5 * int32')         # Instead use the dshape function
+    dshape("5 * int32")
+
+    >>> dshape([Fixed(5), int32])   # It can even do construction from elements
+    dshape("5 * int32")
+
+    See Also
+    --------
+    datashape.dshape
+    """
+    composite = False
+
+    def __init__(self, *parameters, **kwds):
+        if len(parameters) == 1 and isinstance(parameters[0], _strtypes):
+            raise TypeError("DataShape constructor for internal use.\n"
+                            "Use dshape function to convert strings into "
+                            "datashapes.\nTry:\n\tdshape('%s')"
+                            % parameters[0])
+        if len(parameters) > 0:
+            self._parameters = tuple(map(_launder, parameters))
+            if getattr(self._parameters[-1], 'cls', MEASURE) != MEASURE:
+                raise TypeError(('Only a measure can appear on the'
+                                 ' last position of a datashape, not %s') %
+                                repr(self._parameters[-1]))
+            for dim in self._parameters[:-1]:
+                if getattr(dim, 'cls', DIMENSION) != DIMENSION:
+                    raise TypeError(('Only dimensions can appear before the'
+                                     ' last position of a datashape, not %s') %
+                                    repr(dim))
+        else:
+            raise ValueError('the data shape should be constructed from 2 or'
+                             ' more parameters, only got %s' % len(parameters))
+        self.composite = True
+        self.name = kwds.get('name')
+
+        if self.name:
+            type(type(self))._registry[self.name] = self
+
+    def __len__(self):
+        return len(self.parameters)
+
+    def __getitem__(self, index):
+        return self.parameters[index]
+
+    def __str__(self):
+        return self.name or ' * '.join(map(str, self.parameters))
+
+    def __repr__(self):
+        s = pprint(self)
+        if '\n' in s:
+            return 'dshape("""%s""")' % s
+        else:
+            return 'dshape("%s")' % s
+
+    @property
+    def shape(self):
+        return self.parameters[:-1]
+
+    @property
+    def measure(self):
+        return self.parameters[-1]
+
+    def subarray(self, leading):
+        """Returns a data shape object of the subarray with 'leading'
+        dimensions removed.
+
+        >>> from datashader.datashape import dshape
+        >>> dshape('1 * 2 * 3 * int32').subarray(1)
+        dshape("2 * 3 * int32")
+        >>> dshape('1 * 2 * 3 * int32').subarray(2)
+        dshape("3 * int32")
+        """
+        if leading >= len(self.parameters):
+            raise IndexError('Not enough dimensions in data shape '
+                             'to remove %d leading dimensions.' % leading)
+        elif leading in [len(self.parameters) - 1, -1]:
+            return DataShape(self.parameters[-1])
+        else:
+            return DataShape(*self.parameters[leading:])
+
+    def __rmul__(self, other):
+        if isinstance(other, _inttypes):
+            other = Fixed(other)
+        return DataShape(other, *self)
+
+    @property
+    def subshape(self):
+        return IndexCallable(self._subshape)
+
+    def _subshape(self, index):
+        """ The DataShape of an indexed subarray
+
+        >>> from datashader.datashape import dshape
+
+        >>> ds = dshape('var * {name: string, amount: int32}')
+        >>> print(ds.subshape[0])
+        {name: string, amount: int32}
+
+        >>> print(ds.subshape[0:3])
+        3 * {name: string, amount: int32}
+
+        >>> print(ds.subshape[0:7:2, 'amount'])
+        4 * int32
+
+        >>> print(ds.subshape[[1, 10, 15]])
+        3 * {name: string, amount: int32}
+
+        >>> ds = dshape('{x: int, y: int}')
+        >>> print(ds.subshape['x'])
+        int32
+
+        >>> ds = dshape('10 * var * 10 * int32')
+        >>> print(ds.subshape[0:5, 0:3, 5])
+        5 * 3 * int32
+
+        >>> ds = dshape('var * {name: string, amount: int32, id: int32}')
+        >>> print(ds.subshape[:, [0, 2]])
+        var * {name: string, id: int32}
+
+        >>> ds = dshape('var * {name: string, amount: int32, id: int32}')
+        >>> print(ds.subshape[:, ['name', 'id']])
+        var * {name: string, id: int32}
+
+        >>> print(ds.subshape[0, 1:])
+        {amount: int32, id: int32}
+        """
+        from .predicates import isdimension
+        if isinstance(index, _inttypes) and isdimension(self[0]):
+            return self.subarray(1)
+        if isinstance(self[0], Record) and isinstance(index, _strtypes):
+            return self[0][index]
+        if isinstance(self[0], Record) and isinstance(index, _inttypes):
+            return self[0].parameters[0][index][1]
+        if isinstance(self[0], Record) and isinstance(index, list):
+            rec = self[0]
+            # Translate strings to corresponding integers
+            index = [self[0].names.index(i) if isinstance(i, _strtypes) else i
+                     for i in index]
+            return DataShape(Record([rec.parameters[0][i] for i in index]))
+        if isinstance(self[0], Record) and isinstance(index, slice):
+            rec = self[0]
+            return DataShape(Record(rec.parameters[0][index]))
+        if isinstance(index, list) and isdimension(self[0]):
+            return len(index) * self.subarray(1)
+        if isinstance(index, slice):
+            if isinstance(self[0], Fixed):
+                n = int(self[0])
+                start = index.start or 0
+                stop = index.stop or n
+                if start < 0:
+                    start = n + start
+                if stop < 0:
+                    stop = n + stop
+                count = stop - start
+            else:
+                start = index.start or 0
+                stop = index.stop
+                if not stop:
+                    count = -start if start < 0 else var
+                if (stop is not None and start is not None and stop >= 0 and
+                        start >= 0):
+                    count = stop - start
+                else:
+                    count = var
+
+            if count != var and index.step is not None:
+                count = int(ceil(count / index.step))
+
+            return count * self.subarray(1)
+        if isinstance(index, tuple):
+            if not index:
+                return self
+            elif index[0] is None:
+                return 1 * self._subshape(index[1:])
+            elif len(index) == 1:
+                return self._subshape(index[0])
+            else:
+                ds = self.subarray(1)._subshape(index[1:])
+                return (self[0] * ds)._subshape(index[0])
+        raise TypeError('invalid index value %s of type %r' %
+                        (index, type(index).__name__))
+
+    def __setstate__(self, state):
+        self._parameters = state
+        self.composite = True
+        self.name = None
+
+
+numpy_provides_missing = frozenset((Date, DateTime, TimeDelta))
+
+
+class Option(Mono):
+
+    """
+    Measure types which may or may not hold data. Makes no
+    indication of how this is implemented in memory.
+    """
+    __slots__ = 'ty',
+
+    def __init__(self, ds):
+        self.ty = _launder(ds)
+
+    @property
+    def shape(self):
+        return self.ty.shape
+
+    @property
+    def itemsize(self):
+        return self.ty.itemsize
+
+    def __str__(self):
+        return '?%s' % self.ty
+
+    def to_numpy_dtype(self):
+        if type(self.ty) in numpy_provides_missing:
+            return self.ty.to_numpy_dtype()
+        raise TypeError('DataShape measure %s is not NumPy-compatible' % self)
+
+
+class CType(Unit):
+
+    """
+    Symbol for a sized type mapping uniquely to a native type.
+    """
+    cls = MEASURE
+    __slots__ = 'name', '_itemsize', '_alignment'
+
+    def __init__(self, name, itemsize, alignment):
+        self.name = name
+        self._itemsize = itemsize
+        self._alignment = alignment
+        Type.register(name, self)
+
+    @classmethod
+    def from_numpy_dtype(self, dt):
+        """
+        From Numpy dtype.
+
+        >>> from datashader.datashape import CType
+        >>> from numpy import dtype
+        >>> CType.from_numpy_dtype(dtype('int32'))
+        ctype("int32")
+        >>> CType.from_numpy_dtype(dtype('i8'))
+        ctype("int64")
+        >>> CType.from_numpy_dtype(dtype('M8'))
+        DateTime(tz=None)
+        >>> CType.from_numpy_dtype(dtype('U30'))
+        ctype("string[30, 'U32']")
+        """
+        try:
+            return Type.lookup_type(dt.name)
+        except KeyError:
+            pass
+        if np.issubdtype(dt, np.datetime64):
+            unit, _ = np.datetime_data(dt)
+            defaults = {'D': date_, 'Y': date_, 'M': date_, 'W': date_}
+            return defaults.get(unit, datetime_)
+        elif np.issubdtype(dt, np.timedelta64):
+            unit, _ = np.datetime_data(dt)
+            return TimeDelta(unit=unit)
+        elif np.issubdtype(dt, np.unicode_):
+            return String(dt.itemsize // 4, 'U32')
+        elif np.issubdtype(dt, np.str_) or np.issubdtype(dt, np.bytes_):
+            return String(dt.itemsize, 'ascii')
+        raise NotImplementedError("NumPy datatype %s not supported" % dt)
+
+    @property
+    def itemsize(self):
+        """The size of one element of this type."""
+        return self._itemsize
+
+    @property
+    def alignment(self):
+        """The alignment of one element of this type."""
+        return self._alignment
+
+    def to_numpy_dtype(self):
+        """
+        To Numpy dtype.
+        """
+        # TODO: Fixup the complex type to how numpy does it
+        name = self.name
+        return np.dtype({
+            'complex[float32]': 'complex64',
+            'complex[float64]': 'complex128'
+        }.get(name, name))
+
+    def __str__(self):
+        return self.name
+
+    def __repr__(self):
+        s = str(self)
+        return 'ctype("%s")' % s.encode('unicode_escape').decode('ascii')
+
+
+class Fixed(Unit):
+
+    """
+    Fixed dimension.
+    """
+    cls = DIMENSION
+    __slots__ = 'val',
+
+    def __init__(self, i):
+        # Use operator.index, so Python integers, numpy int scalars, etc work
+        i = operator.index(i)
+
+        if i < 0:
+            raise ValueError('Fixed dimensions must be positive')
+
+        self.val = i
+
+    def __index__(self):
+        return self.val
+
+    def __int__(self):
+        return self.val
+
+    def __eq__(self, other):
+        return (type(other) is Fixed and self.val == other.val or
+                isinstance(other, _inttypes) and self.val == other)
+
+    __hash__ = Mono.__hash__
+
+    def __str__(self):
+        return str(self.val)
+
+
+class Var(Unit):
+
+    """ Variable dimension """
+    cls = DIMENSION
+    __slots__ = ()
+
+
+class TypeVar(Unit):
+
+    """
+    A free variable in the signature. Not user facing.
+    """
+    # cls could be MEASURE or DIMENSION, depending on context
+    __slots__ = 'symbol',
+
+    def __init__(self, symbol):
+        if not symbol[0].isupper():
+            raise ValueError(('TypeVar symbol %r does not '
+                              'begin with a capital') % symbol)
+        self.symbol = symbol
+
+    def __str__(self):
+        return str(self.symbol)
+
+
+class Function(Mono):
+    """Function signature type
+    """
+    @property
+    def restype(self):
+        return self.parameters[-1]
+
+    @property
+    def argtypes(self):
+        return self.parameters[:-1]
+
+    def __str__(self):
+        return '(%s) -> %s' % (
+            ', '.join(map(str, self.argtypes)), self.restype
+        )
+
+
+class Map(Mono):
+    __slots__ = 'key', 'value'
+
+    def __init__(self, key, value):
+        self.key = _launder(key)
+        self.value = _launder(value)
+
+    def __str__(self):
+        return '%s[%s, %s]' % (type(self).__name__.lower(),
+                               self.key,
+                               self.value)
+
+    def to_numpy_dtype(self):
+        return to_numpy_dtype(self)
+
+
+def _launder(x):
+    """ Clean up types prior to insertion into DataShape
+
+    >>> from datashader.datashape import dshape
+    >>> _launder(5)         # convert ints to Fixed
+    Fixed(val=5)
+    >>> _launder('int32')   # parse strings
+    ctype("int32")
+    >>> _launder(dshape('int32'))
+    ctype("int32")
+    >>> _launder(Fixed(5))  # No-op on valid parameters
+    Fixed(val=5)
+    """
+    if isinstance(x, _inttypes):
+        x = Fixed(x)
+    if isinstance(x, _strtypes):
+        x = datashape.dshape(x)
+    if isinstance(x, DataShape) and len(x) == 1:
+        return x[0]
+    if isinstance(x, Mono):
+        return x
+    return x
+
+
+class CollectionPrinter(object):
+
+    def __repr__(self):
+        s = str(self)
+        strs = ('"""%s"""' if '\n' in s else '"%s"') % s
+        return 'dshape(%s)' % strs
+
+
+class RecordMeta(Type):
+    @staticmethod
+    def _unpack_slice(s, idx):
+        if not isinstance(s, slice):
+            raise TypeError(
+                'invalid field specification at position %d.\n'
+                'fields must be formatted like: {name}:{type}' % idx,
+            )
+
+        name, type_ = packed = s.start, s.stop
+        if name is None:
+            raise TypeError('missing field name at position %d' % idx)
+        if not isinstance(name, str):
+            raise TypeError(
+                "field name at position %d ('%s') was not a string" % (
+                    idx, name,
+                ),
+            )
+        if type_ is None and s.step is None:
+            raise TypeError(
+                "missing type for field '%s' at position %d" % (name, idx))
+        if s.step is not None:
+            raise TypeError(
+                "unexpected slice step for field '%s' at position %d.\n"
+                "hint: you might have a second ':'" % (name, idx),
+            )
+
+        return packed
+
+    def __getitem__(self, types):
+        if not isinstance(types, tuple):
+            types = types,
+
+        return self(list(map(self._unpack_slice, types, range(len(types)))))
+
+
+class Record(CollectionPrinter, Mono, metaclass=RecordMeta):
+    """
+    A composite data structure of ordered fields mapped to types.
+
+    Properties
+    ----------
+
+    fields: tuple of (name, type) pairs
+        The only stored data, also the input to ``__init__``
+    dict: dict
+        A dictionary view of ``fields``
+    names: list of strings
+        A list of the names
+    types: list of datashapes
+        A list of the datashapes
+
+    Example
+    -------
+
+    >>> Record([['id', 'int'], ['name', 'string'], ['amount', 'real']])
+    dshape("{id: int32, name: string, amount: float64}")
+    """
+    cls = MEASURE
+
+    def __init__(self, fields):
+        """
+        Parameters
+        ----------
+        fields : list/OrderedDict of (name, type) entries
+            The fields which make up the record.
+        """
+        if isinstance(fields, OrderedDict):
+            fields = fields.items()
+        fields = list(fields)
+        names = [
+            str(name) if not isinstance(name, _strtypes) else name
+            for name, _ in fields
+        ]
+        types = [_launder(v) for _, v in fields]
+
+        if len(set(names)) != len(names):
+            for name in set(names):
+                names.remove(name)
+            raise ValueError("duplicate field names found: %s" % names)
+
+        self._parameters = tuple(zip(names, types)),
+
+    @property
+    def fields(self):
+        return self._parameters[0]
+
+    @property
+    def dict(self):
+        return dict(self.fields)
+
+    @property
+    def names(self):
+        return [n for n, t in self.fields]
+
+    @property
+    def types(self):
+        return [t for n, t in self.fields]
+
+    def to_numpy_dtype(self):
+        """
+        To Numpy record dtype.
+        """
+        return np.dtype([(str(name), to_numpy_dtype(typ))
+                         for name, typ in self.fields])
+
+    def __getitem__(self, key):
+        return self.dict[key]
+
+    def __str__(self):
+        return pprint(self)
+
+
+R = Record  # Alias for record literals
+
+
+def _format_categories(cats, n=10):
+    return '[%s%s]' % (
+        ', '.join(map(repr, cats[:n])),
+        ', ...' if len(cats) > n else ''
+    )
+
+
+class Categorical(Mono):
+    """Unordered categorical type.
+    """
+
+    __slots__ = 'categories', 'type', 'ordered'
+    cls = MEASURE
+
+    def __init__(self, categories, type=None, ordered=False):
+        self.categories = tuple(categories)
+        self.type = (type or datashape.discover(self.categories)).measure
+        self.ordered = ordered
+
+    def __str__(self):
+        return '%s[%s, type=%s, ordered=%s]' % (
+            type(self).__name__.lower(),
+            _format_categories(self.categories),
+            self.type,
+            self.ordered
+        )
+
+    def __repr__(self):
+        return '%s(categories=%s, type=%r, ordered=%s)' % (
+            type(self).__name__,
+            _format_categories(self.categories),
+            self.type,
+            self.ordered
+        )
+
+
+class Tuple(CollectionPrinter, Mono):
+
+    """
+    A product type.
+    """
+    __slots__ = 'dshapes',
+    cls = MEASURE
+
+    def __init__(self, dshapes):
+        """
+        Parameters
+        ----------
+        dshapes : list of dshapes
+            The datashapes which make up the tuple.
+        """
+        dshapes = [DataShape(ds) if not isinstance(ds, DataShape) else ds
+                   for ds in dshapes]
+        self.dshapes = tuple(dshapes)
+
+    def __str__(self):
+        return '(%s)' % ', '.join(map(str, self.dshapes))
+
+    def to_numpy_dtype(self):
+        """
+        To Numpy record dtype.
+        """
+        return np.dtype([('f%d' % i, to_numpy_dtype(typ))
+                         for i, typ in enumerate(self.parameters[0])])
+
+
+class JSON(Mono):
+
+    """ JSON measure """
+    cls = MEASURE
+    __slots__ = ()
+
+    def __str__(self):
+        return 'json'
+
+
+bool_ = CType('bool', 1, 1)
+char = CType('char', 1, 1)
+
+int8 = CType('int8', 1, 1)
+int16 = CType('int16', 2, ctypes.alignment(ctypes.c_int16))
+int32 = CType('int32', 4, ctypes.alignment(ctypes.c_int32))
+int64 = CType('int64', 8, ctypes.alignment(ctypes.c_int64))
+
+# int is an alias for int32
+int_ = int32
+Type.register('int', int_)
+
+uint8 = CType('uint8', 1, 1)
+uint16 = CType('uint16', 2, ctypes.alignment(ctypes.c_uint16))
+uint32 = CType('uint32', 4, ctypes.alignment(ctypes.c_uint32))
+uint64 = CType('uint64', 8, ctypes.alignment(ctypes.c_uint64))
+
+float16 = CType('float16', 2, ctypes.alignment(ctypes.c_uint16))
+float32 = CType('float32', 4, ctypes.alignment(ctypes.c_float))
+float64 = CType('float64', 8, ctypes.alignment(ctypes.c_double))
+# float128 = CType('float128', 16)
+
+# real is an alias for float64
+real = float64
+Type.register('real', real)
+
+complex_float32 = CType('complex[float32]', 8,
+                        ctypes.alignment(ctypes.c_float))
+complex_float64 = CType('complex[float64]', 16,
+                        ctypes.alignment(ctypes.c_double))
+Type.register('complex64', complex_float32)
+complex64 = complex_float32
+
+Type.register('complex128', complex_float64)
+complex128 = complex_float64
+# complex256 = CType('complex256', 32)
+
+# complex is an alias for complex[float64]
+complex_ = complex_float64
+
+date_ = Date()
+time_ = Time()
+datetime_ = DateTime()
+timedelta_ = TimeDelta()
+Type.register('date', date_)
+Type.register('time', time_)
+Type.register('datetime', datetime_)
+Type.register('timedelta', timedelta_)
+
+null = Null()
+Type.register('null', null)
+
+c_byte = int8
+c_short = int16
+c_int = int32
+c_longlong = int64
+
+c_ubyte = uint8
+c_ushort = uint16
+c_ulonglong = uint64
+
+if ctypes.sizeof(ctypes.c_long) == 4:
+    c_long = int32
+    c_ulong = uint32
+else:
+    c_long = int64
+    c_ulong = uint64
+
+if ctypes.sizeof(ctypes.c_void_p) == 4:
+    intptr = c_ssize_t = int32
+    uintptr = c_size_t = uint32
+else:
+    intptr = c_ssize_t = int64
+    uintptr = c_size_t = uint64
+Type.register('intptr', intptr)
+Type.register('uintptr', uintptr)
+
+c_half = float16
+c_float = float32
+c_double = float64
+
+# TODO: Deal with the longdouble == one of float64/float80/float96/float128
+# situation
+
+# c_longdouble = float128
+
+half = float16
+single = float32
+double = float64
+
+void = CType('void', 0, 1)
+object_ = pyobj = CType('object',
+                        ctypes.sizeof(ctypes.py_object),
+                        ctypes.alignment(ctypes.py_object))
+
+na = Null
+NullRecord = Record(())
+bytes_ = Bytes()
+
+string = String()
+json = JSON()
+
+Type.register('float', c_float)
+Type.register('double', c_double)
+
+Type.register('bytes', bytes_)
+
+Type.register('string', String())
+
+var = Var()
+
+
+def to_numpy_dtype(ds):
+    """ Throw away the shape information and just return the
+    measure as NumPy dtype instance."""
+    if isinstance(ds.measure, datashape.coretypes.Map):
+        ds = ds.measure.key
+    return to_numpy(ds.measure)[1]
+
+
+def to_numpy(ds):
+    """
+    Downcast a datashape object into a Numpy (shape, dtype) tuple if
+    possible.
+
+    >>> from datashader.datashape import dshape, to_numpy
+    >>> to_numpy(dshape('5 * 5 * int32'))
+    ((5, 5), dtype('int32'))
+    >>> to_numpy(dshape('10 * string[30]'))
+    ((10,), dtype('<U30'))
+    >>> to_numpy(dshape('N * int32'))
+    ((-1,), dtype('int32'))
+    """
+    shape = []
+    if isinstance(ds, DataShape):
+        # The datashape dimensions
+        for dim in ds[:-1]:
+            if isinstance(dim, Fixed):
+                shape.append(int(dim))
+            elif isinstance(dim, TypeVar):
+                shape.append(-1)
+            else:
+                raise TypeError('DataShape dimension %s is not '
+                                'NumPy-compatible' % dim)
+
+        # The datashape measure
+        msr = ds[-1]
+    else:
+        msr = ds
+
+    return tuple(shape), msr.to_numpy_dtype()
+
+
+def from_numpy(shape, dt):
+    """
+    Upcast a (shape, dtype) tuple if possible.
+
+    >>> from datashader.datashape import from_numpy
+    >>> from numpy import dtype
+    >>> from_numpy((5, 5), dtype('int32'))
+    dshape("5 * 5 * int32")
+
+    >>> from_numpy((10,), dtype('S10'))
+    dshape("10 * string[10, 'A']")
+    """
+    dtype = np.dtype(dt)
+
+    if dtype.kind == 'S':
+        measure = String(dtype.itemsize, 'A')
+    elif dtype.kind == 'U':
+        measure = String(dtype.itemsize // 4, 'U32')
+    elif dtype.fields:
+        fields = [(name, dtype.fields[name]) for name in dtype.names]
+        rec = [(name, from_numpy(t.shape, t.base))  # recurse into nested dtype
+               for name, (t, _) in fields]  # _ is the byte offset: ignore it
+        measure = Record(rec)
+    else:
+        measure = CType.from_numpy_dtype(dtype)
+
+    if not shape:
+        return measure
+    return DataShape(*tuple(map(Fixed, shape)) + (measure,))
+
+
+def print_unicode_string(s):
+    try:
+        return s.decode('unicode_escape').encode('ascii')
+    except AttributeError:
+        return s
+
+
+def pprint(ds, width=80):
+    ''' Pretty print a datashape
+
+    >>> from datashader.datashape import dshape, pprint
+    >>> print(pprint(dshape('5 * 3 * int32')))
+    5 * 3 * int32
+
+    >>> ds = dshape("""
+    ... 5000000000 * {
+    ...     a: (int, float32, real, string, datetime),
+    ...     b: {c: 5 * int, d: var * 100 * float32}
+    ... }""")
+    >>> print(pprint(ds))
+    5000000000 * {
+      a: (int32, float32, float64, string, datetime),
+      b: {c: 5 * int32, d: var * 100 * float32}
+      }
+
+    Record measures print like full datashapes
+    >>> print(pprint(ds.measure, width=30))
+    {
+      a: (
+        int32,
+        float32,
+        float64,
+        string,
+        datetime
+        ),
+      b: {
+        c: 5 * int32,
+        d: var * 100 * float32
+        }
+      }
+
+    Control width of the result
+    >>> print(pprint(ds, width=30))
+    5000000000 * {
+      a: (
+        int32,
+        float32,
+        float64,
+        string,
+        datetime
+        ),
+      b: {
+        c: 5 * int32,
+        d: var * 100 * float32
+        }
+      }
+    >>>
+    '''
+    result = ''
+
+    if isinstance(ds, DataShape):
+        if ds.shape:
+            result += ' * '.join(map(str, ds.shape))
+            result += ' * '
+        ds = ds[-1]
+
+    if isinstance(ds, Record):
+        pairs = ['%s: %s' % (name if isidentifier(name) else
+                             repr(print_unicode_string(name)),
+                             pprint(typ, width - len(result) - len(name)))
+                 for name, typ in zip(ds.names, ds.types)]
+        short = '{%s}' % ', '.join(pairs)
+
+        if len(result + short) < width:
+            return result + short
+        else:
+            long = '{\n%s\n}' % ',\n'.join(pairs)
+            return result + long.replace('\n', '\n  ')
+
+    elif isinstance(ds, Tuple):
+        typs = [pprint(typ, width-len(result))
+                for typ in ds.dshapes]
+        short = '(%s)' % ', '.join(typs)
+        if len(result + short) < width:
+            return result + short
+        else:
+            long = '(\n%s\n)' % ',\n'.join(typs)
+            return result + long.replace('\n', '\n  ')
+    else:
+        result += str(ds)
+    return result
diff --git a/datashader/datashape/discovery.py b/datashader/datashape/discovery.py
new file mode 100644
index 000000000..c33be5e5a
--- /dev/null
+++ b/datashader/datashape/discovery.py
@@ -0,0 +1,446 @@
+from __future__ import print_function, division, absolute_import
+
+from collections import OrderedDict
+from datetime import datetime, date, time, timedelta
+from itertools import chain
+import re
+from textwrap import dedent
+from types import MappingProxyType
+from warnings import warn
+
+from dateutil.parser import parse as dateparse
+import numpy as np
+
+from .dispatch import dispatch
+from .coretypes import (int32, int64, float64, bool_, complex128, datetime_,
+                        Option, var, from_numpy, Tuple, null,
+                        Record, string, Null, DataShape, real, date_, time_,
+                        Unit, timedelta_, TimeDelta, object_, String)
+from .predicates import isdimension, isrecord
+from .py2help import _strtypes, _inttypes
+from .internal_utils import _toposort, groupby
+from .util import subclasses
+
+
+__all__ = ['discover']
+
+
+@dispatch(object)
+def discover(obj, **kwargs):
+    """ Discover datashape of object
+
+    A datashape encodes the datatypes and the shape/length of an object.
+    Discover returns the datashape of a Python object.  This object can refer
+    to external data.
+
+    Datashapes range from simple scalars
+
+    >>> discover(10)
+    ctype('int64')
+
+    To collections
+
+    >>> discover([[1, 2, 3], [4, 5, 6]])
+    dshape('2 * 3 * int64')
+
+    To record types and other objects
+
+    >>> x = np.array([('Alice', 100), ('Bob', 200)], dtype=[('name', 'S7'),
+    ...                                                     ('amount', 'i4')])
+    >>> discover(x)
+    dshape('2 * {name: string[7, "ascii"], amount: int32}')
+
+    See http://datashape.pydata.org/grammar.html#some-simple-examples
+    for more examples
+    """
+    type_name = type(obj).__name__
+    if hasattr(obj, 'shape') and hasattr(obj, 'dtype'):
+        warn(
+            dedent(
+                """\
+                array-like discovery is deperecated.
+                Please write an explicit discover function for type '%s'.
+                """ % type_name,
+            ),
+            DeprecationWarning,
+        )
+        return from_numpy(obj.shape, obj.dtype)
+    raise NotImplementedError("Don't know how to discover type %r" % type_name)
+
+
+@dispatch(_inttypes)
+def discover(i):  # noqa: F811
+    return int64
+
+
+npinttypes = tuple(chain.from_iterable((x for x in subclasses(icls)
+                                        if x.__name__.startswith(('int',
+                                                                  'uint')))
+                                       for icls in subclasses(np.integer)))
+
+
+@dispatch(bytes)
+def discover(b):  # noqa: F811
+    return String('A')
+
+
+@dispatch(npinttypes)
+def discover(n):  # noqa: F811
+    return from_numpy((), n.dtype)
+
+
+@dispatch(float)
+def discover(f):  # noqa: F811
+    return float64
+
+
+@dispatch(bool)
+def discover(b):  # noqa: F811
+    return bool_
+
+
+@dispatch(complex)
+def discover(z):  # noqa: F811
+    return complex128
+
+
+@dispatch(datetime)
+def discover(dt):  # noqa: F811
+    return datetime_
+
+
+@dispatch(timedelta)
+def discover(td):  # noqa: F811
+    return TimeDelta(unit='us')
+
+
+@dispatch(date)
+def discover(dt):  # noqa: F811
+    return date_
+
+
+@dispatch(time)
+def discover(t):  # noqa: F811
+    return time_
+
+
+@dispatch((type(None), Null))
+def discover(i):  # noqa: F811
+    return null
+
+
+bools = {'False': False,
+         'false': False,
+         'True': True,
+         'true': True}
+
+
+def timeparse(x, formats=('%H:%M:%S', '%H:%M:%S.%f')):
+    msg = ''
+    for format in formats:
+        try:
+            return datetime.strptime(x, format).time()
+        except ValueError as e:  # raises if it doesn't match the format
+            msg = str(e)
+    raise ValueError(msg)
+
+
+def deltaparse(x):
+    """Naive timedelta string parser
+
+    Examples
+    --------
+    >>> td = '1 day'
+    >>> deltaparse(td)
+    numpy.timedelta64(1,'D')
+    >>> deltaparse('1.2 days')  # doctest: +IGNORE_EXCEPTION_DETAIL
+    Traceback (most recent call last):
+        ...
+    ValueError: floating point timedelta value not supported
+    """
+    value, unit = re.split(r'\s+', x.strip())
+    value = float(value)
+    if not value.is_integer():
+        raise ValueError('floating point timedelta values not supported')
+    return np.timedelta64(int(value), TimeDelta(unit=unit).unit)
+
+
+string_coercions = int, float, bools.__getitem__, deltaparse, timeparse
+
+
+def is_zero_time(t):
+    return not (t.hour or t.minute or t.second or t.microsecond)
+
+
+@dispatch(_strtypes)
+def discover(s):  # noqa: F811
+    if not s:
+        return null
+
+    for f in string_coercions:
+        try:
+            return discover(f(s))
+        except (ValueError, KeyError):
+            pass
+
+    # don't let dateutil parse things like sunday, monday etc into dates
+    if s.isalpha() or s.isspace():
+        return string
+
+    try:
+        d = dateparse(s)
+    except (ValueError, OverflowError):  # OverflowError for stuff like 'INF...'
+        pass
+    else:
+        return date_ if is_zero_time(d.time()) else datetime_
+
+    return string
+
+
+@dispatch((tuple, list, set, frozenset))
+def discover(seq):  # noqa: F811
+    if not seq:
+        return var * string
+    unite = do_one([unite_identical, unite_base, unite_merge_dimensions])
+    # [(a, b), (a, c)]
+    if (all(isinstance(item, (tuple, list)) for item in seq) and
+            len(set(map(len, seq))) == 1):
+        columns = list(zip(*seq))
+        try:
+            types = [unite([discover(data) for data in column]).subshape[0]
+                     for column in columns]
+            unite = do_one([unite_identical, unite_merge_dimensions, Tuple])
+            return len(seq) * unite(types)
+        except AttributeError:  # no subshape available
+            pass
+
+    # [{k: v, k: v}, {k: v, k: v}]
+    if all(isinstance(item, dict) for item in seq):
+        keys = sorted(set.union(*(set(d) for d in seq)))
+        columns = [[item.get(key) for item in seq] for key in keys]
+        try:
+            types = [unite([discover(data) for data in column]).subshape[0]
+                     for column in columns]
+            return len(seq) * Record(list(zip(keys, types)))
+        except AttributeError:
+            pass
+
+    types = list(map(discover, seq))
+    return do_one([unite_identical, unite_merge_dimensions, Tuple])(types)
+
+
+def isnull(ds):
+    return ds == null or ds == DataShape(null)
+
+
+identity = lambda x: x
+
+# (a, b) implies that b can turn into a
+edges = [
+    (string, int64),  # E.g. int64 can be turned into a string
+    (string, real),
+    (string, date_),
+    (string, datetime_),
+    (string, timedelta_),
+    (string, bool_),
+    (datetime_, date_),
+    (int64, int32),
+    (real, int64),
+    (string, null)]
+
+numeric_edges = [
+    (int64, int32),
+    (real, int64),
+    (string, null)
+]
+
+
+# {a: [b, c]} a is more general than b or c
+edges = groupby(lambda x: x[1], edges)
+edges = dict((k, set(a for a, b in v)) for k, v in edges.items())
+toposorted = _toposort(edges)
+
+
+def lowest_common_dshape(dshapes):
+    """ Find common shared dshape
+
+    >>> lowest_common_dshape([int32, int64, float64])
+    ctype("float64")
+
+    >>> lowest_common_dshape([int32, int64])
+    ctype("int64")
+
+    >>> lowest_common_dshape([string, int64])
+    ctype("string")
+    """
+    common = set.intersection(*[descendents(edges, ds) for ds in dshapes])
+    if common and any(c in toposorted for c in common):
+        return min(common, key=toposorted.index)
+    raise ValueError("Not all dshapes are known.  Extend edges.")
+
+
+def unite_base(dshapes):
+    """ Performs lowest common dshape and also null aware
+
+    >>> unite_base([float64, float64, int64])
+    dshape("3 * float64")
+
+    >>> unite_base([int32, int64, null])
+    dshape("3 * ?int64")
+    """
+    dshapes = [unpack(ds) for ds in dshapes]
+    bynull = groupby(isnull, dshapes)
+    try:
+        good_dshapes = bynull[False]
+    except KeyError:
+        return len(dshapes) * null
+    if all(isinstance(ds, Unit) for ds in good_dshapes):
+        base = lowest_common_dshape(good_dshapes)
+    elif (all(isinstance(ds, Record) for ds in good_dshapes) and
+          ds.names == dshapes[0].names for ds in good_dshapes):
+        names = good_dshapes[0].names
+        base = Record([[name,
+                        unite_base([ds.dict.get(name, null) for ds in good_dshapes]).subshape[0]]
+                       for name in names])
+    if base:
+        if bynull.get(True):
+            base = Option(base)
+        return len(dshapes) * base
+
+
+def unite_identical(dshapes):
+    """
+
+    >>> unite_identical([int32, int32, int32])
+    dshape("3 * int32")
+    """
+    if len(set(dshapes)) == 1:
+        return len(dshapes) * dshapes[0]
+
+
+def unite_merge_dimensions(dshapes, unite=unite_identical):
+    """
+
+    >>> unite_merge_dimensions([10 * string, 10 * string])
+    dshape("2 * 10 * string")
+
+    >>> unite_merge_dimensions([10 * string, 20 * string])
+    dshape("2 * var * string")
+    """
+    n = len(dshapes)
+    if all(isinstance(ds, DataShape) and isdimension(ds[0]) for ds in dshapes):
+        dims = [ds[0] for ds in dshapes]
+        base = unite([ds.subshape[0] for ds in dshapes])
+        if base:
+            if len(set(dims)) == 1:
+                return n * (dims[0] * base.subshape[0])
+            else:
+                return n * (var * base.subshape[0])
+
+
+def do_one(funcs):
+    def f(inp):
+        for func in funcs:
+            result = func(inp)
+            if result:
+                return result
+        return inp
+    return f
+
+
+def unpack(ds):
+    """ Unpack DataShape constructor if unnecessary
+
+    Record packs inputs in DataShape containers.  This unpacks it.
+
+    >>> from datashader.datashape import dshape
+    >>> unpack(dshape('string'))
+    ctype("string")
+    """
+    if isinstance(ds, DataShape) and len(ds) == 1:
+        return ds[0]
+    else:
+        return ds
+
+
+@discover.register(dict)
+@discover.register(MappingProxyType)
+def _mapping_discover(m):
+    return Record((k, discover(m[k])) for k in sorted(m))
+
+
+@dispatch(OrderedDict)
+def discover(od):
+    return Record((k, discover(v)) for k, v in od.items())
+
+
+@dispatch(np.number)
+def discover(n):
+    return from_numpy((), type(n))
+
+
+@dispatch(np.timedelta64)
+def discover(n):
+    return from_numpy((), n)
+
+
+def is_string_array(x):
+    """ Is an array of strings
+
+    >>> is_string_array(np.array(['Hello', 'world'], dtype='O'))
+    True
+    >>> is_string_array(np.array(['Hello', None], dtype='O'))
+    False
+    """
+    return all(isinstance(i, _strtypes) for i in x.flat[:5].tolist())
+
+
+@dispatch(np.ndarray)
+def discover(x):
+    ds = from_numpy(x.shape, x.dtype)
+
+    # NumPy uses object dtype both for strings (which we want to call string)
+    # and for Python objects (which we want to call object)
+    # Lets look at the first few elements and check
+    if ds.measure == object_ and is_string_array(x):
+        return DataShape(*(ds.shape + (string,)))
+
+    if isrecord(ds.measure) and object_ in ds.measure.types:
+        m = Record([[name, string if typ == object_ and is_string_array(x[name])
+                     else typ]
+                    for name, typ in ds.measure.parameters[0]])
+        return DataShape(*(ds.shape + (m,)))
+    else:
+        return ds
+
+
+def descendents(d, x):
+    """
+
+    >>> d = {3: [2], 2: [1, 0], 5: [6]}
+    >>> sorted(descendents(d, 3))
+    [0, 1, 2, 3]
+    """
+    desc = set([x])
+    children = d.get(x, set())
+    while children:
+        children = set.union(*[set(d.get(kid, ())) for kid in desc])
+        children -= desc
+        desc.update(children)
+    return desc
+
+
+Mock = None
+try:
+    from unittest.mock import Mock
+except ImportError:
+    try:
+        from mock import Mock
+    except ImportError:
+        pass
+
+if Mock is not None:
+    @dispatch(Mock)
+    def discover(m):
+        raise NotImplementedError("Don't know how to discover mock objects")
+del Mock
diff --git a/datashader/datashape/dispatch.py b/datashader/datashape/dispatch.py
new file mode 100644
index 000000000..0e92cbfe3
--- /dev/null
+++ b/datashader/datashape/dispatch.py
@@ -0,0 +1,6 @@
+from multipledispatch import dispatch
+from functools import partial
+
+namespace = dict()
+
+dispatch = partial(dispatch, namespace=namespace)
diff --git a/datashader/datashape/error.py b/datashader/datashape/error.py
new file mode 100644
index 000000000..7fe0b75f0
--- /dev/null
+++ b/datashader/datashape/error.py
@@ -0,0 +1,47 @@
+"""Error handling"""
+
+syntax_error = """
+
+  File {filename}, line {lineno}
+    {line}
+    {pointer}
+
+{error}: {msg}
+"""
+
+class DataShapeSyntaxError(SyntaxError):
+    """
+    Makes datashape parse errors look like Python SyntaxError.
+    """
+    def __init__(self, lexpos, filename, text, msg=None):
+        self.lexpos = lexpos
+        self.filename = filename
+        self.text = text
+        self.msg = msg or 'invalid syntax'
+        self.lineno = text.count('\n', 0, lexpos) + 1
+        # Get the extent of the line with the error
+        linestart = text.rfind('\n', 0, lexpos)
+        if linestart < 0:
+            linestart = 0
+        else:
+            linestart = linestart + 1
+        lineend = text.find('\n', lexpos)
+        if lineend < 0:
+            lineend = len(text)
+        self.line = text[linestart:lineend]
+        self.col_offset = lexpos - linestart
+
+    def __str__(self):
+        pointer = ' ' * self.col_offset + '^'
+
+        return syntax_error.format(
+            filename=self.filename,
+            lineno=self.lineno,
+            line=self.line,
+            pointer=pointer,
+            msg=self.msg,
+            error=self.__class__.__name__,
+        )
+
+    def __repr__(self):
+        return str(self)
diff --git a/datashader/datashape/internal_utils.py b/datashader/datashape/internal_utils.py
new file mode 100644
index 000000000..701d2a95e
--- /dev/null
+++ b/datashader/datashape/internal_utils.py
@@ -0,0 +1,123 @@
+"""
+Utility functions that are unrelated to datashape
+
+Do not import datashape modules into this module.  See util.py in that case
+"""
+
+from __future__ import print_function, division, absolute_import
+
+import keyword
+import re
+
+
+class IndexCallable(object):
+    """ Provide getitem syntax for functions
+
+    >>> def inc(x):
+    ...     return x + 1
+
+    >>> I = IndexCallable(inc)
+    >>> I[3]
+    4
+    """
+    __slots__ = 'fn',
+
+    def __init__(self, fn):
+        self.fn = fn
+
+    def __getitem__(self, key):
+        return self.fn(key)
+
+
+def remove(predicate, seq):
+    return filter(lambda x: not predicate(x), seq)
+
+
+# Taken from theano/theano/gof/sched.py
+# Avoids licensing issues because this was written by Matthew Rocklin
+def reverse_dict(d):
+    """Reverses direction of dependence dict
+
+    >>> d = {'a': (1, 2), 'b': (2, 3), 'c':()}
+    >>> reverse_dict(d)  # doctest: +SKIP
+    {1: ('a',), 2: ('a', 'b'), 3: ('b',)}
+
+    :note: dict order are not deterministic. As we iterate on the
+        input dict, it make the output of this function depend on the
+        dict order. So this function output order should be considered
+        as undeterministic.
+
+    """
+    result = {}
+    for key in d:
+        for val in d[key]:
+            result[val] = result.get(val, tuple()) + (key, )
+    return result
+
+
+# Taken from theano/theano/gof/sched.py
+# Avoids licensing issues because this was written by Matthew Rocklin
+def _toposort(edges):
+    """ Topological sort algorithm by Kahn [1] - O(nodes + vertices)
+
+    inputs:
+        edges - a dict of the form {a: {b, c}} where b and c depend on a
+    outputs:
+        L - an ordered list of nodes that satisfy the dependencies of edges
+
+    >>> _toposort({1: (2, 3), 2: (3, )})
+    [1, 2, 3]
+
+    Closely follows the wikipedia page [2]
+
+    [1] Kahn, Arthur B. (1962), "Topological sorting of large networks",
+    Communications of the ACM
+    [2] http://en.wikipedia.org/wiki/Toposort#Algorithms
+    """
+    incoming_edges = reverse_dict(edges)
+    incoming_edges = dict((k, set(val)) for k, val in incoming_edges.items())
+    S = set((v for v in edges if v not in incoming_edges))
+    L = []
+
+    while S:
+        n = S.pop()
+        L.append(n)
+        for m in edges.get(n, ()):
+            assert n in incoming_edges[m]
+            incoming_edges[m].remove(n)
+            if not incoming_edges[m]:
+                S.add(m)
+    if any(incoming_edges.get(v) for v in edges):
+        raise ValueError("Input has cycles")
+    return L
+
+
+# Taken from toolz
+# Avoids licensing issues because this version was authored by Matthew Rocklin
+def groupby(func, seq):
+    """ Group a collection by a key function
+
+    >>> names = ['Alice', 'Bob', 'Charlie', 'Dan', 'Edith', 'Frank']
+    >>> groupby(len, names) # doctest: +SKIP
+    {3: ['Bob', 'Dan'], 5: ['Alice', 'Edith', 'Frank'], 7: ['Charlie']}
+
+    >>> iseven = lambda x: x % 2 == 0
+    >>> groupby(iseven, [1, 2, 3, 4, 5, 6, 7, 8])
+    {False: [1, 3, 5, 7], True: [2, 4, 6, 8]}
+
+    See Also:
+        ``countby``
+    """
+
+    d = dict()
+    for item in seq:
+        key = func(item)
+        if key not in d:
+            d[key] = list()
+        d[key].append(item)
+    return d
+
+
+def isidentifier(s):
+    return (keyword.iskeyword(s) or
+            re.match(r'^[_a-zA-Z][_a-zA-Z0-9]*$', s) is not None)
diff --git a/datashader/datashape/lexer.py b/datashader/datashape/lexer.py
new file mode 100644
index 000000000..b3e19358c
--- /dev/null
+++ b/datashader/datashape/lexer.py
@@ -0,0 +1,103 @@
+"""
+Lexer for the datashape grammar.
+"""
+
+from __future__ import absolute_import, division, print_function
+
+import re
+import ast
+import collections
+
+from . import error
+
+# This is updated to include all the token names from _tokens,
+# where e.g. _tokens[NAME_LOWER-1] is the entry for NAME_LOWER
+__all__ = ['lex', 'Token']
+
+def _str_val(s):
+    # Use the Python parser via the ast module to parse the string,
+    # since the string_escape and unicode_escape codecs do the wrong thing
+    return ast.parse('u' + s).body[0].value.s
+
+# A list of the token names, corresponding regex, and value extraction function
+_tokens = [
+    ('BOOLEAN',    r'True|False', ast.literal_eval),
+    ('NAME_LOWER', r'[a-z][a-zA-Z0-9_]*', lambda x : x),
+    ('NAME_UPPER', r'[A-Z][a-zA-Z0-9_]*', lambda x : x),
+    ('NAME_OTHER', r'_[a-zA-Z0-9_]*', lambda x : x),
+    ('ASTERISK',   r'\*'),
+    ('COMMA',      r','),
+    ('EQUAL',      r'='),
+    ('COLON',      r':'),
+    ('LBRACKET',   r'\['),
+    ('RBRACKET',   r'\]'),
+    ('LBRACE',     r'\{'),
+    ('RBRACE',     r'\}'),
+    ('LPAREN',     r'\('),
+    ('RPAREN',     r'\)'),
+    ('ELLIPSIS',   r'\.\.\.'),
+    ('RARROW',     r'->'),
+    ('QUESTIONMARK', r'\?'),
+    ('INTEGER',    r'0(?![0-9])|-?[1-9][0-9]*', int),
+    ('STRING', (r"""(?:"(?:[^"\n\r\\]|(?:\\u[0-9a-fA-F]{4})|(?:\\["bfnrt]))*")|""" +
+                r"""(?:'(?:[^'\n\r\\]|(?:\\u[0-9a-fA-F]{4})|(?:\\['bfnrt]))*')"""),
+                _str_val),
+]
+
+# Dynamically add all the token indices to globals() and __all__
+__all__.extend(tok[0] for tok in _tokens)
+globals().update((tok[0], i) for i, tok in enumerate(_tokens, 1))
+
+# Regex for skipping whitespace and comments
+_whitespace = r'(?:\s|(?:#.*$))*'
+
+# Compile the token-matching and whitespace-matching regular expressions
+_tokens_re = re.compile('|'.join('(' + tok[1] + ')' for tok in _tokens),
+                        re.MULTILINE)
+_whitespace_re = re.compile(_whitespace, re.MULTILINE)
+
+Token = collections.namedtuple('Token', 'id, name, span, val')
+
+def lex(ds_str):
+    """A generator which lexes a datashape string into a
+    sequence of tokens.
+
+    Example
+    -------
+
+        import datashape
+        s = '   -> ... A... "string" 1234 Blah _eil(# comment'
+        print('lexing %r' % s)
+        for tok in datashape.lexer.lex(s):
+            print(tok.id, tok.name, tok.span, repr(tok.val))
+    """
+    pos = 0
+    # Skip whitespace
+    m = _whitespace_re.match(ds_str, pos)
+    if m:
+        pos = m.end()
+    while pos < len(ds_str):
+        # Try to match a token
+        m = _tokens_re.match(ds_str, pos)
+        if m:
+            # m.lastindex gives us which group was matched, which
+            # is one greater than the index into the _tokens list.
+            id = m.lastindex
+            tokinfo = _tokens[id - 1]
+            name = tokinfo[0]
+            span = m.span()
+            if len(tokinfo) > 2:
+                val = tokinfo[2](ds_str[span[0]:span[1]])
+            else:
+                val = None
+            pos = m.end()
+            yield Token(id, name, span, val)
+        else:
+            raise error.DataShapeSyntaxError(pos, '<nofile>',
+                                             ds_str,
+                                             'Invalid DataShape token')
+        # Skip whitespace
+        m = _whitespace_re.match(ds_str, pos)
+        if m:
+            pos = m.end()
+
diff --git a/datashader/datashape/parser.py b/datashader/datashape/parser.py
new file mode 100644
index 000000000..aecab52dc
--- /dev/null
+++ b/datashader/datashape/parser.py
@@ -0,0 +1,613 @@
+"""
+Parser for the datashape grammar.
+"""
+
+from __future__ import absolute_import, division, print_function
+
+from . import lexer, error
+# TODO: Remove coretypes dependency, make 100% of interaction through
+#       the type symbol table
+from . import coretypes
+
+__all__ = ['parse']
+
+
+class DataShapeParser(object):
+    """A DataShape parser object."""
+    def __init__(self, ds_str, sym):
+        # The datashape string being parsed
+        self.ds_str = ds_str
+        # Symbol tables for dimensions, dtypes, and type constructors for each
+        self.sym = sym
+        # The lexer
+        self.lex = lexer.lex(ds_str)
+        # The array of tokens self.lex has already produced
+        self.tokens = []
+        # The token currently being examined, and
+        # the end position, set when self.lex is exhausted
+        self.pos = -1
+        self.end_pos = None
+        # Advance to the first token
+        self.advance_tok()
+
+    def advance_tok(self):
+        """Advances self.pos by one, if it is not already at the end."""
+        if self.pos != self.end_pos:
+            self.pos = self.pos + 1
+            try:
+                # If self.pos has not been backtracked,
+                # we need to request a new token from the lexer
+                if self.pos >= len(self.tokens):
+                    self.tokens.append(next(self.lex))
+            except StopIteration:
+                # Create an EOF token, whose span starts at the
+                # end of the last token to use for error messages
+                if len(self.tokens) > 0:
+                    span = (self.tokens[self.pos-1].span[1],)*2
+                else:
+                    span = (0, 0)
+                self.tokens.append(lexer.Token(None, None, span, None))
+                self.end_pos = self.pos
+
+    @property
+    def tok(self):
+        return self.tokens[self.pos]
+
+    def raise_error(self, errmsg):
+        raise error.DataShapeSyntaxError(self.tok.span[0], '<nofile>',
+                                         self.ds_str, errmsg)
+
+    def parse_homogeneous_list(self, parse_item, sep_tok_id, errmsg,
+                               trailing_sep=False):
+        """
+        <item>_list : <item> <SEP> <item>_list
+                    | <item>
+
+        Returns a list of <item>s, or None.
+        """
+        saved_pos = self.pos
+        # Parse zero or more "<item> <SEP>" repetitions
+        items = []
+        item = True
+        while item is not None:
+            # Parse the <item>
+            item = parse_item()
+            if item is not None:
+                items.append(item)
+                if self.tok.id == sep_tok_id:
+                    # If a <SEP> is next, there are more items
+                    self.advance_tok()
+                else:
+                    # Otherwise we've reached the end
+                    return items
+            else:
+                if len(items) > 0:
+                    if trailing_sep:
+                        return items
+                    else:
+                        # If we already saw "<item> <SEP>" at least once,
+                        # we can point at the more specific position within
+                        # the list of <item>s where the error occurred
+                        self.raise_error(errmsg)
+                else:
+                    self.pos = saved_pos
+                    return None
+
+    def syntactic_sugar(self, symdict, name, dshapemsg, error_pos=None):
+        """
+        Looks up a symbol in the provided symbol table dictionary for
+        syntactic sugar, raising a standard error message if the symbol
+        is missing.
+
+        Parameters
+        ----------
+        symdict : symbol table dictionary
+            One of self.sym.dtype, self.sym.dim,
+            self.sym.dtype_constr, or self.sym.dim_constr.
+        name : str
+            The name of the symbol to look up.
+        dshapemsg : str
+            The datashape construct this lookup is for, e.g.
+            '{...} dtype constructor'.
+        error_pos : int, optional
+            The position in the token stream at which to flag the error.
+        """
+        entry = symdict.get(name)
+        if entry is not None:
+            return entry
+        else:
+            if error_pos is not None:
+                self.pos = error_pos
+            self.raise_error(('Symbol table missing "%s" ' +
+                             'entry for %s') % (name, dshapemsg))
+
+    def parse_datashape(self):
+        """
+        datashape : datashape_nooption
+                  | QUESTIONMARK datashape_nooption
+                  | EXCLAMATIONMARK datashape_nooption
+
+        Returns a datashape object or None.
+        """
+        tok = self.tok
+        constructors = {lexer.QUESTIONMARK: 'option'}
+        if tok.id in constructors:
+            self.advance_tok()
+            saved_pos = self.pos
+            ds = self.parse_datashape_nooption()
+            if ds is not None:
+                # Look in the dtype symbol table for the option type constructor
+                option = self.syntactic_sugar(self.sym.dtype_constr,
+                                              constructors[tok.id],
+                                              '%s dtype construction' %
+                                              constructors[tok.id],
+                                              saved_pos - 1)
+                return coretypes.DataShape(option(ds))
+        else:
+            return self.parse_datashape_nooption()
+
+    def parse_datashape_nooption(self):
+        """
+        datashape_nooption : dim ASTERISK datashape
+                           | dtype
+
+        Returns a datashape object or None.
+        """
+        saved_pos = self.pos
+        # Try dim ASTERISK datashape
+        dim = self.parse_dim()
+        if dim is not None:
+            if self.tok.id == lexer.ASTERISK:
+                # If an asterisk is next, we're good
+                self.advance_tok()
+                saved_pos = self.pos
+                dshape = self.parse_datashape()
+                if dshape is None:
+                    self.pos = saved_pos
+                    self.raise_error('Expected a dim or a dtype')
+                return coretypes.DataShape(dim, *dshape.parameters)
+        # Try dtype
+        dtype = self.parse_dtype()
+        if dtype:
+            return coretypes.DataShape(dtype)
+        else:
+            return None
+
+    def parse_dim(self):
+        """
+        dim : typevar
+            | ellipsis_typevar
+            | type
+            | type_constr
+            | INTEGER
+            | ELLIPSIS
+        typevar : NAME_UPPER
+        ellipsis_typevar : NAME_UPPER ELLIPSIS
+        type : NAME_LOWER
+        type_constr : NAME_LOWER LBRACKET type_arg_list RBRACKET
+
+        Returns a the dim object, or None.
+        TODO: Support type constructors
+        """
+        saved_pos = self.pos
+        tok = self.tok
+        if tok.id == lexer.NAME_UPPER:
+            val = tok.val
+            self.advance_tok()
+            if self.tok.id == lexer.ELLIPSIS:
+                self.advance_tok()
+                # TypeVars ellipses are treated as the "ellipsis" dim
+                tconstr = self.syntactic_sugar(self.sym.dim_constr, 'ellipsis',
+                                               'TypeVar... dim constructor',
+                                               saved_pos)
+                return tconstr(val)
+            elif self.tok.id == lexer.ASTERISK:
+                # Using a lookahead check for '*' after the TypeVar, so that
+                # the error message would be about a dtype problem instead
+                # of a dim problem when 'typevar' isn't in the symbol table
+                #
+                # TypeVars are treated as the "typevar" dim
+                tconstr = self.syntactic_sugar(self.sym.dim_constr, 'typevar',
+                                               'TypeVar dim constructor',
+                                               saved_pos)
+                return tconstr(val)
+            else:
+                self.pos = saved_pos
+                return None
+        elif tok.id == lexer.NAME_LOWER:
+            name = tok.val
+            self.advance_tok()
+            if self.tok.id == lexer.LBRACKET:
+                dim_constr = self.sym.dim_constr.get(name)
+                if dim_constr is None:
+                    self.pos = saved_pos
+                    return None
+                self.advance_tok()
+                args = self.parse_type_arg_list()   # noqa: F841
+                if self.tok.id == lexer.RBRACKET:
+                    self.advance_tok()
+                    raise NotImplementedError(
+                        'dim type constructors not actually supported yet')
+                else:
+                    self.raise_error('Expected a closing "]"')
+            else:
+                dim = self.sym.dim.get(name)
+                if dim is not None:
+                    return dim
+                else:
+                    self.pos = saved_pos
+                    return None
+        elif tok.id == lexer.INTEGER:
+            val = tok.val
+            self.advance_tok()
+            # If the token after the INTEGER is not ASTERISK,
+            # it cannot be a dim, so skip it
+            if self.tok.id != lexer.ASTERISK:
+                self.pos = saved_pos
+                return None
+            # Integers are treated as "fixed" dimensions
+            tconstr = self.syntactic_sugar(self.sym.dim_constr, 'fixed',
+                                           'integer dimensions')
+            return tconstr(val)
+        elif tok.id == lexer.ELLIPSIS:
+            self.advance_tok()
+            # Ellipses are treated as the "ellipsis" dim
+            dim = self.syntactic_sugar(self.sym.dim, 'ellipsis',
+                                           '... dim',
+                                           saved_pos)
+            return dim
+        else:
+            return None
+
+    def parse_dtype(self):
+        """
+        dtype : typevar
+              | type
+              | type_constr
+              | struct_type
+              | funcproto_or_tuple_type
+        typevar : NAME_UPPER
+        ellipsis_typevar : NAME_UPPER ELLIPSIS
+        type : NAME_LOWER
+        type_constr : NAME_LOWER LBRACKET type_arg_list RBRACKET
+        struct_type : LBRACE ...
+        funcproto_or_tuple_type : LPAREN ...
+
+        Returns a the dtype object, or None.
+        """
+        saved_pos = self.pos
+        tok = self.tok
+        if tok.id == lexer.NAME_UPPER:
+            val = tok.val
+            self.advance_tok()
+            # TypeVars are treated as the "typevar" dtype
+            tconstr = self.syntactic_sugar(self.sym.dtype_constr, 'typevar',
+                                           'TypeVar dtype constructor',
+                                           saved_pos)
+            return tconstr(val)
+        elif tok.id == lexer.NAME_LOWER:
+            name = tok.val
+            self.advance_tok()
+            if self.tok.id == lexer.LBRACKET:
+                dtype_constr = self.sym.dtype_constr.get(name)
+                if dtype_constr is None:
+                    self.pos = saved_pos
+                    return None
+                self.advance_tok()
+                args, kwargs = self.parse_type_arg_list()
+                if self.tok.id == lexer.RBRACKET:
+                    if len(args) == 0 and len(kwargs) == 0:
+                        self.raise_error('Expected at least one type ' +
+                                         'constructor argument')
+                    self.advance_tok()
+                    return dtype_constr(*args, **kwargs)
+                else:
+                    self.raise_error('Invalid type constructor argument')
+            else:
+                dtype = self.sym.dtype.get(name)
+                if dtype is not None:
+                    return dtype
+                else:
+                    self.pos = saved_pos
+                    return None
+        elif tok.id == lexer.LBRACE:
+            return self.parse_struct_type()
+        elif tok.id == lexer.LPAREN:
+            return self.parse_funcproto_or_tuple_type()
+        else:
+            return None
+
+    def parse_type_arg_list(self):
+        """
+        type_arg_list : type_arg COMMA type_arg_list
+                      | type_kwarg_list
+                      | type_arg
+        type_kwarg_list : type_kwarg COMMA type_kwarg_list
+                        | type_kwarg
+
+        Returns a tuple (args, kwargs), or (None, None).
+        """
+        # Parse zero or more "type_arg COMMA" repetitions
+        args = []
+        arg = True
+        while arg is not None:
+            # Parse the type_arg
+            arg = self.parse_type_arg()
+            if arg is not None:
+                if self.tok.id == lexer.COMMA:
+                    # If a comma is next, there are more args
+                    self.advance_tok()
+                    args.append(arg)
+                else:
+                    # Otherwise we've reached the end, and there
+                    # were no keyword args
+                    args.append(arg)
+                    return (args, {})
+            else:
+                break
+        kwargs = self.parse_homogeneous_list(self.parse_type_kwarg, lexer.COMMA,
+                                           'Expected another keyword argument, ' +
+                                           'positional arguments cannot follow ' +
+                                           'keyword arguments')
+        return (args, dict(kwargs) if kwargs else {})
+
+    def parse_type_arg(self):
+        """
+        type_arg : datashape
+                 | INTEGER
+                 | STRING
+                 | BOOLEAN
+                 | list_type_arg
+        list_type_arg : LBRACKET RBRACKET
+                      | LBRACKET datashape_list RBRACKET
+                      | LBRACKET integer_list RBRACKET
+                      | LBRACKET string_list RBRACKET
+
+        Returns a type_arg value, or None.
+        """
+        ds = self.parse_datashape()
+        if ds is not None:
+            return ds
+        if self.tok.id in [lexer.INTEGER, lexer.STRING, lexer.BOOLEAN]:
+            val = self.tok.val
+            self.advance_tok()
+            return val
+        elif self.tok.id == lexer.LBRACKET:
+            self.advance_tok()
+            val = self.parse_datashape_list()
+            if val is None:
+                val = self.parse_integer_list()
+            if val is None:
+                val = self.parse_string_list()
+            if val is None:
+                val = self.parse_boolean_list()
+            if self.tok.id == lexer.RBRACKET:
+                self.advance_tok()
+                return [] if val is None else val
+            else:
+                if val is None:
+                    self.raise_error('Expected a type constructor argument ' +
+                                     'or a closing "]"')
+                else:
+                    self.raise_error('Expected a "," or a closing "]"')
+        else:
+            return None
+
+    def parse_type_kwarg(self):
+        """
+        type_kwarg : NAME_LOWER EQUAL type_arg
+
+        Returns a (name, type_arg) tuple, or None.
+        """
+        if self.tok.id != lexer.NAME_LOWER:
+            return None
+        saved_pos = self.pos
+        name = self.tok.val
+        self.advance_tok()
+        if self.tok.id != lexer.EQUAL:
+            self.pos = saved_pos
+            return None
+        self.advance_tok()
+        arg = self.parse_type_arg()
+        if arg is not None:
+            return (name, arg)
+        else:
+            # After "NAME_LOWER EQUAL", a type_arg is required.
+            self.raise_error('Expected a type constructor argument')
+
+    def parse_datashape_list(self):
+        """
+        datashape_list : datashape COMMA datashape_list
+                       | datashape
+
+        Returns a list of datashape type objects, or None.
+        """
+        return self.parse_homogeneous_list(self.parse_datashape, lexer.COMMA,
+                                           'Expected another datashape, ' +
+                                           'type constructor parameter ' +
+                                           'lists must have uniform type')
+
+    def parse_integer(self):
+        """
+        integer : INTEGER
+        """
+        if self.tok.id == lexer.INTEGER:
+            val = self.tok.val
+            self.advance_tok()
+            return val
+        else:
+            return None
+
+    def parse_integer_list(self):
+        """
+        integer_list : INTEGER COMMA integer_list
+                     | INTEGER
+
+        Returns a list of integers, or None.
+        """
+        return self.parse_homogeneous_list(self.parse_integer, lexer.COMMA,
+                                           'Expected another integer, ' +
+                                           'type constructor parameter ' +
+                                           'lists must have uniform type')
+
+    def parse_boolean(self):
+        """
+        boolean : BOOLEAN
+        """
+        if self.tok.id == lexer.BOOLEAN:
+            val = self.tok.val
+            self.advance_tok()
+            return val
+        else:
+            return None
+
+    def parse_boolean_list(self):
+        """
+        boolean_list : boolean COMMA boolean_list
+                     | boolean
+
+        Returns a list of booleans, or None.
+        """
+        return self.parse_homogeneous_list(self.parse_boolean, lexer.COMMA,
+                                           'Expected another boolean, ' +
+                                           'type constructor parameter ' +
+                                           'lists must have uniform type')
+
+    def parse_string(self):
+        """
+        string : STRING
+        """
+        if self.tok.id == lexer.STRING:
+            val = self.tok.val
+            self.advance_tok()
+            return val
+        else:
+            return None
+
+    def parse_string_list(self):
+        """
+        string_list : STRING COMMA string_list
+                    | STRING
+
+        Returns a list of strings, or None.
+        """
+        return self.parse_homogeneous_list(self.parse_string, lexer.COMMA,
+                                           'Expected another string, ' +
+                                           'type constructor parameter ' +
+                                           'lists must have uniform type')
+
+    def parse_struct_type(self):
+        """
+        struct_type : LBRACE struct_field_list RBRACE
+                    | LBRACE struct_field_list COMMA RBRACE
+
+        Returns a struct type, or None.
+        """
+        if self.tok.id != lexer.LBRACE:
+            return None
+        saved_pos = self.pos
+        self.advance_tok()
+        fields = self.parse_homogeneous_list(self.parse_struct_field, lexer.COMMA,
+                                             'Invalid field in struct',
+                                             trailing_sep=True) or []
+        if self.tok.id != lexer.RBRACE:
+            self.raise_error('Invalid field in struct')
+        self.advance_tok()
+        # Split apart the names and types into separate lists,
+        # compatible with type constructor parameters
+        names = [f[0] for f in fields]
+        types = [f[1] for f in fields]
+        # Structs are treated as the "struct" dtype
+        tconstr = self.syntactic_sugar(self.sym.dtype_constr, 'struct',
+                                       '{...} dtype constructor', saved_pos)
+        return tconstr(names, types)
+
+    def parse_struct_field(self):
+        """
+        struct_field : struct_field_name COLON datashape
+        struct_field_name : NAME_LOWER
+                          | NAME_UPPER
+                          | NAME_OTHER
+                          | STRING
+
+        Returns a tuple (name, datashape object) or None
+        """
+        if self.tok.id not in [lexer.NAME_LOWER, lexer.NAME_UPPER,
+                               lexer.NAME_OTHER, lexer.STRING]:
+            return None
+        name = self.tok.val
+        self.advance_tok()
+        if self.tok.id != lexer.COLON:
+            self.raise_error('Expected a ":" separating the field ' +
+                             'name from its datashape')
+        self.advance_tok()
+        ds = self.parse_datashape()
+        if ds is None:
+            self.raise_error('Expected the datashape of the field')
+        return (name, ds)
+
+    def parse_funcproto_or_tuple_type(self):
+        """
+        funcproto_or_tuple_type : tuple_type RARROW datashape
+                                | tuple_type
+        tuple_type : LPAREN tuple_item_list RPAREN
+                   | LPAREN tuple_item_list COMMA RPAREN
+                   | LPAREN RPAREN
+        tuple_item_list : datashape COMMA tuple_item_list
+                        | datashape
+
+        Returns a tuple type object, a function prototype, or None.
+        """
+        if self.tok.id != lexer.LPAREN:
+            return None
+        saved_pos = self.pos
+        self.advance_tok()
+        dshapes = self.parse_homogeneous_list(
+            self.parse_datashape,
+            lexer.COMMA,
+            'Invalid datashape in tuple',
+            trailing_sep=True,
+        ) or ()
+        if self.tok.id != lexer.RPAREN:
+            self.raise_error('Invalid datashape in tuple')
+        self.advance_tok()
+        if self.tok.id != lexer.RARROW:
+            # Tuples are treated as the "tuple" dtype
+            tconstr = self.syntactic_sugar(self.sym.dtype_constr, 'tuple',
+                                           '(...) dtype constructor', saved_pos)
+            return tconstr(dshapes)
+        else:
+            # Get the return datashape after the right arrow
+            self.advance_tok()
+            ret_dshape = self.parse_datashape()
+            if ret_dshape is None:
+                self.raise_error('Expected function prototype return ' +
+                                 'datashape')
+            # Function Prototypes are treated as the "funcproto" dtype
+            tconstr = self.syntactic_sugar(self.sym.dtype_constr, 'funcproto',
+                                           '(...) -> ... dtype constructor',
+                                           saved_pos)
+            return tconstr(dshapes, ret_dshape)
+
+
+def parse(ds_str, sym):
+    """Parses a single datashape from a string.
+
+    Parameters
+    ----------
+    ds_str : string
+        The datashape string to parse.
+    sym : TypeSymbolTable
+        The symbol tables of dimensions, dtypes, and type constructors for each.
+
+    """
+    dsp = DataShapeParser(ds_str, sym)
+    ds = dsp.parse_datashape()
+    # If no datashape could be found
+    if ds is None:
+        dsp.raise_error('Invalid datashape')
+
+    # Make sure there's no garbage at the end
+    if dsp.pos != dsp.end_pos:
+        dsp.raise_error('Unexpected token in datashape')
+    return ds
diff --git a/datashader/datashape/predicates.py b/datashader/datashape/predicates.py
new file mode 100644
index 000000000..bacc45d7e
--- /dev/null
+++ b/datashader/datashape/predicates.py
@@ -0,0 +1,209 @@
+import numpy as np
+
+from .util import collect, dshape
+from .internal_utils import remove
+from .coretypes import (DataShape, Fixed, Var, Ellipsis, Record, Unit,
+                        date_, datetime_, TypeVar, to_numpy_dtype,
+                        Categorical)
+from .typesets import floating, boolean
+
+# https://github.com/blaze/datashape/blob/master/docs/source/types.rst
+
+__all__ = ['isdimension', 'ishomogeneous', 'istabular', 'isfixed', 'isscalar',
+           'isrecord', 'iscollection', 'isnumeric', 'isboolean', 'isdatelike',
+           'isreal']
+
+dimension_types = Fixed, Var, Ellipsis, int
+
+
+def isscalar(ds):
+    """ Is this dshape a single dtype?
+
+    >>> isscalar('int')
+    True
+    >>> isscalar('?int')
+    True
+    >>> isscalar('{name: string, amount: int}')
+    False
+    """
+    if isinstance(ds, str):
+        ds = dshape(ds)
+    if isinstance(ds, DataShape) and len(ds) == 1:
+        ds = ds[0]
+    return isinstance(getattr(ds, 'ty', ds), (Unit, Categorical))
+
+
+def isrecord(ds):
+    """ Is this dshape a record type?
+
+    >>> isrecord('{name: string, amount: int}')
+    True
+    >>> isrecord('int')
+    False
+    >>> isrecord('?{name: string, amount: int}')
+    True
+    """
+    if isinstance(ds, str):
+        ds = dshape(ds)
+    if isinstance(ds, DataShape) and len(ds) == 1:
+        ds = ds[0]
+    return isinstance(getattr(ds, 'ty', ds), Record)
+
+
+def isdimension(ds):
+    """ Is a component a dimension?
+
+    >>> from datashader.datashape import int32
+    >>> isdimension(Fixed(10))
+    True
+    >>> isdimension(Var())
+    True
+    >>> isdimension(int32)
+    False
+    """
+    return isinstance(ds, dimension_types)
+
+
+def ishomogeneous(ds):
+    """ Does datashape contain only one dtype?
+
+    >>> from datashader.datashape import int32
+    >>> ishomogeneous(int32)
+    True
+    >>> ishomogeneous('var * 3 * string')
+    True
+    >>> ishomogeneous('var * {name: string, amount: int}')
+    False
+    """
+    ds = dshape(ds)
+    return len(set(remove(isdimension, collect(isscalar, ds)))) == 1
+
+
+def _dimensions(ds):
+    """Number of dimensions of datashape
+    """
+    return len(dshape(ds).shape)
+
+
+def isfixed(ds):
+    """ Contains no variable dimensions
+
+    >>> isfixed('10 * int')
+    True
+    >>> isfixed('var * int')
+    False
+    >>> isfixed('10 * {name: string, amount: int}')
+    True
+    >>> isfixed('10 * {name: string, amounts: var * int}')
+    False
+    """
+    ds = dshape(ds)
+    if isinstance(ds[0], TypeVar):
+        return None  # don't know
+    if isinstance(ds[0], Var):
+        return False
+    if isinstance(ds[0], Record):
+        return all(map(isfixed, ds[0].types))
+    if len(ds) > 1:
+        return isfixed(ds.subarray(1))
+    return True
+
+
+def istabular(ds):
+    """ A collection of records
+
+    >>> istabular('var * {name: string, amount: int}')
+    True
+    >>> istabular('var * 10 * 3 * int')
+    False
+    >>> istabular('10 * var * int')
+    False
+    >>> istabular('var * (int64, string, ?float64)')
+    False
+    """
+    ds = dshape(ds)
+    return _dimensions(ds) == 1 and isrecord(ds.measure)
+
+
+def iscollection(ds):
+    """ Is a collection of items, has dimension
+
+    >>> iscollection('5 * int32')
+    True
+    >>> iscollection('int32')
+    False
+    """
+    if isinstance(ds, str):
+        ds = dshape(ds)
+    return isdimension(ds[0])
+
+
+def isnumeric(ds):
+    """ Has a numeric measure
+
+    >>> isnumeric('int32')
+    True
+    >>> isnumeric('3 * ?real')
+    True
+    >>> isnumeric('string')
+    False
+    >>> isnumeric('var * {amount: ?int32}')
+    False
+    """
+    ds = launder(ds)
+
+    try:
+        npdtype = to_numpy_dtype(ds)
+    except TypeError:
+        return False
+    else:
+        return isinstance(ds, Unit) and np.issubdtype(npdtype, np.number)
+
+
+def launder(ds):
+    if isinstance(ds, str):
+        ds = dshape(ds)
+    if isinstance(ds, DataShape):
+        ds = ds.measure
+    return getattr(ds, 'ty', ds)
+
+
+def isreal(ds):
+    """ Has a numeric measure
+
+    >>> isreal('float32')
+    True
+    >>> isreal('3 * ?real')
+    True
+    >>> isreal('string')
+    False
+    """
+    ds = launder(ds)
+    return isinstance(ds, Unit) and ds in floating
+
+
+def isboolean(ds):
+    """ Has a boolean measure
+
+    >>> isboolean('bool')
+    True
+    >>> isboolean('3 * ?bool')
+    True
+    >>> isboolean('int')
+    False
+    """
+    return launder(ds) in boolean
+
+
+def isdatelike(ds):
+    """ Has a date or datetime measure
+
+    >>> isdatelike('int32')
+    False
+    >>> isdatelike('3 * datetime')
+    True
+    >>> isdatelike('?datetime')
+    True
+    """
+    ds = launder(ds)
+    return ds == date_ or ds == datetime_
diff --git a/datashader/datashape/promote.py b/datashader/datashape/promote.py
new file mode 100644
index 000000000..2403a4482
--- /dev/null
+++ b/datashader/datashape/promote.py
@@ -0,0 +1,78 @@
+from __future__ import absolute_import
+
+import numpy as np
+from datashader import datashape
+
+
+__all__ = ['promote', 'optionify']
+
+
+def promote(lhs, rhs, promote_option=True):
+    """Promote two scalar dshapes to a possibly larger, but compatible type.
+
+    Examples
+    --------
+    >>> from datashader.datashape import int32, int64, Option, string
+    >>> x = Option(int32)
+    >>> y = int64
+    >>> promote(x, y)
+    Option(ty=ctype("int64"))
+    >>> promote(int64, int64)
+    ctype("int64")
+
+    Don't promote to option types.
+    >>> promote(x, y, promote_option=False)
+    ctype("int64")
+
+    Strings are handled differently than NumPy, which promotes to ctype("object")
+    >>> x = string
+    >>> y = Option(string)
+    >>> promote(x, y) == promote(y, x) == Option(string)
+    True
+    >>> promote(x, y, promote_option=False)
+    ctype("string")
+
+    Notes
+    ----
+    Except for ``datashader.datashape.string`` types, this uses ``numpy.result_type`` for
+    type promotion logic.  See the numpy documentation at:
+
+    http://docs.scipy.org/doc/numpy/reference/generated/numpy.result_type.html
+    """
+    if lhs == rhs:
+        return lhs
+    left, right = getattr(lhs, 'ty', lhs), getattr(rhs, 'ty', rhs)
+    if left == right == datashape.string:
+        # Special case string promotion, since numpy promotes to `object`.
+        dtype = datashape.string
+    else:
+        np_res_type = np.result_type(datashape.to_numpy_dtype(left),
+                                     datashape.to_numpy_dtype(right))
+        dtype = datashape.CType.from_numpy_dtype(np_res_type)
+    if promote_option:
+        dtype = optionify(lhs, rhs, dtype)
+    return dtype
+
+
+def optionify(lhs, rhs, dshape):
+    """Check whether a binary operation's dshape came from
+    :class:`~datashape.coretypes.Option` typed operands and construct an
+    :class:`~datashape.coretypes.Option` type accordingly.
+
+    Examples
+    --------
+    >>> from datashader.datashape import int32, int64, Option
+    >>> x = Option(int32)
+    >>> x
+    Option(ty=ctype("int32"))
+    >>> y = int64
+    >>> y
+    ctype("int64")
+    >>> optionify(x, y, int64)
+    Option(ty=ctype("int64"))
+    """
+    if hasattr(dshape.measure, 'ty'):
+        return dshape
+    if hasattr(lhs, 'ty') or hasattr(rhs, 'ty'):
+        return datashape.Option(dshape)
+    return dshape
diff --git a/datashader/datashape/py2help.py b/datashader/datashape/py2help.py
new file mode 100644
index 000000000..4eaabe199
--- /dev/null
+++ b/datashader/datashape/py2help.py
@@ -0,0 +1,24 @@
+# Portions of this taken from the six library, licensed as follows.
+#
+# Copyright (c) 2010-2013 Benjamin Peterson
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in all
+# copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+_inttypes = (int,)
+_strtypes = (str,)
diff --git a/datashader/datashape/type_symbol_table.py b/datashader/datashape/type_symbol_table.py
new file mode 100644
index 000000000..103210036
--- /dev/null
+++ b/datashader/datashape/type_symbol_table.py
@@ -0,0 +1,155 @@
+"""
+A symbol table object to hold types for the parser.
+"""
+
+from __future__ import absolute_import, division, print_function
+import ctypes
+from itertools import chain
+
+from . import coretypes as ct
+
+__all__ = ['TypeSymbolTable', 'sym']
+
+
+_is_64bit = (ctypes.sizeof(ctypes.c_void_p) == 8)
+
+
+def _complex(tp):
+    """Simple temporary type constructor for complex"""
+    if tp == ct.DataShape(ct.float32):
+        return ct.complex_float32
+    elif tp == ct.DataShape(ct.float64):
+        return ct.complex_float64
+    else:
+        raise TypeError(
+            'Cannot contruct a complex type with real component %s' % tp)
+
+
+def _struct(names, dshapes):
+    """Simple temporary type constructor for struct"""
+    return ct.Record(list(zip(names, dshapes)))
+
+
+def _funcproto(args, ret):
+    """Simple temporary type constructor for funcproto"""
+    return ct.Function(*chain(args, (ret,)))
+
+
+def _typevar_dim(name):
+    """Simple temporary type constructor for typevar as a dim"""
+    # Note: Presently no difference between dim and dtype typevar
+    return ct.TypeVar(name)
+
+
+def _typevar_dtype(name):
+    """Simple temporary type constructor for typevar as a dtype"""
+    # Note: Presently no difference between dim and dtype typevar
+    return ct.TypeVar(name)
+
+
+def _ellipsis(name):
+    return ct.Ellipsis(ct.TypeVar(name))
+
+# data types with no type constructor
+no_constructor_types = [
+    ('bool', ct.bool_),
+    ('int8', ct.int8),
+    ('int16', ct.int16),
+    ('int32', ct.int32),
+    ('int64', ct.int64),
+    ('intptr', ct.int64 if _is_64bit else ct.int32),
+    ('int', ct.int32),
+    ('uint8', ct.uint8),
+    ('uint16', ct.uint16),
+    ('uint32', ct.uint32),
+    ('uint64', ct.uint64),
+    ('uintptr', ct.uint64 if _is_64bit else ct.uint32),
+    ('float16', ct.float16),
+    ('float32', ct.float32),
+    ('float64', ct.float64),
+    ('complex64', ct.complex64),
+    ('complex128', ct.complex128),
+    ('real', ct.float64),
+    ('complex', ct.complex_float64),
+    ('string', ct.string),
+    ('json', ct.json),
+    ('date', ct.date_),
+    ('time', ct.time_),
+    ('datetime', ct.datetime_),
+    ('timedelta', ct.timedelta_),
+    ('null', ct.null),
+    ('void', ct.void),
+    ('object', ct.object_),
+]
+
+# data types with a type constructor
+constructor_types = [
+    ('complex', _complex),
+    ('string', ct.String),
+    ('struct', _struct),
+    ('tuple', ct.Tuple),
+    ('funcproto', _funcproto),
+    ('typevar', _typevar_dtype),
+    ('option', ct.Option),
+    ('map', ct.Map),
+    ('time', ct.Time),
+    ('datetime', ct.DateTime),
+    ('timedelta', ct.TimeDelta),
+    ('units', ct.Units),
+    ('decimal', ct.Decimal),
+    ('categorical', ct.Categorical),
+]
+
+# dim types with no type constructor
+dim_no_constructor = [
+    ('var', ct.Var()),
+    ('ellipsis', ct.Ellipsis()),
+]
+
+# dim types with a type constructor
+dim_constructor = [
+    ('fixed', ct.Fixed),
+    ('typevar', _typevar_dim),
+    ('ellipsis', _ellipsis),
+]
+
+
+class TypeSymbolTable(object):
+
+    """
+    This is a class which holds symbols for types and type constructors,
+    and is used by the datashape parser to build types during its parsing.
+    A TypeSymbolTable sym has four tables, as follows:
+
+    sym.dtype
+        Data type symbols with no type constructor.
+    sym.dtype_constr
+        Data type symbols with a type constructor. This may contain
+        symbols also in sym.dtype, e.g. for 'complex' and 'complex[float64]'.
+    sym.dim
+        Dimension symbols with no type constructor.
+    sym.dim_constr
+        Dimension symbols with a type constructor.
+    """
+    __slots__ = ['dtype', 'dtype_constr', 'dim', 'dim_constr']
+
+    def __init__(self, bare=False):
+        # Initialize all the symbol tables to empty dicts1
+        self.dtype = {}
+        self.dtype_constr = {}
+        self.dim = {}
+        self.dim_constr = {}
+        if not bare:
+            self.add_default_types()
+
+    def add_default_types(self):
+        """
+        Adds all the default datashape types to the symbol table.
+        """
+        self.dtype.update(no_constructor_types)
+        self.dtype_constr.update(constructor_types)
+        self.dim.update(dim_no_constructor)
+        self.dim_constr.update(dim_constructor)
+
+# Create the default global type symbol table
+sym = TypeSymbolTable()
diff --git a/datashader/datashape/typesets.py b/datashader/datashape/typesets.py
new file mode 100644
index 000000000..bfcec9748
--- /dev/null
+++ b/datashader/datashape/typesets.py
@@ -0,0 +1,209 @@
+"""
+Traits constituting sets of types.
+"""
+
+from itertools import chain
+
+from .coretypes import (Unit, int8, int16, int32, int64, uint8, uint16, uint32,
+                        uint64, float16, float32, float64, complex64,
+                        complex128, bool_, Decimal, TimeDelta, Option)
+
+
+__all__ = ['TypeSet', 'matches_typeset', 'signed', 'unsigned', 'integral',
+           'floating', 'complexes', 'boolean', 'numeric', 'scalar',
+           'maxtype']
+
+
+class TypeSet(Unit):
+    """
+    Create a new set of types. Keyword argument 'name' may create a registered
+    typeset for use in datashape type strings.
+    """
+    __slots__ = '_order', 'name'
+
+    def __init__(self, *args, **kwds):
+        self._order = args
+        self.name = kwds.get('name')
+        if self.name:
+            register_typeset(self.name, self)
+
+    @property
+    def _set(self):
+        return set(self._order)
+
+    @property
+    def types(self):
+        return self._order
+
+    def __eq__(self, other):
+        return (isinstance(other, type(self)) and
+                self.name == other.name and self.types == other.types)
+
+    def __hash__(self):
+        return hash((self.name, self.types))
+
+    def __contains__(self, val):
+        return val in self._set
+
+    def __repr__(self):
+        if self.name:
+            return '{%s}' % (self.name,)
+        return "%s(%s, name=%s)" % (self.__class__.__name__, self._set,
+                                    self.name)
+
+    def __or__(self, other):
+        return TypeSet(*chain(self, other))
+
+    def __iter__(self):
+        return iter(self._order)
+
+    def __len__(self):
+        return len(self._set)
+
+
+def matches_typeset(types, signature):
+    """Match argument types to the parameter types of a signature
+
+    >>> matches_typeset(int32, integral)
+    True
+    >>> matches_typeset(float32, integral)
+    False
+    >>> matches_typeset(integral, real)
+    True
+    """
+    if types in signature:
+        return True
+    match = True
+    for a, b in zip(types, signature):
+        check = isinstance(b, TypeSet)
+        if check and (a not in b) or (not check and a != b):
+            match = False
+            break
+    return match
+
+
+class TypesetRegistry(object):
+    def __init__(self):
+        self.registry = {}
+        self.lookup = self.registry.get
+
+    def register_typeset(self, name, typeset):
+        if name in self.registry:
+            raise TypeError("TypeSet %s already defined with types %s" %
+                            (name, self.registry[name].types))
+        self.registry[name] = typeset
+        return typeset
+
+    def __getitem__(self, key):
+        value = self.lookup(key)
+        if value is None:
+            raise KeyError(key)
+        return value
+
+registry = TypesetRegistry()
+register_typeset = registry.register_typeset
+lookup = registry.lookup
+
+#------------------------------------------------------------------------
+# Default Type Sets
+#------------------------------------------------------------------------
+
+signed = TypeSet(int8, int16, int32, int64, name='signed')
+unsigned = TypeSet(uint8, uint16, uint32, uint64, name='unsigned')
+integral = TypeSet(*[x for t in zip(signed, unsigned) for x in t],
+                   name='integral')
+floating = TypeSet(float32, float64, name='floating')
+complexes = TypeSet(complex64, complex128, name='complexes')
+boolean = TypeSet(bool_, name='boolean')
+
+real = TypeSet(*integral | floating, name='real')
+numeric = TypeSet(*integral | floating | complexes, name='numeric')
+scalar = TypeSet(*boolean | numeric, name='scalar')
+
+
+supertype_map = {
+    int8: signed,
+    int16: signed,
+    int32: signed,
+    int64: signed,
+    uint8: unsigned,
+    uint16: unsigned,
+    uint32: unsigned,
+    uint64: unsigned,
+    float16: floating,
+    float32: floating,
+    float64: floating,
+    complex64: complexes,
+    complex128: complexes,
+    bool_: boolean
+}
+
+
+def supertype(measure):
+    """Get the super type of a concrete numeric type
+
+    Examples
+    --------
+    >>> supertype(int8)
+    {signed}
+
+    >>> supertype(float32)
+    {floating}
+
+    >>> supertype(complex128)
+    {complexes}
+
+    >>> supertype(bool_)
+    {boolean}
+
+    >>> supertype(Option(bool_))
+    {boolean}
+    """
+    if isinstance(measure, Option):
+        measure = measure.ty
+    assert matches_typeset(measure, scalar), 'measure must be numeric'
+    return supertype_map[measure]
+
+
+def maxtype(measure):
+    """Get the maximum width for a particular numeric type
+
+    Examples
+    --------
+    >>> maxtype(int8)
+    ctype("int64")
+
+    >>> maxtype(Option(float64))
+    Option(ty=ctype("float64"))
+
+    >>> maxtype(bool_)
+    ctype("bool")
+
+    >>> maxtype(Decimal(11, 2))
+    Decimal(precision=11, scale=2)
+
+    >>> maxtype(Option(Decimal(11, 2)))
+    Option(ty=Decimal(precision=11, scale=2))
+
+    >>> maxtype(TimeDelta(unit='ms'))
+    TimeDelta(unit='ms')
+
+    >>> maxtype(Option(TimeDelta(unit='ms')))
+    Option(ty=TimeDelta(unit='ms'))
+    """
+    measure = measure.measure
+    isoption = isinstance(measure, Option)
+    if isoption:
+        measure = measure.ty
+    if (not matches_typeset(measure, scalar) and
+        not isinstance(measure, (Decimal, TimeDelta))):
+
+        raise TypeError('measure must be numeric')
+
+    if measure == bool_:
+        result = bool_
+    elif isinstance(measure, (Decimal, TimeDelta)):
+        result = measure
+    else:
+        result = max(supertype(measure).types, key=lambda x: x.itemsize)
+    return Option(result) if isoption else result
diff --git a/datashader/datashape/user.py b/datashader/datashape/user.py
new file mode 100644
index 000000000..0aa9b4764
--- /dev/null
+++ b/datashader/datashape/user.py
@@ -0,0 +1,98 @@
+from __future__ import print_function, division, absolute_import
+from .dispatch import dispatch
+from .coretypes import (
+    CType, Date, DateTime, DataShape, Record, String, Time, Var, from_numpy, to_numpy_dtype)
+from .predicates import isdimension
+from .util import dshape
+from datetime import date, time, datetime
+import numpy as np
+
+
+__all__ = ['validate', 'issubschema']
+
+
+basetypes = np.generic, int, float, str, date, time, datetime
+
+
+@dispatch(np.dtype, basetypes)
+def validate(schema, value):
+    return np.issubdtype(type(value), schema)
+
+
+@dispatch(CType, basetypes)
+def validate(schema, value):  # noqa: F811
+    return validate(to_numpy_dtype(schema), value)
+
+
+@dispatch(DataShape, (tuple, list))
+def validate(schema, value):  # noqa: F811
+    head = schema[0]
+    return ((len(schema) == 1 and validate(head, value))
+        or (isdimension(head)
+       and (isinstance(head, Var) or int(head) == len(value))
+       and all(validate(DataShape(*schema[1:]), item) for item in value)))
+
+
+@dispatch(DataShape, object)
+def validate(schema, value):  # noqa: F811
+    if len(schema) == 1:
+        return validate(schema[0], value)
+
+
+@dispatch(Record, dict)
+def validate(schema, d):  # noqa: F811
+    return all(validate(sch, d.get(k)) for k, sch in schema.parameters[0])
+
+
+@dispatch(Record, (tuple, list))
+def validate(schema, seq):  # noqa: F811
+    return all(validate(sch, item) for (k, sch), item
+                                    in zip(schema.parameters[0], seq))
+
+
+@dispatch(str, object)
+def validate(schema, value):  # noqa: F811
+    return validate(dshape(schema), value)
+
+
+@dispatch(type, object)
+def validate(schema, value):  # noqa: F811
+    return isinstance(value, schema)
+
+
+@dispatch(tuple, object)
+def validate(schemas, value):  # noqa: F811
+    return any(validate(schema, value) for schema in schemas)
+
+
+@dispatch(object, object)
+def validate(schema, value):  # noqa: F811
+    return False
+
+
+@validate.register(String, str)
+@validate.register(Time, time)
+@validate.register(Date, date)
+@validate.register(DateTime, datetime)
+def validate_always_true(schema, value):
+    return True
+
+
+@dispatch(DataShape, np.ndarray)
+def validate(schema, value):
+    return issubschema(from_numpy(value.shape, value.dtype), schema)
+
+
+@dispatch(object, object)
+def issubschema(a, b):
+    return issubschema(dshape(a), dshape(b))
+
+
+@dispatch(DataShape, DataShape)
+def issubschema(a, b):  # noqa: F811
+    if a == b:
+        return True
+    # TODO, handle cases like float < real
+    # TODO, handle records {x: int, y: int, z: int} < {x: int, y: int}
+
+    return None  # We don't know, return something falsey
diff --git a/datashader/datashape/util/__init__.py b/datashader/datashape/util/__init__.py
new file mode 100644
index 000000000..5aa4d0783
--- /dev/null
+++ b/datashader/datashape/util/__init__.py
@@ -0,0 +1,145 @@
+from __future__ import print_function, division, absolute_import
+
+from itertools import chain
+import operator
+
+from .. import py2help
+from .. import parser
+from .. import type_symbol_table
+from ..validation import validate
+from .. import coretypes
+
+
+__all__ = 'dshape', 'dshapes', 'has_var_dim', 'has_ellipsis', 'cat_dshapes'
+
+subclasses = operator.methodcaller('__subclasses__')
+
+#------------------------------------------------------------------------
+# Utility Functions for DataShapes
+#------------------------------------------------------------------------
+
+def dshapes(*args):
+    """
+    Parse a bunch of datashapes all at once.
+
+    >>> a, b = dshapes('3 * int32', '2 * var * float64')
+    """
+    return [dshape(arg) for arg in args]
+
+
+def dshape(o):
+    """
+    Parse a datashape. For a thorough description see
+    http://blaze.pydata.org/docs/datashape.html
+
+    >>> ds = dshape('2 * int32')
+    >>> ds[1]
+    ctype("int32")
+    """
+    if isinstance(o, coretypes.DataShape):
+        return o
+    if isinstance(o, py2help._strtypes):
+        ds = parser.parse(o, type_symbol_table.sym)
+    elif isinstance(o, (coretypes.CType, coretypes.String,
+                        coretypes.Record, coretypes.JSON,
+                        coretypes.Date, coretypes.Time, coretypes.DateTime,
+                        coretypes.Unit)):
+        ds = coretypes.DataShape(o)
+    elif isinstance(o, coretypes.Mono):
+        ds = o
+    elif isinstance(o, (list, tuple)):
+        ds = coretypes.DataShape(*o)
+    else:
+        raise TypeError('Cannot create dshape from object of type %s' % type(o))
+    validate(ds)
+    return ds
+
+
+def cat_dshapes(dslist):
+    """
+    Concatenates a list of dshapes together along
+    the first axis. Raises an error if there is
+    a mismatch along another axis or the measures
+    are different.
+
+    Requires that the leading dimension be a known
+    size for all data shapes.
+    TODO: Relax this restriction to support
+          streaming dimensions.
+
+    >>> cat_dshapes(dshapes('10 * int32', '5 * int32'))
+    dshape("15 * int32")
+    """
+    if len(dslist) == 0:
+        raise ValueError('Cannot concatenate an empty list of dshapes')
+    elif len(dslist) == 1:
+        return dslist[0]
+
+    outer_dim_size = operator.index(dslist[0][0])
+    inner_ds = dslist[0][1:]
+    for ds in dslist[1:]:
+        outer_dim_size += operator.index(ds[0])
+        if ds[1:] != inner_ds:
+            raise ValueError(('The datashapes to concatenate much'
+                              ' all match after'
+                              ' the first dimension (%s vs %s)') %
+                              (inner_ds, ds[1:]))
+    return coretypes.DataShape(*[coretypes.Fixed(outer_dim_size)] + list(inner_ds))
+
+
+def collect(pred, expr):
+    """ Collect terms in expression that match predicate
+
+    >>> from datashader.datashape import Unit, dshape
+    >>> predicate = lambda term: isinstance(term, Unit)
+    >>> dshape = dshape('var * {value: int64, loc: 2 * int32}')
+    >>> sorted(set(collect(predicate, dshape)), key=str)
+    [Fixed(val=2), ctype("int32"), ctype("int64"), Var()]
+    >>> from datashader.datashape import var, int64
+    >>> sorted(set(collect(predicate, [var, int64])), key=str)
+    [ctype("int64"), Var()]
+    """
+    if pred(expr):
+        return [expr]
+    if isinstance(expr, coretypes.Record):
+        return chain.from_iterable(collect(pred, typ) for typ in expr.types)
+    if isinstance(expr, coretypes.Mono):
+        return chain.from_iterable(collect(pred, typ) for typ in expr.parameters)
+    if isinstance(expr, (list, tuple)):
+        return chain.from_iterable(collect(pred, item) for item in expr)
+
+
+def has_var_dim(ds):
+    """Returns True if datashape has a variable dimension
+
+    Note currently treats variable length string as scalars.
+
+    >>> has_var_dim(dshape('2 * int32'))
+    False
+    >>> has_var_dim(dshape('var * 2 * int32'))
+    True
+    """
+    return has((coretypes.Ellipsis, coretypes.Var), ds)
+
+
+def has(typ, ds):
+    if isinstance(ds, typ):
+        return True
+    if isinstance(ds, coretypes.Record):
+        return any(has(typ, t) for t in ds.types)
+    if isinstance(ds, coretypes.Mono):
+        return any(has(typ, p) for p in ds.parameters)
+    if isinstance(ds, (list, tuple)):
+        return any(has(typ, item) for item in ds)
+    return False
+
+
+def has_ellipsis(ds):
+    """Returns True if the datashape has an ellipsis
+
+    >>> has_ellipsis(dshape('2 * int'))
+    False
+    >>> has_ellipsis(dshape('... * int'))
+    True
+    """
+    return has(coretypes.Ellipsis, ds)
diff --git a/datashader/datashape/validation.py b/datashader/datashape/validation.py
new file mode 100644
index 000000000..a60867246
--- /dev/null
+++ b/datashader/datashape/validation.py
@@ -0,0 +1,65 @@
+"""
+Datashape validation.
+"""
+
+from . import coretypes as T
+
+
+def traverse(f, t):
+    """
+    Map `f` over `t`, calling `f` with type `t` and the map result of the
+    mapping `f` over `t` 's parameters.
+
+    Parameters
+    ----------
+    f : callable
+    t : DataShape
+
+    Returns
+    -------
+    DataShape
+    """
+    if isinstance(t, T.Mono) and not isinstance(t, T.Unit):
+        return f(t, [traverse(f, p) for p in t.parameters])
+    return t
+
+
+def validate(ds):
+    """
+    Validate a datashape to see whether it is well-formed.
+
+    Parameters
+    ----------
+    ds : DataShape
+
+    Examples
+    --------
+    >>> from datashader.datashape import dshape
+    >>> dshape('10 * int32')
+    dshape("10 * int32")
+    >>> dshape('... * int32')
+    dshape("... * int32")
+    >>> dshape('... * ... * int32') # doctest: +IGNORE_EXCEPTION_DETAIL
+    Traceback (most recent call last):
+        ...
+    TypeError: Can only use a single wildcard
+    >>> dshape('T * ... * X * ... * X') # doctest: +IGNORE_EXCEPTION_DETAIL
+    Traceback (most recent call last):
+        ...
+    TypeError: Can only use a single wildcard
+    >>> dshape('T * ...') # doctest: +IGNORE_EXCEPTION_DETAIL
+    Traceback (most recent call last):
+        ...
+    DataShapeSyntaxError: Expected a dtype
+    """
+    traverse(_validate, ds)
+
+
+def _validate(ds, params):
+    if isinstance(ds, T.DataShape):
+        # Check ellipses
+        ellipses = [x for x in ds.parameters if isinstance(x, T.Ellipsis)]
+        if len(ellipses) > 1:
+            raise TypeError("Can only use a single wildcard")
+        elif isinstance(ds.parameters[-1], T.Ellipsis):
+            raise TypeError("Measure may not be an Ellipsis (...)")
diff --git a/datashader/reductions.py b/datashader/reductions.py
index e6ce7a00a..dd1b3ab8a 100644
--- a/datashader/reductions.py
+++ b/datashader/reductions.py
@@ -3,8 +3,8 @@
 from enum import Enum
 from packaging.version import Version
 import numpy as np
-from datashape import dshape, isnumeric, Record, Option
-from datashape import coretypes as ct
+from datashader.datashape import dshape, isnumeric, Record, Option
+from datashader.datashape import coretypes as ct
 from toolz import concat, unique
 import xarray as xr
 
diff --git a/datashader/utils.py b/datashader/utils.py
index 0fb7c3783..70667b1fb 100644
--- a/datashader/utils.py
+++ b/datashader/utils.py
@@ -13,7 +13,7 @@
 from xarray import DataArray
 
 import dask.dataframe as dd
-import datashape
+import datashader.datashape as datashape
 
 try:
     from datashader.datatypes import RaggedDtype
@@ -397,7 +397,7 @@ def lnglat_to_meters(longitude, latitude):
 
 # Heavily inspired by odo
 def dshape_from_pandas_helper(col):
-    """Return an object from datashape.coretypes given a column from a pandas
+    """Return an object from datashader.datashape.coretypes given a column from a pandas
     dataframe.
     """
     if (isinstance(col.dtype, type(pd.Categorical.dtype)) or
diff --git a/doc/conf.py b/doc/conf.py
index d46b689b0..0f4d438b1 100644
--- a/doc/conf.py
+++ b/doc/conf.py
@@ -1,5 +1,3 @@
-# -*- coding: utf-8 -*-
-
 from nbsite.shared_conf import *
 
 project = 'Datashader'
diff --git a/setup.py b/setup.py
index 78891011f..ef35712a1 100644
--- a/setup.py
+++ b/setup.py
@@ -11,7 +11,7 @@
 install_requires = [
     'colorcet',
     'dask',
-    'datashape',
+    'multipledispatch',
     'numba',
     'numpy',
     'pandas',


Test patch:
diff --git a/datashader/datashape/tests/__init__.py b/datashader/datashape/tests/__init__.py
new file mode 100644
index 000000000..e69de29bb
diff --git a/datashader/datashape/tests/test_coretypes.py b/datashader/datashape/tests/test_coretypes.py
new file mode 100644
index 000000000..dfb91ce3e
--- /dev/null
+++ b/datashader/datashape/tests/test_coretypes.py
@@ -0,0 +1,687 @@
+from collections import OrderedDict
+import datetime
+from operator import getitem
+import pickle
+
+import numpy as np
+import pytest
+
+from datashader.datashape.coretypes import (
+    CType,
+    Categorical,
+    DataShape,
+    Date,
+    DateTime,
+    Decimal,
+    Ellipsis,
+    Fixed,
+    Map,
+    Option,
+    R,
+    Record,
+    String,
+    Time,
+    TimeDelta,
+    Type,
+    TypeVar,
+    _unit_aliases,
+    _units,
+    int32,
+    int64,
+    null,
+    real,
+)
+from datashader.datashape import (
+    Bytes,
+    datetime_,
+    date_,
+    dshape,
+    error,
+    float64,
+    from_numpy,
+    string,
+    timedelta_,
+    to_numpy,
+    to_numpy_dtype,
+    Tuple,
+    Units,
+    uint32,
+    var,
+)
+
+
+@pytest.fixture
+def a():
+    return Record([('x', 'int'), ('y', 'int')])
+
+
+@pytest.fixture
+def b():
+    return Record([('y', 'int'), ('x', 'int')])
+
+@pytest.fixture
+def c():
+    return Record([('y', '?int'), ('x', '?int')])
+
+
+def test_respects_order(a, b):
+    assert a != b
+
+
+def test_strings():
+    assert Record([('x', 'real')]) == Record([('x', real)])
+
+
+def test_integers():
+    assert Record([(0, 'real')]) == Record([('0', real)])
+
+
+def test_error_on_datashape_with_string_argument():
+    with pytest.raises(TypeError):
+        DataShape('5 * int32')
+
+
+class TestToNumpyDtype(object):
+
+    def test_simple(self):
+        assert to_numpy_dtype(dshape('2 * int32')) == np.int32
+        assert (to_numpy_dtype(dshape('2 * {x: int32, y: int32}')) ==
+                np.dtype([('x', '<i4'), ('y', '<i4')]))
+
+    def test_datetime(self):
+        assert to_numpy_dtype(dshape('2 * datetime')) == np.dtype('M8[us]')
+
+    def test_date(self):
+        assert to_numpy_dtype(dshape('2 * date')) == np.dtype('M8[D]')
+
+    def test_string(self):
+        assert to_numpy_dtype(dshape('2 * string')) == np.dtype('O')
+
+    def test_dimensions(self):
+        assert to_numpy_dtype(dshape('var * int32')) == np.int32
+
+    def test_timedelta(self):
+        assert to_numpy_dtype(dshape('2 * timedelta')) == np.dtype('m8[us]')
+        assert to_numpy_dtype(dshape("2 * timedelta[unit='s']")) == \
+            np.dtype('m8[s]')
+
+    def test_decimal(self):
+        assert to_numpy_dtype(dshape('decimal[18,0]')) == np.int64
+        assert to_numpy_dtype(dshape('decimal[7,2]')) == np.float64
+        assert to_numpy_dtype(dshape('decimal[4]')) == np.int16
+        with pytest.raises(TypeError):
+            to_numpy_dtype(dshape('decimal[21]'))
+
+
+def test_timedelta_eval_repr():
+    assert eval(repr(dshape('timedelta'))) == dshape('timedelta')
+    assert eval(repr(dshape('timedelta[unit="ms"]'))) == \
+        dshape('timedelta[unit="ms"]')
+
+
+def test_timedelta_bad_unit():
+    with pytest.raises(ValueError):
+        dshape('timedelta[unit="foo"]')
+
+
+def test_timedelta_nano():
+    dshape('timedelta[unit="ns"]').measure.unit == 'ns'
+
+
+def test_timedelta_aliases():
+    for alias in _unit_aliases:
+        a = alias + 's'
+        assert (dshape('timedelta[unit=%r]' % a) ==
+                dshape('timedelta[unit=%r]' % _unit_aliases[alias]))
+
+
+class TestFromNumPyDtype(object):
+
+    def test_int32(self):
+        assert from_numpy((2,), 'int32') == dshape('2 * int32')
+        assert from_numpy((2,), 'i4') == dshape('2 * int32')
+
+    def test_struct(self):
+        dtype = np.dtype([('x', '<i4'), ('y', '<i4')])
+        result = from_numpy((2,), dtype)
+        assert result == dshape('2 * {x: int32, y: int32}')
+
+    def test_datetime(self):
+        keys = 'h', 'm', 's', 'ms', 'us', 'ns', 'ps', 'fs', 'as'
+        for k in keys:
+            assert from_numpy((2,),
+                              np.dtype('M8[%s]' % k)) == dshape('2 * datetime')
+
+    def test_date(self):
+        for d in ('D', 'M', 'Y', 'W'):
+            assert from_numpy((2,),
+                              np.dtype('M8[%s]' % d)) == dshape('2 * date')
+
+    def test_timedelta(self):
+        for d in _units:
+            assert from_numpy((2,),
+                              np.dtype('m8[%s]' % d)) == \
+                dshape('2 * timedelta[unit=%r]' % d)
+
+    def test_ascii_string(self):
+        assert (from_numpy((2,), np.dtype('S7')) ==
+                dshape('2 * string[7, "ascii"]'))
+
+    def test_string(self):
+        assert (from_numpy((2,), np.dtype('U7')) ==
+                dshape('2 * string[7, "U32"]'))
+
+    def test_string_from_CType_classmethod(self):
+        assert CType.from_numpy_dtype(np.dtype('S7')) == String(7, 'A')
+
+
+def test_eq():
+    assert dshape('int') == dshape('int')
+    assert dshape('int') != 'apple'
+
+
+def test_serializable():
+    ds = dshape('''{id: int64,
+                    name: string,
+                    amount: float32,
+                    arr: 3 * (int32, string)}''')
+    ds2 = pickle.loads(pickle.dumps(ds))
+
+    assert str(ds) == str(ds2)
+
+
+def test_subshape():
+    ds = dshape('5 * 3 * float32')
+    assert ds.subshape[2:] == dshape('3 * 3 * float32')
+
+    ds = dshape('5 * 3 * float32')
+    assert ds.subshape[::2] == dshape('3 * 3 * float32')
+
+
+def test_negative_slicing():
+    ds = dshape('10 * int')
+    assert ds.subshape[-3:] == dshape('3 * int')
+
+
+def test_newaxis_slicing():
+    ds = dshape('10 * int')
+    assert ds.subshape[None, :] == dshape('1 * 10 * int')
+    assert ds.subshape[:, None] == dshape('10 * 1 * int')
+
+
+def test_datashape_coerces_ints():
+    assert DataShape(5, 'int32')[0] == Fixed(5)
+    assert DataShape(5, 'int32')[1] == int32
+
+
+def test_shape():
+    assert dshape('5 * 3 * float32').shape == (5, 3)
+    assert dshape('float32').shape == ()
+    assert dshape('float32').measure.shape == ()
+    assert dshape('?float32').measure.shape == ()
+
+
+def test_option_sanitizes_strings():
+    assert Option('float32').ty == dshape('float32').measure
+
+
+def test_option_passes_itemsize():
+    assert (dshape('?float32').measure.itemsize ==
+            dshape('float32').measure.itemsize)
+
+
+class TestComplexFieldNames(object):
+
+    """
+    The tests in this class should verify that the datashape parser can handle
+    field names that contain strange characters like spaces, quotes, and
+    backslashes
+
+    The idea is that any given input datashape should be recoverable once we
+    have created the actual dshape object.
+
+    This test suite is by no means complete, but it does handle some of the
+    more common special cases (common special? oxymoron?)
+    """
+
+    def test_spaces_01(self):
+        space_dshape = "{'Unique Key': ?int64}"
+        assert space_dshape == str(dshape(space_dshape))
+
+    def test_spaces_02(self):
+        big_space_dshape = """{ 'Unique Key' : ?int64, 'Created Date' : string,
+'Closed Date' : string, Agency : string, 'Agency Name' : string,
+'Complaint Type' : string, Descriptor : string, 'Location Type' : string,
+'Incident Zip' : ?int64, 'Incident Address' : ?string, 'Street Name' : ?string,
+'Cross Street 1' : ?string, 'Cross Street 2' : ?string,
+'Intersection Street 1' : ?string, 'Intersection Street 2' : ?string,
+'Address Type' : string, City : string, Landmark : string,
+'Facility Type' : string, Status : string, 'Due Date' : string,
+'Resolution Action Updated Date' : string, 'Community Board' : string,
+Borough : string, 'X Coordinate (State Plane)' : ?int64,
+'Y Coordinate (State Plane)' : ?int64, 'Park Facility Name' : string,
+'Park Borough' : string, 'School Name' : string, 'School Number' : string,
+'School Region' : string, 'School Code' : string,
+'School Phone Number' : string, 'School Address' : string,
+'School City' : string, 'School State' : string, 'School Zip' : string,
+'School Not Found' : string, 'School or Citywide Complaint' : string,
+'Vehicle Type' : string, 'Taxi Company Borough' : string,
+'Taxi Pick Up Location' : string, 'Bridge Highway Name' : string,
+'Bridge Highway Direction' : string, 'Road Ramp' : string,
+'Bridge Highway Segment' : string, 'Garage Lot Name' : string,
+'Ferry Direction' : string, 'Ferry Terminal Name' : string,
+Latitude : ?float64, Longitude : ?float64, Location : string }"""
+
+        ds1 = dshape(big_space_dshape)
+        ds2 = dshape(str(ds1))
+
+        assert str(ds1) == str(ds2)
+
+    def test_single_quotes_01(self):
+
+        quotes_dshape = """{ 'field \\' with \\' quotes' : string }"""
+
+        ds1 = dshape(quotes_dshape)
+        ds2 = dshape(str(ds1))
+
+        assert str(ds1) == str(ds2)
+
+    def test_double_quotes_01(self):
+        quotes_dshape = """{ 'doublequote \" field \"' : int64 }"""
+        ds1 = dshape(quotes_dshape)
+        ds2 = dshape(str(ds1))
+
+        assert str(ds1) == str(ds2)
+
+    def test_multi_quotes_01(self):
+        quotes_dshape = """{
+            'field \\' with \\' quotes' : string,
+            'doublequote \" field \"' : int64
+        }"""
+
+        ds1 = dshape(quotes_dshape)
+        ds2 = dshape(str(ds1))
+
+        assert str(ds1) == str(ds2)
+
+    def test_mixed_quotes_01(self):
+        quotes_dshape = """{
+            'field \" with \\' quotes' : string,
+            'doublequote \" field \\'' : int64
+        }"""
+
+        ds1 = dshape(quotes_dshape)
+        ds2 = dshape(str(ds1))
+
+        assert str(ds1) == str(ds2)
+
+    def test_bad_02(self):
+        bad_dshape = """{ Unique Key : int64}"""
+        with pytest.raises(error.DataShapeSyntaxError):
+            dshape(bad_dshape)
+
+    def test_bad_backslashes_01(self):
+        """backslashes aren't allowed in datashapes according to the definitions
+        in lexer.py as of 2014-10-02. This is probably an oversight that should
+        be fixed.
+        """
+        backslash_dshape = """{ 'field with \\\\   backslashes' : int64 }"""
+
+        with pytest.raises(error.DataShapeSyntaxError):
+            dshape(backslash_dshape)
+
+
+def test_record_string():
+    s = '{name_with_underscores: int32}'
+    assert s.replace(' ', '') == str(dshape(s)).replace(' ', '')
+
+
+def test_record_with_unicode_name_as_numpy_dtype():
+    r = Record([(str('a'), 'int32')])
+    assert r.to_numpy_dtype() == np.dtype([('a', 'i4')])
+
+
+def test_record_from_OrderedDict():
+    r = Record(OrderedDict([('a', 'int32'), ('b', 'float64')]))
+    assert r.to_numpy_dtype() == np.dtype([('a', 'i4'), ('b', 'f8')])
+
+
+def test_tuple_datashape_to_numpy_dtype():
+    ds = dshape('5 * (int32, float32)')
+    assert to_numpy_dtype(ds) == [('f0', 'i4'), ('f1', 'f4')]
+
+
+def test_option_date_to_numpy():
+    assert Option(Date()).to_numpy_dtype() == np.dtype('datetime64[D]')
+
+
+def test_option_datetime_to_numpy():
+    assert Option(DateTime()).to_numpy_dtype() == np.dtype('datetime64[us]')
+
+
+@pytest.mark.parametrize('unit',
+                         ['Y', 'M', 'D', 'h', 'm', 's', 'ms', 'us', 'ns'])
+def test_option_timedelta_to_numpy(unit):
+    assert (Option(TimeDelta(unit=unit)).to_numpy_dtype() ==
+            np.dtype('timedelta64[%s]' % unit))
+
+
+def unique(x):
+    seen = set()
+    for el in x:
+        if el not in seen:
+            yield el
+            seen.add(el)
+
+
+@pytest.mark.parametrize('data', [list('aaaabbbccc'), [-1, 2, 3, 4, 4, 3, 5]])
+def test_categorical(data):
+    c = Categorical(tuple(unique(data)))
+    assert list(unique(c.categories)) == list(unique(data))
+    assert str(c) == 'categorical[[%s], type=%s, ordered=False]' % (
+        ', '.join(map(repr, c.categories)), c.type
+    )
+    assert (
+        repr(c) == 'Categorical(categories=[%s], type=%r, ordered=False)' % (
+            ', '.join(map(repr, c.categories)), c.type
+        )
+    )
+    assert (
+        dshape("categorical[[%s], type=%s, ordered=False]" % (
+            ', '.join(map(repr, c.categories)), c.type
+        )) == DataShape(c)
+    )
+    assert (
+        dshape("categorical[[%s], type=%s, ordered=False]" % (
+            ', '.join(map(repr, c.categories)), c.type
+        )) == DataShape(c)
+    )
+
+
+def test_long_categorical_repr():
+    cats = list('abcdefghijklmnopqrstuvwxyz')
+    c = Categorical(cats, ordered=True)
+    assert str(c) == 'categorical[[%s, ...], type=%s, ordered=True]' % (
+        ', '.join(map(repr, cats[:10])),
+        c.type
+    )
+
+
+def test_duplicate_field_names_fails():
+    fields = [('a', 'int32'), ('b', 'string'), ('a', 'float32')]
+    with pytest.raises(ValueError):
+        Record(fields)
+
+
+@pytest.mark.parametrize('ds',
+                         ['int64',
+                          'var * float64',
+                          '10 * var * int16',
+                          '{a: int32, b: ?string}',
+                          'var * {a: int32, b: ?string}',
+                          '10 * {a: ?int32, b: var * {c: string[30]}}',
+                          '{"weird col": 3 * var * 2 * ?{a: int8, b: ?uint8}}',
+                          'var * {"func-y": (A) -> var * {a: 10 * float64}}',
+                          'decimal[18]',
+                          'var * {amount: ?decimal[9,2]}'])
+def test_repr_of_eval_is_dshape(ds):
+    assert eval(repr(dshape(ds))) == dshape(ds)
+
+
+def test_complex_with_real_component_fails():
+    with pytest.raises(TypeError):
+        dshape('complex[int64]')
+
+
+def test_already_registered_type():
+    with pytest.raises(TypeError):
+        Type.register('int64', int64)
+
+
+def test_multiplication_of_dshapes():
+    with pytest.raises(TypeError):
+        int32 * 10
+
+
+def test_ellipsis_with_typevar_repr():
+    assert str(Ellipsis(typevar=TypeVar('T'))) == 'T...'
+    assert repr(Ellipsis(typevar=TypeVar('T'))) == 'Ellipsis(\'T...\')'
+
+
+def test_null_datashape_string():
+    assert str(null) == 'null'
+
+
+@pytest.mark.xfail(raises=TypeError, reason="Not yet implemented")
+def test_time_with_tz_not_a_string():
+    assert Time(tz=datetime.tzinfo())
+
+
+@pytest.mark.xfail(raises=TypeError, reason="Not yet implemented")
+def test_datetime_with_tz_not_a_string():
+    assert DateTime(tz=datetime.tzinfo())
+
+
+@pytest.mark.parametrize('unit', _units)
+def test_timedelta_repr(unit):
+    assert repr(TimeDelta(unit=unit)) == 'TimeDelta(unit=%r)' % unit
+
+
+@pytest.mark.parametrize('unit', _units)
+def test_timedelta_str(unit):
+    assert str(TimeDelta(unit=unit)) == 'timedelta[unit=%r]' % unit
+
+
+def test_unit_construction():
+    with pytest.raises(TypeError):
+        Units(1)
+    with pytest.raises(TypeError):
+        Units('kg', 1)
+
+
+def test_unit_str():
+    assert str(Units('kg')) == "units['kg']"
+    assert (str(Units('counts/time', DataShape(uint32))) ==
+            "units['counts/time', uint32]")
+
+
+def test_bytes_str():
+    assert str(Bytes()) == 'bytes'
+
+
+def test_unsupported_string_encoding():
+    with pytest.raises(ValueError):
+        String(1, 'asdfasdf')
+
+
+def test_all_dims_before_last():
+    with pytest.raises(TypeError):
+        DataShape(uint32, var, uint32)
+
+
+def test_datashape_parameter_count():
+    with pytest.raises(ValueError):
+        DataShape()
+
+
+def test_named_datashape():
+    assert str(DataShape(uint32, name='myuint')) == 'myuint'
+
+
+def test_subarray_invalid_index():
+    with pytest.raises(IndexError):
+        dshape('1 * 2 * 3 * int32').subarray(42)
+
+
+def test_record_subshape_integer_index():
+    ds = DataShape(Record([('a', 'int32')]))
+    assert ds.subshape[0] == int32
+
+
+def test_slice_subshape_negative_step():
+    ds = 30 * Record([('a', 'int32')])
+    assert ds.subshape[:-1] == 29 * Record([('a', 'int32')])
+
+
+def test_slice_subshape_negative_start():
+    ds = var * Record([('a', 'int32')])
+    assert ds.subshape[-1:] == var * Record([('a', 'int32')])
+
+
+def test_slice_subshape_bad_types():
+    ds = var * Record([('a', 'int32')])
+    with pytest.raises(TypeError):
+        assert ds.subshape[1.0]
+
+
+@pytest.mark.parametrize(['base', 'expected'],
+                         zip([timedelta_, date_, datetime_],
+                             ['timedelta64[us]', 'datetime64[D]',
+                              'datetime64[us]']))
+def test_option_to_numpy_dtype(base, expected):
+    assert Option(base).to_numpy_dtype() == np.dtype(expected)
+
+
+@pytest.mark.xfail(raises=TypeError,
+                   reason=('NumPy has no notion of missing for types other '
+                           'than timedelta, datetime, and date'))
+@pytest.mark.parametrize('base', [int32, float64, Record([('a', uint32)])])
+def test_option_to_numpy_dtype_fails(base):
+    Option(base).to_numpy_dtype()
+
+
+@pytest.mark.xfail(raises=NotImplementedError,
+                   reason='DataShape does not know about void types (yet?)')
+def test_from_numpy_dtype_fails():
+    x = np.zeros(2, np.dtype([('a', 'int32')]))
+    CType.from_numpy_dtype(x[0].dtype)
+
+
+def test_ctype_alignment():
+    assert int32.alignment == 4
+
+
+def test_fixed_dimensions_must_be_positive():
+    with pytest.raises(ValueError):
+        Fixed(-1)
+
+
+def test_fixed_comparison():
+    assert Fixed(1) != 'a'
+
+
+def test_typevar_must_be_upper_case():
+    with pytest.raises(ValueError):
+        TypeVar('t')
+
+
+def test_typevar_repr():
+    assert repr(TypeVar('T')) == "TypeVar(symbol='T')"
+
+
+def test_funcproto_attrs():
+    f = dshape('(int32, ?float64) -> {a: ?string}').measure
+    assert f.restype == DataShape(Record([('a', Option(String()))]))
+    assert f.argtypes == (DataShape(int32), DataShape(Option(float64)))
+
+
+def test_tuple_str():
+    assert str(Tuple([Option(int32), float64])) == '(?int32, float64)'
+
+
+def test_to_numpy_fails():
+    ds = var * int32
+    with pytest.raises(TypeError):
+        to_numpy(ds)
+    with pytest.raises(TypeError):
+        to_numpy(Option(int32))
+
+
+def test_map():
+    fk = Map(int32, Record([('a', int32)]))
+    assert fk.key == int32
+    assert fk.value == Record([('a', int32)])
+    assert fk.value.dict == {'a': int32}
+    assert fk.value.fields == (('a', int32),)
+    assert fk.to_numpy_dtype() == np.dtype('int32')
+
+
+def test_map_parse():
+    result = dshape("var * {b: map[int32, {a: int64}]}")
+    recmeasure = Map(dshape(int32), DataShape(Record([('a', int64)])))
+    assert result == DataShape(var, Record([('b', recmeasure)]))
+
+
+def test_decimal_attributes():
+    d1 = Decimal(18)
+    assert d1.precision == 18 and d1.scale == 0
+    d2 = Decimal(4, 0)
+    assert d2.precision == 4 and d2.scale == 0
+    d3 = Decimal(11, 2)
+    assert d3.precision == 11 and d3.scale == 2
+    with pytest.raises(TypeError):
+        Decimal()
+
+
+def test_record_literal():
+    assert R is Record
+    assert R['a':'int32'] == R([('a', 'int32')])
+    assert R['a':'int32', 'b':'int64'] == R([('a', 'int32'), ('b', 'int64')])
+
+
+@pytest.mark.parametrize('invalid', (
+    # Non slice objects
+    None,
+    0,
+    'a',
+    # Invalid slices
+    np.s_[:],
+    np.s_['a':],
+    np.s_[:'a'],
+    np.s_['a'::'int32'],  # double ':'
+    np.s_[:'int32'],
+    np.s_[0:'int32'],
+))
+def test_invalid_record_literal(invalid):
+    assert pytest.raises(TypeError, getitem, R, invalid)
+
+
+@pytest.mark.parametrize(
+    ['names', 'typ'],
+    [
+        (['foo', b'\xc4\x87'.decode('utf8')], str),
+        (['foo', 'bar'], str),
+        (list(u'ab'), str)
+    ]
+)
+def test_unicode_record_names(names, typ):
+    types = [int64, float64]
+    record = Record(list(zip(names, types)))
+    string_type, = set(map(type, record.names))
+    assert record.names == names
+    assert record.types == types
+    assert all(isinstance(s, string_type) for s in record.names)
+
+
+equiv_dshape_pairs = [(dshape('?string'), Option('string')),
+                      (dshape('string'), string),
+                      (dshape('datetime'), datetime_),
+                      (dshape('?datetime'), Option(datetime_)),
+                      (dshape('10 * int32'), 10 * int32),
+                      (dshape('var * ?int32'), var * Option(int32)),
+                      (dshape('10 * ?float64'), Fixed(10) * Option(float64))]
+
+@pytest.mark.parametrize('a,b', equiv_dshape_pairs)
+def test_hash_and_eq_consistency(a, b):
+    assert a == b
+    assert hash(a) == hash(b)
+
+
+def test_record_parse_optional(b, c):
+
+    assert all(isinstance(ty, Option) for ty in c.types)
+
+    assert (
+        [ty for ty in b.types] ==
+        [oty.ty for oty in c.types]
+    )
diff --git a/datashader/datashape/tests/test_creation.py b/datashader/datashape/tests/test_creation.py
new file mode 100644
index 000000000..e7872fe45
--- /dev/null
+++ b/datashader/datashape/tests/test_creation.py
@@ -0,0 +1,215 @@
+from __future__ import absolute_import, division, print_function
+
+import ctypes
+import unittest
+
+import pytest
+
+from datashader import datashape
+from datashader.datashape import dshape, error, DataShape, Record
+
+
+class TestDataShapeCreation(unittest.TestCase):
+
+    def test_raise_on_bad_input(self):
+        # Make sure it raises exceptions on a few nonsense inputs
+        self.assertRaises(TypeError, dshape, None)
+        self.assertRaises(TypeError, dshape, lambda x: x+1)
+        # Check issue 11
+        self.assertRaises(datashape.DataShapeSyntaxError, dshape, '1 *')
+        self.assertRaises(datashape.DataShapeSyntaxError, dshape, '1,')
+
+    def test_reserved_future_bigint(self):
+        # The "bigint" datashape is reserved for a future big integer type
+        self.assertRaises(Exception, dshape, "bigint")
+
+    def test_atom_shapes(self):
+        self.assertEqual(dshape('bool'), dshape(datashape.bool_))
+        self.assertEqual(dshape('int8'), dshape(datashape.int8))
+        self.assertEqual(dshape('int16'), dshape(datashape.int16))
+        self.assertEqual(dshape('int32'), dshape(datashape.int32))
+        self.assertEqual(dshape('int64'), dshape(datashape.int64))
+        self.assertEqual(dshape('uint8'), dshape(datashape.uint8))
+        self.assertEqual(dshape('uint16'), dshape(datashape.uint16))
+        self.assertEqual(dshape('uint32'), dshape(datashape.uint32))
+        self.assertEqual(dshape('uint64'), dshape(datashape.uint64))
+        self.assertEqual(dshape('float32'), dshape(datashape.float32))
+        self.assertEqual(dshape('float64'), dshape(datashape.float64))
+        self.assertEqual(dshape('complex64'), dshape(datashape.complex64))
+        self.assertEqual(dshape('complex128'), dshape(datashape.complex128))
+        self.assertEqual(dshape('complex64'), dshape('complex[float32]'))
+        self.assertEqual(dshape('complex128'), dshape('complex[float64]'))
+        self.assertEqual(dshape("string"), dshape(datashape.string))
+        self.assertEqual(dshape("json"), dshape(datashape.json))
+        self.assertEqual(dshape("date"), dshape(datashape.date_))
+        self.assertEqual(dshape("time"), dshape(datashape.time_))
+        self.assertEqual(dshape("datetime"), dshape(datashape.datetime_))
+
+    def test_atom_shape_errors(self):
+        self.assertRaises(error.DataShapeSyntaxError, dshape, 'boot')
+        self.assertRaises(error.DataShapeSyntaxError, dshape, 'int33')
+        self.assertRaises(error.DataShapeSyntaxError, dshape, '12')
+        self.assertRaises(error.DataShapeSyntaxError, dshape, 'var')
+
+    @pytest.mark.xfail(reason='implements has not been implemented in the new parser')
+    def test_constraints_error(self):
+        self.assertRaises(error.DataShapeTypeError, dshape,
+                          'A : integral * B : numeric')
+
+    def test_ellipsis_error(self):
+        self.assertRaises(error.DataShapeSyntaxError, dshape, 'T * ...')
+        self.assertRaises(error.DataShapeSyntaxError, dshape, 'T * S...')
+
+    @pytest.mark.xfail(reason='type decl has been removed in the new parser')
+    def test_type_decl(self):
+        self.assertRaises(error.DataShapeTypeError, dshape, 'type X T = 3, T')
+
+    @pytest.mark.xfail(reason='type decl has been removed in the new parser')
+    def test_type_decl_concrete(self):
+        self.assertEqual(dshape('3, int32'), dshape('type X = 3, int32'))
+
+    def test_string_atom(self):
+        self.assertEqual(dshape('string'), dshape("string['U8']"))
+        self.assertEqual(dshape("string['ascii']")[0].encoding, 'A')
+        self.assertEqual(dshape("string['A']")[0].encoding, 'A')
+        self.assertEqual(dshape("string['utf-8']")[0].encoding, 'U8')
+        self.assertEqual(dshape("string['U8']")[0].encoding, 'U8')
+        self.assertEqual(dshape("string['utf-16']")[0].encoding, 'U16')
+        self.assertEqual(dshape("string['U16']")[0].encoding, 'U16')
+        self.assertEqual(dshape("string['utf-32']")[0].encoding, 'U32')
+        self.assertEqual(dshape("string['U32']")[0].encoding, 'U32')
+
+    def test_time(self):
+        self.assertEqual(dshape('time')[0].tz, None)
+        self.assertEqual(dshape('time[tz="UTC"]')[0].tz, 'UTC')
+        self.assertEqual(dshape('time[tz="America/Vancouver"]')[0].tz,
+                         'America/Vancouver')
+        self.assertEqual(str(dshape('time[tz="UTC"]')), "time[tz='UTC']")
+
+    def test_datetime(self):
+        self.assertEqual(dshape('datetime')[0].tz, None)
+        self.assertEqual(dshape('datetime[tz="UTC"]')[0].tz, 'UTC')
+        self.assertEqual(dshape('datetime[tz="America/Vancouver"]')[0].tz,
+                         'America/Vancouver')
+        self.assertEqual(str(dshape('datetime[tz="UTC"]')),
+                         "datetime[tz='UTC']")
+
+    def test_units(self):
+        self.assertEqual(dshape('units["second"]')[0].unit, 'second')
+        self.assertEqual(dshape('units["second"]')[0].tp, dshape('float64'))
+        self.assertEqual(dshape('units["second", int32]')[0].unit, 'second')
+        self.assertEqual(dshape('units["second", int32]')[0].tp,
+                         dshape('int32'))
+
+    def test_empty_struct(self):
+        self.assertEqual(dshape('{}'), DataShape(Record([])))
+
+    def test_struct_of_array(self):
+        self.assertEqual(str(dshape('5 * int32')), '5 * int32')
+        self.assertEqual(str(dshape('{field: 5 * int32}')),
+                         '{field: 5 * int32}')
+        self.assertEqual(str(dshape('{field: M * int32}')),
+                         '{field: M * int32}')
+
+    def test_ragged_array(self):
+        self.assertTrue(isinstance(dshape('3 * var * int32')[1],
+                        datashape.Var))
+
+    def test_from_numpy_fields(self):
+        import numpy as np
+        dt = np.dtype('i4,i8,f8')
+        ds = datashape.from_numpy((), dt)
+        self.assertEqual(ds.names, ['f0', 'f1', 'f2'])
+        self.assertEqual(ds.types,
+                         [datashape.int32, datashape.int64, datashape.float64])
+
+    def test_to_numpy_fields(self):
+        import numpy as np
+        ds = datashape.dshape('{x: int32, y: float32}')
+        shape, dt = datashape.to_numpy(ds)
+        self.assertEqual(shape, ())
+        self.assertEqual(dt, np.dtype([('x', 'int32'), ('y', 'float32')]))
+
+    def test_syntax(self):
+        self.assertEqual(datashape.Fixed(3) * dshape('int32'),
+                         dshape('3 * int32'))
+        self.assertEqual(3 * dshape('int32'),
+                         dshape('3 * int32'))
+        self.assertEqual(datashape.Var() * dshape('int32'),
+                         dshape('var * int32'))
+        self.assertEqual(datashape.Var() * datashape.int32,
+                         dshape('var * int32'))
+        self.assertEqual(datashape.Var() * 'int32',
+                         dshape('var * int32'))
+        self.assertEqual(3 * datashape.int32,
+                         dshape('3 * int32'))
+
+    def test_python_containers(self):
+        var = datashape.Var()
+        int32 = datashape.int32
+        self.assertEqual(dshape('3 * int32'),
+                         dshape((3, int32)))
+        self.assertEqual(dshape('3 * int32'),
+                         dshape([3, int32]))
+        self.assertEqual(dshape('var * 3 * int32'),
+                         dshape((var, 3, int32)))
+
+    dshapes = ['bool',
+               'int8',
+               'int16',
+               'int32',
+               'int64',
+               'uint8',
+               'uint16',
+               'uint32',
+               'uint64',
+               'float32',
+               'float64',
+               'complex64',
+               'complex128',
+               'string',
+               'json',
+               'date',
+               'time',
+               'datetime',
+               'int',
+               'real',
+               'complex',
+               'intptr',
+               'uintptr',
+               '{id: int8, value: bool, result: int16}',
+               '{a: int32, b: int64, x: uint8, y: uint16, z: uint32}',
+               '{a: float32, b: float64, c: complex64, d: complex128, '
+               ' e: string, f: json, g: date, h: time, i: datetime}']
+
+    dimensions = ['2',
+                  '100',
+                  '...',
+                  'var',
+                  '2 * var * 2',
+                  ]
+
+    def test_dshape_into_repr(self):
+        for ds in self.dshapes:
+            self.assertEqual(eval(repr(dshape(ds))), dshape(ds))
+            for dm in self.dimensions:
+                d = dshape(dm + ' * ' + ds)
+                self.assertEqual(eval(repr(d)), d)
+
+
+pointer_sizes = {
+    4: {
+        'intptr': datashape.int32,
+        'uintptr': datashape.uint32,
+    },
+    8: {
+        'intptr': datashape.int64,
+        'uintptr': datashape.uint64,
+    }
+}
+
+
+@pytest.mark.parametrize('kind', ['intptr', 'uintptr'])
+def test_intptr_size(kind):
+    assert (dshape(kind) ==
+            dshape(pointer_sizes[ctypes.sizeof(ctypes.c_void_p)][kind]))
diff --git a/datashader/datashape/tests/test_discovery.py b/datashader/datashape/tests/test_discovery.py
new file mode 100644
index 000000000..9ecc5d1c3
--- /dev/null
+++ b/datashader/datashape/tests/test_discovery.py
@@ -0,0 +1,350 @@
+from collections import OrderedDict
+from itertools import starmap
+from types import MappingProxyType
+from warnings import catch_warnings, simplefilter
+
+import numpy as np
+import pytest
+
+from datashader.datashape.discovery import (
+    discover, null, unite_identical, unite_base, unite_merge_dimensions, do_one,
+    lowest_common_dshape)
+from datashader.datashape.coretypes import (
+    int64, float64, complex128, string, bool_, Tuple, Record, date_, datetime_, time_,
+    timedelta_, int32, var, Option, real, Null, TimeDelta, String, float32, R)
+from datashader.datashape.util.testing import assert_dshape_equal
+from datashader.datashape import dshape
+from datetime import date, time, datetime, timedelta
+
+
+def test_simple():
+    assert discover(3) == int64
+    assert discover(3.0) == float64
+    assert discover(3.0 + 1j) == complex128
+    assert discover('Hello') == string
+    assert discover(True) == bool_
+    assert discover(None) == null
+
+
+def test_list():
+    assert discover([1, 2, 3]) == 3 * discover(1)
+    assert discover([1.0, 2.0, 3.0]) == 3 * discover(1.0)
+
+
+def test_set():
+    assert discover(set([1])) == 1 * discover(1)
+
+
+def test_frozenset():
+    assert discover(frozenset([1])) == 1 * discover(1)
+
+
+def test_heterogeneous_ordered_container():
+    assert discover(('Hello', 1)) == Tuple([discover('Hello'), discover(1)])
+
+
+def test_string():
+    assert discover('1') == discover(1)
+    assert discover('1.0') == discover(1.0)
+    assert discover('True') == discover(True)
+    assert discover('true') == discover(True)
+
+
+def test_record():
+    assert (discover({'name': 'Alice', 'amount': 100}) ==
+            Record([['amount', discover(100)],
+                    ['name', discover('Alice')]]))
+
+
+def test_mappingproxy():
+    d = {'a': np.int64(1), 'b': 'cs', 'c': np.float32(1.0)}
+    assert_dshape_equal(
+        discover(MappingProxyType(d)),
+        discover(d),
+    )
+
+
+def test_ordereddict():
+    od = OrderedDict((('c', np.int64(1)), ('b', 'cs'), ('a', np.float32(1.0))))
+    assert_dshape_equal(
+        discover(od),
+        R['c': int64, 'b': string, 'a': float32],
+    )
+
+
+def test_datetime():
+    inputs = ["1991-02-03 04:05:06",
+              "11/12/1822 06:47:26.00",
+              "1822-11-12T06:47:26",
+              "Fri Dec 19 15:10:11 1997",
+              "Friday, November 11, 2005 17:56:21",
+              "1982-2-20 5:02:00",
+              "20030331 05:59:59.9",
+              "Jul  6 2030  5:55PM",
+              "1994-10-20 T 11:15",
+              "2013-03-04T14:38:05.123",
+              datetime(2014, 1, 1, 12, 1, 1),
+              # "15MAR1985:14:15:22",
+              # "201303041438"
+              ]
+    for dt in inputs:
+        assert discover(dt) == datetime_
+
+
+def test_string_date():
+    assert discover('2014-01-01') == date_
+
+
+def test_python_date():
+    assert discover(date(2014, 1, 1)) == date_
+
+
+def test_single_space_string_is_not_date():
+    assert discover(' ') == string
+
+
+def test_string_that_looks_like_date():
+    # GH 91
+    assert discover("31-DEC-99 12.00.00.000000000") == string
+
+
+def test_time():
+    assert discover(time(12, 0, 1)) == time_
+
+
+def test_timedelta():
+    objs = starmap(timedelta, (range(10, 10 - i, -1) for i in range(1, 8)))
+    for ts in objs:
+        assert discover(ts) == timedelta_
+
+
+def test_timedelta_strings():
+    inputs = ["1 day",
+              "-2 hours",
+              "3 seconds",
+              "1 microsecond",
+              "1003 milliseconds"]
+    for ts in inputs:
+        assert discover(ts) == TimeDelta(unit=ts.split()[1])
+
+    with pytest.raises(ValueError):
+        TimeDelta(unit='buzz light-years')
+
+
+def test_time_string():
+    assert discover('12:00:01') == time_
+    assert discover('12:00:01.000') == time_
+    assert discover('12:00:01.123456') == time_
+    assert discover('12:00:01.1234') == time_
+    assert discover('10-10-01T12:00:01') == datetime_
+    assert discover('10-10-01 12:00:01') == datetime_
+
+
+def test_integrative():
+    data = [{'name': 'Alice', 'amount': '100'},
+            {'name': 'Bob', 'amount': '200'},
+            {'name': 'Charlie', 'amount': '300'}]
+
+    assert (dshape(discover(data)) ==
+            dshape('3 * {amount: int64, name: string}'))
+
+
+def test_numpy_scalars():
+    assert discover(np.int32(1)) == int32
+    assert discover(np.float64(1)) == float64
+
+
+def test_numpy_array():
+    assert discover(np.ones((3, 2), dtype=np.int32)) == dshape('3 * 2 * int32')
+
+
+def test_numpy_array_with_strings():
+    x = np.array(['Hello', 'world'], dtype='O')
+    assert discover(x) == 2 * string
+
+
+def test_numpy_recarray_with_strings():
+    x = np.array([('Alice', 1), ('Bob', 2)],
+                 dtype=[('name', 'O'), ('amt', 'i4')])
+    assert discover(x) == dshape('2 * {name: string, amt: int32}')
+
+
+unite = do_one([unite_identical,
+                unite_merge_dimensions,
+                unite_base])
+
+
+def test_unite():
+    assert unite([int32, int32, int32]) == 3 * int32
+    assert unite([3 * int32, 2 * int32]) == 2 * (var * int32)
+    assert unite([2 * int32, 2 * int32]) == 2 * (2 * int32)
+    assert unite([3 * (2 * int32), 2 * (2 * int32)]) == 2 * (var * (2 * int32))
+
+
+def test_unite_missing_values():
+    assert unite([int32, null, int32]) == 3 * Option(int32)
+    assert unite([string, null, int32])
+
+
+def test_unite_tuples():
+    assert (discover([[1, 1, 'hello'],
+                     [1, '', ''],
+                     [1, 1, 'hello']]) ==
+            3 * Tuple([int64, Option(int64), Option(string)]))
+
+    assert (discover([[1, 1, 'hello', 1],
+                     [1, '', '', 1],
+                     [1, 1, 'hello', 1]]) ==
+            3 * Tuple([int64, Option(int64), Option(string), int64]))
+
+
+def test_unite_records():
+    assert (discover([{'name': 'Alice', 'balance': 100},
+                     {'name': 'Bob', 'balance': ''}]) ==
+            2 * Record([['balance', Option(int64)], ['name', string]]))
+
+    assert (discover([{'name': 'Alice', 's': 'foo'},
+                     {'name': 'Bob', 's': None}]) ==
+            2 * Record([['name', string], ['s', Option(string)]]))
+
+    assert (discover([{'name': 'Alice', 's': 'foo', 'f': 1.0},
+                     {'name': 'Bob', 's': None, 'f': None}]) ==
+            2 * Record([['f', Option(float64)],
+                        ['name', string],
+                        ['s', Option(string)]]))
+
+    # assert unite((Record([['name', string], ['balance', int32]]),
+    #               Record([['name', string]]))) == \
+    #                 Record([['name', string], ['balance', Option(int32)]])
+
+
+def test_dshape_missing_data():
+    assert (discover([[1, 2, '', 3],
+                     [1, 2, '', 3],
+                     [1, 2, '', 3]]) ==
+            3 * Tuple([int64, int64, null, int64]))
+
+
+def test_discover_mixed():
+    i = discover(1)
+    f = discover(1.0)
+    exp = 10 * Tuple([i, i, f, f])
+    assert dshape(discover([[1, 2, 1.0, 2.0]] * 10)) == exp
+
+    exp = 10 * (4 * f)
+    assert dshape(discover([[1, 2, 1.0, 2.0], [1.0, 2.0, 1, 2]] * 5)) == exp
+
+
+def test_test():
+    expected = 2 * Tuple([string, int64])
+    assert discover([['Alice', 100], ['Bob', 200]]) == expected
+
+
+def test_discover_appropriate():
+    assert discover((1, 1.0)) == Tuple([int64, real])
+    assert discover([(1, 1.0), (1, 1.0), (1, 1)]) == 3 * Tuple([int64, real])
+
+
+def test_big_discover():
+    data = [['1'] + ['hello']*20] * 10
+    assert discover(data) == 10 * Tuple([int64] + [string]*20)
+
+
+def test_unite_base():
+    assert unite_base([date_, datetime_]) == 2 * datetime_
+
+
+def test_list_of_dicts_no_difference():
+    data = [{'name': 'Alice', 'amount': 100},
+            {'name': 'Bob'}]
+    result = discover(data)
+    expected = dshape('2 * {amount: ?int64, name: string}')
+    assert result == expected
+
+
+def test_list_of_dicts_difference():
+    data = [{'name': 'Alice', 'amount': 100},
+            {'name': 'Bob', 'house_color': 'blue'}]
+    result = discover(data)
+    s = '2 * {amount: ?int64, house_color: ?string, name: string}'
+    expected = dshape(s)
+    assert result == expected
+
+
+def test_unite_base_on_records():
+    dshapes = [dshape('{name: string, amount: int32}'),
+               dshape('{name: string, amount: int32}')]
+    assert unite_base(dshapes) == dshape('2 * {name: string, amount: int32}')
+
+    dshapes = [Null(), dshape('{name: string, amount: int32}')]
+    assert unite_base(dshapes) == dshape('2 * ?{name: string, amount: int32}')
+
+    dshapes = [dshape('{name: string, amount: int32}'),
+               dshape('{name: string, amount: int64}')]
+    assert unite_base(dshapes) == dshape('2 * {name: string, amount: int64}')
+
+
+def test_nested_complex_record_type():
+    dt = np.dtype([('a', 'U7'), ('b', [('c', 'int64', 2), ('d', 'float64')])])
+    x = np.zeros(5, dt)
+    s = "5 * {a: string[7, 'U32'], b: {c: 2 * int64, d: float64}}"
+    assert discover(x) == dshape(s)
+
+
+def test_letters_only_strings():
+    strings = ('sunday', 'monday', 'tuesday', 'wednesday', 'thursday',
+               'friday', 'saturday', 'a', 'b', 'now', 'yesterday', 'tonight')
+    for s in strings:
+        assert discover(s) == string
+
+
+def test_discover_array_like():
+    class MyArray(object):
+        def __init__(self, shape, dtype):
+            self.shape = shape
+            self.dtype = dtype
+
+    with catch_warnings(record=True) as wl:
+        simplefilter('always')
+        assert discover(MyArray((4, 3), 'f4')) == dshape('4 * 3 * float32')
+    assert len(wl) == 1
+    assert issubclass(wl[0].category, DeprecationWarning)
+    assert 'MyArray' in str(wl[0].message)
+
+
+def test_discover_bytes():
+    x = b'abcdefg'
+    assert discover(x) == String('A')
+
+
+def test_discover_undiscoverable():
+    class MyClass(object):
+        pass
+    with pytest.raises(NotImplementedError):
+        discover(MyClass())
+
+
+@pytest.mark.parametrize('seq', [(), [], set()])
+def test_discover_empty_sequence(seq):
+    assert discover(seq) == var * string
+
+
+@pytest.mark.xfail(raises=ValueError, reason='Not yet implemented')
+def test_lowest_common_dshape_varlen_strings():
+    assert lowest_common_dshape([String(10), String(11)]) == String(11)
+    assert lowest_common_dshape([String(11), string]) == string
+
+
+def test_discover_mock():
+    try:
+        from unittest.mock import Mock
+    except ImportError:
+        from mock import Mock
+
+    # This used to segfault because we were sending mocks into numpy
+    with pytest.raises(NotImplementedError):
+        discover(Mock())
+
+
+def test_string_with_overflow():
+    assert discover('INF US Equity') == string
diff --git a/datashader/datashape/tests/test_lexer.py b/datashader/datashape/tests/test_lexer.py
new file mode 100644
index 000000000..e56e6a427
--- /dev/null
+++ b/datashader/datashape/tests/test_lexer.py
@@ -0,0 +1,150 @@
+"""
+Test the DataShape lexer.
+"""
+
+from __future__ import absolute_import, division, print_function
+
+import unittest
+
+from datashader import datashape
+from datashader.datashape import lexer
+
+
+class TestDataShapeLexer(unittest.TestCase):
+
+    def check_isolated_token(self, ds_str, tname, val=None):
+        # The token name should be a property in parser
+        tid = getattr(lexer, tname)
+        # Lexing should produce a single token matching the specification
+        self.assertEqual(list(lexer.lex(ds_str)),
+                         [lexer.Token(tid, tname, (0, len(ds_str)), val)])
+
+    def check_failing_token(self, ds_str):
+        # Creating the lexer will fail, because the error is
+        # in the first token.
+        self.assertRaises(datashape.DataShapeSyntaxError, list, lexer.lex(ds_str))
+
+    def test_isolated_tokens(self):
+        self.check_isolated_token('testing', 'NAME_LOWER', 'testing')
+        self.check_isolated_token('Testing', 'NAME_UPPER', 'Testing')
+        self.check_isolated_token('_testing', 'NAME_OTHER', '_testing')
+        self.check_isolated_token('*', 'ASTERISK')
+        self.check_isolated_token(',', 'COMMA')
+        self.check_isolated_token('=', 'EQUAL')
+        self.check_isolated_token(':', 'COLON')
+        self.check_isolated_token('[', 'LBRACKET')
+        self.check_isolated_token(']', 'RBRACKET')
+        self.check_isolated_token('{', 'LBRACE')
+        self.check_isolated_token('}', 'RBRACE')
+        self.check_isolated_token('(', 'LPAREN')
+        self.check_isolated_token(')', 'RPAREN')
+        self.check_isolated_token('...', 'ELLIPSIS')
+        self.check_isolated_token('->', 'RARROW')
+        self.check_isolated_token('?', 'QUESTIONMARK')
+        self.check_isolated_token('32102', 'INTEGER', 32102)
+        self.check_isolated_token('->', 'RARROW')
+        self.check_isolated_token('"testing"', 'STRING', 'testing')
+        self.check_isolated_token("'testing'", 'STRING', 'testing')
+
+    def test_integer(self):
+        # Digits
+        self.check_isolated_token('0', 'INTEGER', 0)
+        self.check_isolated_token('1', 'INTEGER', 1)
+        self.check_isolated_token('2', 'INTEGER', 2)
+        self.check_isolated_token('3', 'INTEGER', 3)
+        self.check_isolated_token('4', 'INTEGER', 4)
+        self.check_isolated_token('5', 'INTEGER', 5)
+        self.check_isolated_token('6', 'INTEGER', 6)
+        self.check_isolated_token('7', 'INTEGER', 7)
+        self.check_isolated_token('8', 'INTEGER', 8)
+        self.check_isolated_token('9', 'INTEGER', 9)
+        # Various-sized numbers
+        self.check_isolated_token('10', 'INTEGER', 10)
+        self.check_isolated_token('102', 'INTEGER', 102)
+        self.check_isolated_token('1024', 'INTEGER', 1024)
+        self.check_isolated_token('10246', 'INTEGER', 10246)
+        self.check_isolated_token('102468', 'INTEGER', 102468)
+        self.check_isolated_token('1024683', 'INTEGER', 1024683)
+        self.check_isolated_token('10246835', 'INTEGER', 10246835)
+        self.check_isolated_token('102468357', 'INTEGER', 102468357)
+        self.check_isolated_token('1024683579', 'INTEGER', 1024683579)
+        # Leading zeros are not allowed
+        self.check_failing_token('00')
+        self.check_failing_token('01')
+        self.check_failing_token('090')
+
+    def test_string(self):
+        # Trivial strings
+        self.check_isolated_token('""', 'STRING', '')
+        self.check_isolated_token("''", 'STRING', '')
+        self.check_isolated_token('"test"', 'STRING', 'test')
+        self.check_isolated_token("'test'", 'STRING', 'test')
+        # Valid escaped characters
+        self.check_isolated_token(r'"\"\b\f\n\r\t\ub155"', 'STRING',
+                                  u'"\b\f\n\r\t\ub155')
+        self.check_isolated_token(r"'\'\b\f\n\r\t\ub155'", 'STRING',
+                                  u"'\b\f\n\r\t\ub155")
+        # A sampling of invalid escaped characters
+        self.check_failing_token(r'''"\'"''')
+        self.check_failing_token(r"""'\"'""")
+        self.check_failing_token(r"'\a'")
+        self.check_failing_token(r"'\s'")
+        self.check_failing_token(r"'\R'")
+        self.check_failing_token(r"'\N'")
+        self.check_failing_token(r"'\U'")
+        self.check_failing_token(r"'\u123g'")
+        self.check_failing_token(r"'\u123'")
+        # Some unescaped and escapted unicode characters
+        self.check_isolated_token(u'"\uc548\ub155 \\uc548\\ub155"', 'STRING',
+                                  u'\uc548\ub155 \uc548\ub155')
+
+    def test_failing_tokens(self):
+        self.check_failing_token('~')
+        self.check_failing_token('`')
+        self.check_failing_token('@')
+        self.check_failing_token('$')
+        self.check_failing_token('%')
+        self.check_failing_token('^')
+        self.check_failing_token('&')
+        self.check_failing_token('-')
+        self.check_failing_token('+')
+        self.check_failing_token(';')
+        self.check_failing_token('<')
+        self.check_failing_token('>')
+        self.check_failing_token('.')
+        self.check_failing_token('..')
+        self.check_failing_token('/')
+        self.check_failing_token('|')
+        self.check_failing_token('\\')
+
+    def test_whitespace(self):
+        expected_idval = [(lexer.COLON, None),
+                          (lexer.STRING, 'a'),
+                          (lexer.INTEGER, 12345),
+                          (lexer.RARROW, None),
+                          (lexer.EQUAL, None),
+                          (lexer.ASTERISK, None),
+                          (lexer.NAME_OTHER, '_b')]
+        # With minimal whitespace
+        toks = list(lexer.lex(':"a"12345->=*_b'))
+        self.assertEqual([(tok.id, tok.val) for tok in toks], expected_idval)
+        # With spaces
+        toks = list(lexer.lex(' : "a" 12345 -> = * _b '))
+        self.assertEqual([(tok.id, tok.val) for tok in toks], expected_idval)
+        # With tabs
+        toks = list(lexer.lex('\t:\t"a"\t12345\t->\t=\t*\t_b\t'))
+        self.assertEqual([(tok.id, tok.val) for tok in toks], expected_idval)
+        # With newlines
+        toks = list(lexer.lex('\n:\n"a"\n12345\n->\n=\n*\n_b\n'))
+        self.assertEqual([(tok.id, tok.val) for tok in toks], expected_idval)
+        # With spaces, tabs, newlines and comments
+        toks = list(lexer.lex('# comment\n' +
+                               ': # X\n' +
+                               ' "a" # "b"\t\n' +
+                               '\t12345\n\n' +
+                               '->\n' +
+                               '=\n' +
+                               '*\n' +
+                               '_b # comment\n' +
+                               ' \t # end'))
+        self.assertEqual([(tok.id, tok.val) for tok in toks], expected_idval)
diff --git a/datashader/datashape/tests/test_operations.py b/datashader/datashape/tests/test_operations.py
new file mode 100644
index 000000000..32a6282ac
--- /dev/null
+++ b/datashader/datashape/tests/test_operations.py
@@ -0,0 +1,26 @@
+from datashader import datashape
+import pytest
+
+
+def test_scalar_subarray():
+    assert datashape.int32.subarray(0) == datashape.int32
+    with pytest.raises(IndexError):
+        datashape.int32.subarray(1)
+    assert datashape.string.subarray(0) == datashape.string
+    with pytest.raises(IndexError):
+        datashape.string.subarray(1)
+
+
+def test_array_subarray():
+    assert (datashape.dshape('3 * int32').subarray(0) ==
+            datashape.dshape('3 * int32'))
+    assert (datashape.dshape('3 * int32').subarray(1) ==
+            datashape.DataShape(datashape.int32))
+    assert (str(datashape.dshape('3 * var * M * int32').subarray(2)) ==
+            str(datashape.dshape('M * int32')))
+    assert (str(datashape.dshape('3 * var * M * float64').subarray(3)) ==
+            str(datashape.float64))
+
+
+def test_dshape_compare():
+    assert datashape.int32 != datashape.dshape('1 * int32')
diff --git a/datashader/datashape/tests/test_parser.py b/datashader/datashape/tests/test_parser.py
new file mode 100644
index 000000000..6258b72c4
--- /dev/null
+++ b/datashader/datashape/tests/test_parser.py
@@ -0,0 +1,661 @@
+"""
+Test the DataShape parser.
+"""
+
+from __future__ import absolute_import, division, print_function
+
+import unittest
+import pytest
+
+from datashader import datashape
+from datashader.datashape.util.testing import assert_dshape_equal
+from datashader.datashape.parser import parse
+from datashader.datashape import coretypes as ct
+from datashader.datashape import DataShapeSyntaxError
+
+
+@pytest.fixture
+def sym():
+    return datashape.TypeSymbolTable()
+
+
+class TestDataShapeParseBasicDType(unittest.TestCase):
+
+    def setUp(self):
+        # Create a default symbol table for the parser to use
+        self.sym = datashape.TypeSymbolTable()
+
+    def test_bool(self):
+        self.assertEqual(parse('bool', self.sym),
+                         ct.DataShape(ct.bool_))
+
+    def test_signed_integers(self):
+        self.assertEqual(parse('int8', self.sym),
+                         ct.DataShape(ct.int8))
+        self.assertEqual(parse('int16', self.sym),
+                         ct.DataShape(ct.int16))
+        self.assertEqual(parse('int32', self.sym),
+                         ct.DataShape(ct.int32))
+        self.assertEqual(parse('int64', self.sym),
+                         ct.DataShape(ct.int64))
+        # self.assertEqual(parse('int128', self.sym),
+        #                 ct.DataShape(ct.int128))
+        self.assertEqual(parse('int', self.sym),
+                         ct.DataShape(ct.int_))
+        # 'int' is an alias for 'int32'
+        self.assertEqual(parse('int', self.sym),
+                         parse('int32', self.sym))
+        self.assertEqual(parse('intptr', self.sym),
+                         ct.DataShape(ct.intptr))
+
+    def test_unsigned_integers(self):
+        self.assertEqual(parse('uint8', self.sym),
+                         ct.DataShape(ct.uint8))
+        self.assertEqual(parse('uint16', self.sym),
+                         ct.DataShape(ct.uint16))
+        self.assertEqual(parse('uint32', self.sym),
+                         ct.DataShape(ct.uint32))
+        self.assertEqual(parse('uint64', self.sym),
+                         ct.DataShape(ct.uint64))
+        # self.assertEqual(parse('uint128', self.sym),
+        #                 ct.DataShape(ct.uint128))
+        self.assertEqual(parse('uintptr', self.sym),
+                         ct.DataShape(ct.uintptr))
+
+    def test_float(self):
+        self.assertEqual(parse('float16', self.sym),
+                         ct.DataShape(ct.float16))
+        self.assertEqual(parse('float32', self.sym),
+                         ct.DataShape(ct.float32))
+        self.assertEqual(parse('float64', self.sym),
+                         ct.DataShape(ct.float64))
+        # self.assertEqual(parse('float128', self.sym),
+        #                 ct.DataShape(ct.float128))
+        self.assertEqual(parse('real', self.sym),
+                         ct.DataShape(ct.real))
+        # 'real' is an alias for 'float64'
+        self.assertEqual(parse('real', self.sym),
+                         parse('float64', self.sym))
+
+    def test_null(self):
+        self.assertEqual(parse('null', self.sym), ct.DataShape(ct.null))
+
+    def test_void(self):
+        self.assertEqual(parse('void', self.sym), ct.DataShape(ct.void))
+
+    def test_object(self):
+        self.assertEqual(parse('object', self.sym), ct.DataShape(ct.object_))
+
+    def test_complex(self):
+        self.assertEqual(parse('complex[float32]', self.sym),
+                         ct.DataShape(ct.complex_float32))
+        self.assertEqual(parse('complex[float64]', self.sym),
+                         ct.DataShape(ct.complex_float64))
+        self.assertEqual(parse('complex', self.sym),
+                         ct.DataShape(ct.complex_))
+        # 'complex' is an alias for 'complex[float64]'
+        self.assertEqual(parse('complex', self.sym),
+                         parse('complex[float64]', self.sym))
+
+    def test_option(self):
+        self.assertEqual(parse('option[int32]', self.sym),
+                         ct.DataShape(ct.Option(ct.int32)))
+        self.assertEqual(parse('?int32', self.sym),
+                         ct.DataShape(ct.Option(ct.int32)))
+        self.assertEqual(parse('2 * 3 * option[int32]', self.sym),
+                         ct.DataShape(ct.Fixed(2), ct.Fixed(3),
+                                      ct.Option(ct.int32)))
+        self.assertEqual(parse('2 * 3 * ?int32', self.sym),
+                         ct.DataShape(ct.Fixed(2), ct.Fixed(3),
+                                      ct.Option(ct.int32)))
+        self.assertEqual(parse('2 * option[3 * int32]', self.sym),
+                         ct.DataShape(ct.Fixed(2),
+                                      ct.Option(ct.DataShape(ct.Fixed(3),
+                                                             ct.int32))))
+        self.assertEqual(parse('2 * ?3 * int32', self.sym),
+                         ct.DataShape(ct.Fixed(2),
+                                      ct.Option(ct.DataShape(ct.Fixed(3),
+                                                             ct.int32))))
+
+    def test_raise(self):
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse, '', self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse, 'boot', self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse, 'int33', self.sym)
+
+
+class TestDataShapeParserDTypeConstr(unittest.TestCase):
+
+    def test_unary_dtype_constr(self):
+        # Create a symbol table with no types in it, so we can
+        # make some isolated type constructors for testing
+        sym = datashape.TypeSymbolTable(bare=True)
+        # A limited set of dtypes for testing
+        sym.dtype['int8'] = ct.int8
+        sym.dtype['uint16'] = ct.uint16
+        sym.dtype['float64'] = ct.float64
+        # TypeVar type constructor
+        sym.dtype_constr['typevar'] = ct.TypeVar
+        # Unary dtype constructor that asserts on the argument value
+        expected_blah = [None]
+
+        def _unary_type_constr(blah):
+            self.assertEqual(blah, expected_blah[0])
+            expected_blah[0] = None
+            return ct.float32
+        sym.dtype_constr['unary'] = _unary_type_constr
+
+        def assertExpectedParse(ds_str, expected):
+            # Set the expected value, and call the parser
+            expected_blah[0] = expected
+            self.assertEqual(parse(ds_str, sym), ct.DataShape(ct.float32))
+            # Make sure the expected value was actually run by
+            # check that it reset the expected value to None
+            self.assertEqual(expected_blah[0], None,
+                             'The test unary type constructor did not run')
+
+        # Integer parameter (positional)
+        assertExpectedParse('unary[0]', 0)
+        assertExpectedParse('unary[100000]', 100000)
+        # String parameter (positional)
+        assertExpectedParse('unary["test"]', 'test')
+        assertExpectedParse("unary['test']", 'test')
+        assertExpectedParse('unary["\\uc548\\ub155"]', u'\uc548\ub155')
+        assertExpectedParse(u'unary["\uc548\ub155"]', u'\uc548\ub155')
+        # DataShape parameter (positional)
+        assertExpectedParse('unary[int8]', ct.DataShape(ct.int8))
+        assertExpectedParse('unary[X]', ct.DataShape(ct.TypeVar('X')))
+        # Empty list parameter (positional)
+        assertExpectedParse('unary[[]]', [])
+        # List of integers parameter (positional)
+        assertExpectedParse('unary[[0, 3, 12]]', [0, 3, 12])
+        # List of strings parameter (positional)
+        assertExpectedParse('unary[["test", "one", "two"]]',
+                            ["test", "one", "two"])
+        # List of datashapes parameter (positional)
+        assertExpectedParse('unary[[float64, int8, uint16]]',
+                            [ct.DataShape(ct.float64), ct.DataShape(ct.int8),
+                             ct.DataShape(ct.uint16)])
+
+        # Integer parameter (keyword)
+        assertExpectedParse('unary[blah=0]', 0)
+        assertExpectedParse('unary[blah=100000]', 100000)
+        # String parameter (keyword)
+        assertExpectedParse('unary[blah="test"]', 'test')
+        assertExpectedParse("unary[blah='test']", 'test')
+        assertExpectedParse('unary[blah="\\uc548\\ub155"]', u'\uc548\ub155')
+        assertExpectedParse(u'unary[blah="\uc548\ub155"]', u'\uc548\ub155')
+        # DataShape parameter (keyword)
+        assertExpectedParse('unary[blah=int8]', ct.DataShape(ct.int8))
+        assertExpectedParse('unary[blah=X]', ct.DataShape(ct.TypeVar('X')))
+        # Empty list parameter (keyword)
+        assertExpectedParse('unary[blah=[]]', [])
+        # List of integers parameter (keyword)
+        assertExpectedParse('unary[blah=[0, 3, 12]]', [0, 3, 12])
+        # List of strings parameter (keyword)
+        assertExpectedParse('unary[blah=["test", "one", "two"]]',
+                            ["test", "one", "two"])
+        # List of datashapes parameter (keyword)
+        assertExpectedParse('unary[blah=[float64, int8, uint16]]',
+                            [ct.DataShape(ct.float64), ct.DataShape(ct.int8),
+                             ct.DataShape(ct.uint16)])
+
+    def test_binary_dtype_constr(self):
+        # Create a symbol table with no types in it, so we can
+        # make some isolated type constructors for testing
+        sym = datashape.TypeSymbolTable(bare=True)
+        # A limited set of dtypes for testing
+        sym.dtype['int8'] = ct.int8
+        sym.dtype['uint16'] = ct.uint16
+        sym.dtype['float64'] = ct.float64
+        # TypeVar type constructor
+        sym.dtype_constr['typevar'] = ct.TypeVar
+        # Binary dtype constructor that asserts on the argument values
+        expected_arg = [None, None]
+
+        def _binary_type_constr(a, b):
+            self.assertEqual(a, expected_arg[0])
+            self.assertEqual(b, expected_arg[1])
+            expected_arg[0] = None
+            expected_arg[1] = None
+            return ct.float32
+        sym.dtype_constr['binary'] = _binary_type_constr
+
+        def assertExpectedParse(ds_str, expected_a, expected_b):
+            # Set the expected value, and call the parser
+            expected_arg[0] = expected_a
+            expected_arg[1] = expected_b
+            self.assertEqual(parse(ds_str, sym), ct.DataShape(ct.float32))
+            # Make sure the expected value was actually run by
+            # check that it reset the expected value to None
+            self.assertEqual(expected_arg, [None, None],
+                             'The test binary type constructor did not run')
+
+        # Positional args
+        assertExpectedParse('binary[1, 0]', 1, 0)
+        assertExpectedParse('binary[0, "test"]', 0, 'test')
+        assertExpectedParse('binary[int8, "test"]',
+                            ct.DataShape(ct.int8), 'test')
+        assertExpectedParse('binary[[1,3,5], "test"]', [1, 3, 5], 'test')
+        # Positional and keyword args
+        assertExpectedParse('binary[0, b=1]', 0, 1)
+        assertExpectedParse('binary["test", b=A]', 'test',
+                            ct.DataShape(ct.TypeVar('A')))
+        assertExpectedParse('binary[[3, 6], b=int8]', [3, 6],
+                            ct.DataShape(ct.int8))
+        assertExpectedParse('binary[Arg, b=["x", "test"]]',
+                            ct.DataShape(ct.TypeVar('Arg')), ['x', 'test'])
+        # Keyword args
+        assertExpectedParse('binary[a=1, b=0]', 1, 0)
+        assertExpectedParse('binary[a=[int8, A, uint16], b="x"]',
+                            [ct.DataShape(ct.int8),
+                             ct.DataShape(ct.TypeVar('A')),
+                             ct.DataShape(ct.uint16)],
+                            'x')
+
+    def test_dtype_constr_errors(self):
+        # Create a symbol table with no types in it, so we can
+        # make some isolated type constructors for testing
+        sym = datashape.TypeSymbolTable(bare=True)
+        # A limited set of dtypes for testing
+        sym.dtype['int8'] = ct.int8
+        sym.dtype['uint16'] = ct.uint16
+        sym.dtype['float64'] = ct.float64
+        # Arbitrary dtype constructor that does nothing
+
+        def _type_constr(*args, **kwargs):
+            return ct.float32
+        sym.dtype_constr['tcon'] = _type_constr
+
+        # Require closing "]"
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[', sym)
+        # Type constructors should always have an argument
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[]', sym)
+        # Unknown type
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[unknown]', sym)
+        # Missing parameter value
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[x=', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[x=]', sym)
+        # A positional arg cannot be after a keyword arg
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[x=A, B]', sym)
+        # List args must be homogeneous
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[[0, "x"]]', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[[0, X]]', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[["x", 0]]', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[["x", X]]', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[[X, 0]]', sym)
+        self.assertRaises(DataShapeSyntaxError,
+                          parse, 'tcon[[X, "x"]]', sym)
+
+
+class TestDataShapeParserDims(unittest.TestCase):
+
+    def setUp(self):
+        # Create a default symbol table for the parser to use
+        self.sym = datashape.TypeSymbolTable()
+
+    def test_fixed_dims(self):
+        self.assertEqual(parse('3 * bool', self.sym),
+                         ct.DataShape(ct.Fixed(3), ct.bool_))
+        self.assertEqual(parse('7 * 3 * bool', self.sym),
+                         ct.DataShape(ct.Fixed(7), ct.Fixed(3), ct.bool_))
+        self.assertEqual(parse('5 * 3 * 12 * bool', self.sym),
+                         ct.DataShape(ct.Fixed(5), ct.Fixed(3),
+                                      ct.Fixed(12), ct.bool_))
+        self.assertEqual(parse('2 * 3 * 4 * 5 * bool', self.sym),
+                         ct.DataShape(ct.Fixed(2), ct.Fixed(3),
+                                      ct.Fixed(4), ct.Fixed(5), ct.bool_))
+
+    def test_typevar_dims(self):
+        self.assertEqual(parse('M * bool', self.sym),
+                         ct.DataShape(ct.TypeVar('M'), ct.bool_))
+        self.assertEqual(parse('A * B * bool', self.sym),
+                         ct.DataShape(ct.TypeVar('A'), ct.TypeVar('B'), ct.bool_))
+        self.assertEqual(parse('A... * X * 3 * bool', self.sym),
+                         ct.DataShape(ct.Ellipsis(ct.TypeVar('A')), ct.TypeVar('X'),
+                                      ct.Fixed(3), ct.bool_))
+
+    def test_var_dims(self):
+        self.assertEqual(parse('var * bool', self.sym),
+                         ct.DataShape(ct.Var(), ct.bool_))
+        self.assertEqual(parse('var * var * bool', self.sym),
+                         ct.DataShape(ct.Var(), ct.Var(), ct.bool_))
+        self.assertEqual(parse('M * 5 * var * bool', self.sym),
+                         ct.DataShape(ct.TypeVar('M'), ct.Fixed(5), ct.Var(), ct.bool_))
+
+    def test_ellipses(self):
+        self.assertEqual(parse('... * bool', self.sym),
+                         ct.DataShape(ct.Ellipsis(), ct.bool_))
+        self.assertEqual(parse('M * ... * bool', self.sym),
+                         ct.DataShape(ct.TypeVar('M'), ct.Ellipsis(), ct.bool_))
+        self.assertEqual(parse('M * ... * 3 * bool', self.sym),
+                         ct.DataShape(ct.TypeVar('M'), ct.Ellipsis(),
+                                      ct.Fixed(3), ct.bool_))
+
+
+class TestDataShapeParseStruct(unittest.TestCase):
+
+    def setUp(self):
+        # Create a default symbol table for the parser to use
+        self.sym = datashape.TypeSymbolTable()
+
+    def test_struct(self):
+        # Simple struct
+        self.assertEqual(parse('{x: int16, y: int32}', self.sym),
+                         ct.DataShape(ct.Record([('x', ct.DataShape(ct.int16)),
+                                                 ('y', ct.DataShape(ct.int32))])))
+        # A trailing comma is ok
+        self.assertEqual(parse('{x: int16, y: int32,}', self.sym),
+                         ct.DataShape(ct.Record([('x', ct.DataShape(ct.int16)),
+                                                 ('y', ct.DataShape(ct.int32))])))
+        # Field names starting with _ and caps
+        self.assertEqual(parse('{_x: int16, Zed: int32,}', self.sym),
+                         ct.DataShape(ct.Record([('_x', ct.DataShape(ct.int16)),
+                                                 ('Zed', ct.DataShape(ct.int32))])))
+        # A slightly bigger example
+        ds_str = """3 * var * {
+                        id : int32,
+                        name : string,
+                        description : {
+                            language : string,
+                            text : string
+                        },
+                        entries : var * {
+                            date : date,
+                            text : string
+                        }
+                    }"""
+        int32 = ct.DataShape(ct.int32)
+        string = ct.DataShape(ct.string)
+        date = ct.DataShape(ct.date_)
+        ds = (ct.Fixed(3), ct.Var(),
+              ct.Record([('id', int32),
+                         ('name', string),
+                         ('description', ct.DataShape(ct.Record([('language', string),
+                                                                 ('text', string)]))),
+                         ('entries', ct.DataShape(ct.Var(),
+                                                  ct.Record([('date', date),
+                                                             ('text', string)])))]))
+        self.assertEqual(parse(ds_str, self.sym), ct.DataShape(*ds))
+
+    def test_fields_with_dshape_names(self):
+        # Should be able to name a field 'type', 'int64', etc
+        ds = parse("""{
+                type: bool,
+                data: bool,
+                blob: bool,
+                bool: bool,
+                int: int32,
+                float: float32,
+                double: float64,
+                int8: int8,
+                int16: int16,
+                int32: int32,
+                int64: int64,
+                uint8: uint8,
+                uint16: uint16,
+                uint32: uint32,
+                uint64: uint64,
+                float16: float32,
+                float32: float32,
+                float64: float64,
+                float128: float64,
+                complex: float32,
+                complex64: float32,
+                complex128: float64,
+                string: string,
+                object: string,
+                datetime: string,
+                datetime64: string,
+                timedelta: string,
+                timedelta64: string,
+                json: string,
+                var: string,
+            }""", self.sym)
+        self.assertEqual(type(ds[-1]), ct.Record)
+        self.assertEqual(len(ds[-1].names), 30)
+
+    def test_kiva_datashape(self):
+        # A slightly more complicated datashape which should parse
+        ds = parse("""5 * var * {
+              id: int64,
+              name: string,
+              description: {
+                languages: var * string[2],
+                texts: json,
+              },
+              status: string,
+              funded_amount: float64,
+              basket_amount: json,
+              paid_amount: json,
+              image: {
+                id: int64,
+                template_id: int64,
+              },
+              video: json,
+              activity: string,
+              sector: string,
+              use: string,
+              delinquent: bool,
+              location: {
+                country_code: string[2],
+                country: string,
+                town: json,
+                geo: {
+                  level: string,
+                  pairs: string,
+                  type: string,
+                },
+              },
+              partner_id: int64,
+              posted_date: json,
+              planned_expiration_date: json,
+              loan_amount: float64,
+              currency_exchange_loss_amount: json,
+              borrowers: var * {
+                first_name: string,
+                last_name: string,
+                gender: string[1],
+                pictured: bool,
+              },
+              terms: {
+                disbursal_date: json,
+                disbursal_currency: string[3,'A'],
+                disbursal_amount: float64,
+                loan_amount: float64,
+                local_payments: var * {
+                  due_date: json,
+                  amount: float64,
+                },
+                scheduled_payments: var * {
+                  due_date: json,
+                  amount: float64,
+                },
+                loss_liability: {
+                  nonpayment: string,
+                  currency_exchange: string,
+                  currency_exchange_coverage_rate: json,
+                },
+              },
+              payments: var * {
+                amount: float64,
+                local_amount: float64,
+                processed_date: json,
+                settlement_date: json,
+                rounded_local_amount: float64,
+                currency_exchange_loss_amount: float64,
+                payment_id: int64,
+                comment: json,
+              },
+              funded_date: json,
+              paid_date: json,
+              journal_totals: {
+                entries: int64,
+                bulkEntries: int64,
+              },
+            }
+        """, self.sym)
+        self.assertEqual(type(ds[-1]), ct.Record)
+        self.assertEqual(len(ds[-1].names), 25)
+
+    def test_strings_in_ds(self):
+        # Name the fields with some arbitrary string!
+        ds = parse("""5 * var * {
+              id: int64,
+             'my field': string,
+              name: string }
+             """, self.sym)
+        self.assertEqual(len(ds[-1].names), 3)
+        ds = parse("""2 * var * {
+             "AASD @#$@#$ \' sdf": string,
+              id: float32,
+              id2: int64,
+              name: string }
+             """, self.sym)
+        self.assertEqual(len(ds[-1].names), 4)
+
+    def test_struct_errors(self):
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          '{id: int64, name: string amount: invalidtype}',
+                          self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          '{id: int64, name: string, amount: invalidtype}',
+                          self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          '{id: int64, name: string, amount: %}',
+                          self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          "{\n" +
+                          "   id: int64;\n" +
+                          "   name: string;\n" +
+                          "   amount+ float32;\n" +
+                          "}\n",
+                          self.sym)
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          "{\n" +
+                          "   id: int64;\n" +
+                          "   'my field 1': string;\n" +
+                          "   amount+ float32;\n" +
+                          "}\n",
+                          self.sym)
+        # Don't accept explicitly Unicode string literals
+        self.assertRaises(datashape.DataShapeSyntaxError,
+                          parse,
+                          "{\n" +
+                          "   id: int64,\n" +
+                          "   u'my field 1': string,\n" +
+                          "   amount: float32\n" +
+                          "}\n",
+                          self.sym)
+
+
+class TestDataShapeParseTuple(unittest.TestCase):
+
+    def setUp(self):
+        # Create a default symbol table for the parser to use
+        self.sym = datashape.TypeSymbolTable()
+
+    def test_tuple(self):
+        # Simple tuple
+        self.assertEqual(parse('(float32)', self.sym),
+                         ct.DataShape(ct.Tuple([ct.DataShape(ct.float32)])))
+        self.assertEqual(parse('(int16, int32)', self.sym),
+                         ct.DataShape(ct.Tuple([ct.DataShape(ct.int16),
+                                                ct.DataShape(ct.int32)])))
+        # A trailing comma is ok
+        self.assertEqual(parse('(float32,)', self.sym),
+                         ct.DataShape(ct.Tuple([ct.DataShape(ct.float32)])))
+        self.assertEqual(parse('(int16, int32,)', self.sym),
+                         ct.DataShape(ct.Tuple([ct.DataShape(ct.int16),
+                                                ct.DataShape(ct.int32)])))
+
+
+def test_funcproto(sym):
+    # Simple funcproto
+    assert (parse('(float32) -> float64', sym) ==
+            ct.DataShape(ct.Function(ct.DataShape(ct.float32),
+                                     ct.DataShape(ct.float64))))
+    assert (parse('(int16, int32) -> bool', sym) ==
+            ct.DataShape(ct.Function(ct.DataShape(ct.int16),
+                                     ct.DataShape(ct.int32),
+                                     ct.DataShape(ct.bool_))))
+    # A trailing comma is ok
+    assert (parse('(float32,) -> float64', sym) ==
+            ct.DataShape(ct.Function(ct.DataShape(ct.float32),
+                                     ct.DataShape(ct.float64))))
+    assert_dshape_equal(
+        parse('(int16, int32,) -> bool', sym),
+        ct.DataShape(ct.Function(
+            ct.DataShape(ct.int16),
+            ct.DataShape(ct.int32),
+            ct.DataShape(ct.bool_)
+        ))
+    )
+
+    # Empty argument signature.
+    assert_dshape_equal(
+        parse('() -> bool', sym),
+        ct.DataShape(ct.Function(
+            ct.DataShape(ct.bool_),
+        ))
+    )
+
+
+def test_funcproto_no_return_type(sym):
+    with pytest.raises(DataShapeSyntaxError):
+        parse('(int64, int32) ->', sym)
+
+
+def test_empty_tuple(sym):
+    t = parse('()', sym)
+    assert isinstance(t, ct.DataShape)
+    assert isinstance(t.measure, ct.Tuple)
+    assert t.measure.dshapes == ()
+
+
+def test_no_right_paren_tuple(sym):
+    with pytest.raises(DataShapeSyntaxError):
+        parse('(int64', sym)
+
+
+def test_garbage_at_end(sym):
+    with pytest.raises(DataShapeSyntaxError):
+        parse('int64,asdf', sym)
+
+
+def test_type_constructor_fail(sym):
+    with pytest.raises(DataShapeSyntaxError):
+        parse('string[10,[', sym)
+
+    with pytest.raises(DataShapeSyntaxError):
+        parse('string[10,', sym)
+
+
+def test_dim_constructor_fail(sym):
+    with pytest.raises(NotImplementedError):
+        parse('fixed[10] * var * string', sym)
+    with pytest.raises(DataShapeSyntaxError):
+        parse('fixed[10 * var * string', sym)
+
+
+def test_invalid_dtype(sym):
+    with pytest.raises(DataShapeSyntaxError):
+        parse('10 * foo[10]', sym)
diff --git a/datashader/datashape/tests/test_predicates.py b/datashader/datashape/tests/test_predicates.py
new file mode 100644
index 000000000..93ec7f033
--- /dev/null
+++ b/datashader/datashape/tests/test_predicates.py
@@ -0,0 +1,23 @@
+from datashader.datashape.predicates import isfixed, _dimensions, isnumeric, isscalar
+from datashader.datashape.coretypes import TypeVar, int32, Categorical
+
+
+def test_isfixed():
+    assert not isfixed(TypeVar('M') * int32)
+
+
+def test_isscalar():
+    assert isscalar('?int32')
+    assert isscalar('float32')
+    assert isscalar(int32)
+    assert isscalar(Categorical(['a', 'b', 'c']))
+    assert not isscalar('{a: int32, b: float64}')
+
+
+def test_option():
+    assert _dimensions('?int') == _dimensions('int')
+    assert _dimensions('3 * ?int') == _dimensions('3 * int')
+
+
+def test_time():
+    assert not isnumeric('time')
diff --git a/datashader/datashape/tests/test_promote.py b/datashader/datashape/tests/test_promote.py
new file mode 100644
index 000000000..9d619ee2c
--- /dev/null
+++ b/datashader/datashape/tests/test_promote.py
@@ -0,0 +1,131 @@
+import pytest
+
+from datashader.datashape import (
+    promote, Option, float64, int64, float32, optionify,
+    string, datetime_ as datetime, dshape)
+
+
+def test_simple():
+    x = int64
+    y = float32
+    z = promote(x, y)
+    assert z == float64
+
+
+def test_option():
+    x = int64
+    y = Option(float32)
+    z = promote(x, y)
+    assert z == Option(float64)
+
+
+def test_no_promote_option():
+    x = int64
+    y = Option(float64)
+    z = promote(x, y, promote_option=False)
+    assert z == float64
+
+
+def test_option_in_parent():
+    x = int64
+    y = Option(float32)
+    z = optionify(x, y, y)
+    assert z == y
+
+
+@pytest.mark.parametrize('x,y,p,r',
+                         [[string, string, True, string],
+                          [string, string, False, string],
+
+                          [Option(string),
+                           Option(string),
+                           True,
+                           Option(string)],
+
+                          [Option(string),
+                           Option(string),
+                           False,
+                           Option(string)],
+
+                          [Option(string),
+                           string,
+                           True,
+                           Option(string)],
+
+                          [Option(string),
+                           string,
+                           False,
+                           string],
+
+                          [Option(string),
+                           dshape('?string'),
+                           True,
+                           Option(string)],
+
+                          [dshape('?string'),
+                           Option(string),
+                           False,
+                           Option(string)],
+
+                          [dshape('string'),
+                           Option(string),
+                           True,
+                           Option(string)],
+
+                          [dshape('string'),
+                           Option(string),
+                           False,
+                           string]])
+def test_promote_string_with_option(x, y, p, r):
+    assert (promote(x, y, promote_option=p) ==
+            promote(y, x, promote_option=p) ==
+            r)
+
+
+@pytest.mark.parametrize('x,y,p,r',
+                         [[datetime, datetime, True, datetime],
+                          [datetime, datetime, False, datetime],
+
+                          [Option(datetime),
+                           Option(datetime),
+                           True,
+                           Option(datetime)],
+
+                          [Option(datetime),
+                           Option(datetime),
+                           False,
+                           Option(datetime)],
+
+                          [Option(datetime),
+                           datetime,
+                           True,
+                           Option(datetime)],
+
+                          [Option(datetime),
+                           datetime,
+                           False,
+                           datetime],
+
+                          [Option(datetime),
+                           dshape('?datetime'),
+                           True,
+                           Option(datetime)],
+
+                          [dshape('?datetime'),
+                           Option(datetime),
+                           False,
+                           Option(datetime)],
+
+                          [dshape('datetime'),
+                           Option(datetime),
+                           True,
+                           Option(datetime)],
+
+                          [dshape('datetime'),
+                           Option(datetime),
+                           False,
+                           datetime]])
+def test_promote_datetime_with_option(x, y, p, r):
+    assert (promote(x, y, promote_option=p) ==
+            promote(y, x, promote_option=p) ==
+            r)
diff --git a/datashader/datashape/tests/test_str.py b/datashader/datashape/tests/test_str.py
new file mode 100644
index 000000000..d6aef8b6f
--- /dev/null
+++ b/datashader/datashape/tests/test_str.py
@@ -0,0 +1,74 @@
+import unittest
+import pytest
+
+from datashader import datashape
+from datashader.datashape import dshape, DataShapeSyntaxError
+
+
+class TestDataShapeStr(unittest.TestCase):
+    def test_primitive_measure_str(self):
+        self.assertEqual(str(datashape.int8), 'int8')
+        self.assertEqual(str(datashape.int16), 'int16')
+        self.assertEqual(str(datashape.int32), 'int32')
+        self.assertEqual(str(datashape.int64), 'int64')
+        self.assertEqual(str(datashape.uint8), 'uint8')
+        self.assertEqual(str(datashape.uint16), 'uint16')
+        self.assertEqual(str(datashape.uint32), 'uint32')
+        self.assertEqual(str(datashape.uint64), 'uint64')
+        self.assertEqual(str(datashape.float32), 'float32')
+        self.assertEqual(str(datashape.float64), 'float64')
+        self.assertEqual(str(datashape.string), 'string')
+        self.assertEqual(str(datashape.String(3)), 'string[3]')
+        self.assertEqual(str(datashape.String('A')), "string['A']")
+
+    def test_structure_str(self):
+        self.assertEqual(str(dshape('{x:int32, y:int64}')),
+                         '{x: int32, y: int64}')
+
+    def test_array_str(self):
+        self.assertEqual(str(dshape('3*5*int16')),
+                         '3 * 5 * int16')
+
+    def test_primitive_measure_repr(self):
+        self.assertEqual(repr(datashape.int8),      'ctype("int8")')
+        self.assertEqual(repr(datashape.int16),     'ctype("int16")')
+        self.assertEqual(repr(datashape.int32),     'ctype("int32")')
+        self.assertEqual(repr(datashape.int64),     'ctype("int64")')
+        self.assertEqual(repr(datashape.uint8),     'ctype("uint8")')
+        self.assertEqual(repr(datashape.uint16),    'ctype("uint16")')
+        self.assertEqual(repr(datashape.uint32),    'ctype("uint32")')
+        self.assertEqual(repr(datashape.uint64),    'ctype("uint64")')
+        self.assertEqual(repr(datashape.float32),   'ctype("float32")')
+        self.assertEqual(repr(datashape.float64),   'ctype("float64")')
+        self.assertEqual(repr(datashape.string),    'ctype("string")')
+        self.assertEqual(repr(datashape.String(3)), 'ctype("string[3]")')
+        self.assertEqual(repr(datashape.String('A')),
+                         """ctype("string['A']")""")
+
+    def test_structure_repr(self):
+        self.assertEqual(repr(dshape('{x:int32, y:int64}')),
+                         'dshape("{x: int32, y: int64}")')
+
+    def test_array_repr(self):
+        self.assertEqual(repr(dshape('3*5*int16')),
+                         'dshape("3 * 5 * int16")')
+
+
+@pytest.mark.parametrize('s',
+                         ['{"./abc": int64}',
+                          '{"./a b c": float64}',
+                          '{"./a b\tc": string}',
+                          '{"./a/[0 1 2]/b/\\n": float32}'])
+def test_arbitrary_string(s):
+    ds = dshape(s)
+    assert dshape(str(ds)) == ds
+
+
+@pytest.mark.parametrize('s',
+                         ['{"/a/b/0/c\v/d": int8}',
+                          '{"/a/b/0/c\n/d": int8}',
+                          '{"/a/b/0/c\r/d": int8}'])
+def test_arbitrary_string2(s):
+    with pytest.raises(DataShapeSyntaxError):
+        ds = dshape(s)
+        _ = dshape(str(ds))
diff --git a/datashader/datashape/tests/test_typeset.py b/datashader/datashape/tests/test_typeset.py
new file mode 100644
index 000000000..9f5562e93
--- /dev/null
+++ b/datashader/datashape/tests/test_typeset.py
@@ -0,0 +1,33 @@
+from datashader import datashape
+import pytest
+
+
+def test_equal():
+    assert datashape.integral == datashape.integral
+    assert datashape.floating != datashape.integral
+
+
+def test_repr():
+    assert repr(datashape.integral) == '{integral}'
+
+
+def test_custom_typeset_repr():
+    mytypeset = datashape.TypeSet(datashape.int64, datashape.float64)
+    assert repr(mytypeset).startswith('TypeSet(')
+    assert repr(mytypeset).endswith('name=None)')
+
+
+def test_register_already_existing_typeset_fails():
+    mytypeset = datashape.TypeSet(datashape.int64, datashape.float64,
+                                  name='foo')
+    with pytest.raises(TypeError):
+        datashape.typesets.register_typeset('foo', mytypeset)
+
+
+def test_getitem():
+    assert datashape.typesets.registry['integral'] == datashape.integral
+
+
+def test_getitem_non_existent_typeset():
+    with pytest.raises(KeyError):
+        datashape.typesets.registry['footypeset']
diff --git a/datashader/datashape/tests/test_user.py b/datashader/datashape/tests/test_user.py
new file mode 100644
index 000000000..39136bd05
--- /dev/null
+++ b/datashader/datashape/tests/test_user.py
@@ -0,0 +1,79 @@
+import pytest
+
+from datashader.datashape.user import issubschema, validate
+from datashader.datashape import dshape
+from datetime import date, time, datetime
+import numpy as np
+
+
+min_np = pytest.mark.skipif(
+    np.__version__ > '1.14',
+    reason="issubdtype no longer downcasts"
+)
+
+
+@min_np
+def test_validate():
+    assert validate(int, 1)
+    assert validate('int', 1)
+    assert validate(str, 'Alice')
+    assert validate(dshape('string'), 'Alice')
+    assert validate(dshape('int'), 1)
+    assert validate(dshape('int')[0], 1)
+    assert validate('real', 2.0)
+    assert validate('2 * int', (1, 2))
+    assert not validate('3 * int', (1, 2))
+    assert not validate('2 * int', 2)
+
+
+@min_np
+def test_nested_iteratables():
+    assert validate('2 * 3 * int', [(1, 2, 3), (4, 5, 6)])
+
+
+def test_numeric_tower():
+    assert validate(np.integer, np.int32(1))
+    assert validate(np.number, np.int32(1))
+
+
+@min_np
+def test_validate_dicts():
+    assert validate('{x: int, y: int}', {'x': 1, 'y': 2})
+    assert not validate('{x: int, y: int}', {'x': 1, 'y': 2.0})
+    assert not validate('{x: int, y: int}', {'x': 1, 'z': 2})
+
+    assert validate('var * {x: int, y: int}', [{'x': 1, 'y': 2}])
+
+    assert validate('var * {x: int, y: int}', [{'x': 1, 'y': 2},
+                                               {'x': 3, 'y': 4}])
+
+
+@min_np
+def test_tuples_can_be_records_too():
+    assert validate('{x: int, y: real}', (1, 2.0))
+    assert not validate('{x: int, y: real}', (1.0, 2))
+
+
+def test_datetimes():
+    assert validate('time', time(12, 0, 0))
+    assert validate('date', date(1999, 1, 20))
+    assert validate('datetime', datetime(1999, 1, 20, 12, 0, 0))
+
+
+def test_numpy():
+    assert validate('2 * int32', np.array([1, 2], dtype='int32'))
+
+
+def test_issubschema():
+    assert issubschema('int', 'int')
+    assert not issubschema('int', 'float32')
+
+    assert issubschema('2 * int', '2 * int')
+    assert not issubschema('2 * int', '3 * int')
+
+    # assert issubschema('float32', 'real')
+
+
+def test_integration():
+    assert validate('{name: string, arrived: date}',
+                    {'name': 'Alice', 'arrived': date(2012, 1, 5)})
diff --git a/datashader/datashape/tests/test_util.py b/datashader/datashape/tests/test_util.py
new file mode 100644
index 000000000..a3b901f63
--- /dev/null
+++ b/datashader/datashape/tests/test_util.py
@@ -0,0 +1,72 @@
+import pytest
+
+from datashader import datashape
+from datashader.datashape import dshape, has_var_dim, has_ellipsis
+
+
+def test_cat_dshapes():
+    # concatenating 1 dshape is a no-op
+    dslist = [dshape('3 * 10 * int32')]
+    assert datashape.cat_dshapes(dslist) == dslist[0]
+    # two dshapes
+    dslist = [dshape('3 * 10 * int32'),
+              dshape('7 * 10 * int32')]
+    assert datashape.cat_dshapes(dslist) == dshape('10 * 10 * int32')
+
+
+def test_cat_dshapes_errors():
+    # need at least one dshape
+    with pytest.raises(ValueError):
+        datashape.cat_dshapes([])
+
+    # dshapes need to match after the first dimension
+    with pytest.raises(ValueError):
+        datashape.cat_dshapes([dshape('3 * 10 * int32'),
+                              dshape('3 * 1 * int32')])
+
+
+@pytest.mark.parametrize('ds_pos',
+                         ["... * float32",
+                          "A... * float32",
+                          "var * float32",
+                          "10 * { f0: int32, f1: A... * float32 }",
+                          "{ f0 : { g0 : var * int }, f1: int32 }",
+                          (dshape("var * int32"),)])
+def test_has_var_dim(ds_pos):
+    assert has_var_dim(dshape(ds_pos))
+
+
+@pytest.mark.parametrize('ds_neg',
+                         [dshape("float32"),
+                          dshape("10 * float32"),
+                          dshape("10 * { f0: int32, f1: 10 * float32 }"),
+                          dshape("{ f0 : { g0 : 2 * int }, f1: int32 }"),
+                          (dshape("int32"),)])
+def test_not_has_var_dim(ds_neg):
+    assert not has_var_dim(ds_neg)
+
+
+@pytest.mark.parametrize('ds',
+                         [dshape("... * float32"),
+                          dshape("A... * float32"),
+                          dshape("var * ... * float32"),
+                          dshape("(int32, M... * int16) -> var * int8"),
+                          dshape("(int32, var * int16) -> ... * int8"),
+                          dshape("10 * { f0: int32, f1: A... * float32 }"),
+                          dshape("{ f0 : { g0 : ... * int }, f1: int32 }"),
+                          (dshape("... * int32"),)])
+def test_has_ellipsis(ds):
+    assert has_ellipsis(ds)
+
+
+@pytest.mark.parametrize('ds',
+                         [dshape("float32"),
+                          dshape("10 * var * float32"),
+                          dshape("M * float32"),
+                          dshape("(int32, M * int16) -> var * int8"),
+                          dshape("(int32, int16) -> var * int8"),
+                          dshape("10 * { f0: int32, f1: 10 * float32 }"),
+                          dshape("{ f0 : { g0 : 2 * int }, f1: int32 }"),
+                          (dshape("M * int32"),)])
+def test_not_has_ellipsis(ds):
+    assert not has_ellipsis(ds)
diff --git a/datashader/datashape/util/testing.py b/datashader/datashape/util/testing.py
new file mode 100644
index 000000000..c60e8c9cb
--- /dev/null
+++ b/datashader/datashape/util/testing.py
@@ -0,0 +1,262 @@
+from abc import ABC
+
+from ..coretypes import (
+    DataShape,
+    DateTime,
+    Function,
+    Option,
+    Record,
+    String,
+    Time,
+    TimeDelta,
+    Tuple,
+    Units,
+)
+from ..dispatch import dispatch
+
+
+def _fmt_path(path):
+    """Format the path for final display.
+
+    Parameters
+    ----------
+    path : iterable of str
+        The path to the values that are not equal.
+
+    Returns
+    -------
+    fmtd : str
+        The formatted path to put into the error message.
+    """
+    if not path:
+        return ''
+    return 'path: _' + ''.join(path)
+
+
+@dispatch(DataShape, DataShape)
+def assert_dshape_equal(a, b, check_dim=True, path=None, **kwargs):
+    """Assert that two dshapes are equal, providing an informative error
+    message when they are not equal.
+
+    Parameters
+    ----------
+    a, b : dshape
+        The dshapes to check for equality.
+    check_dim : bool, optional
+        Check shapes for equality with respect to their dimensions.
+        default: True
+    check_tz : bool, optional
+        Checks times and datetimes for equality with respect to timezones.
+        default: True
+    check_timedelta_unit : bool, optional
+        Checks timedeltas for equality with respect to their unit (us, ns, ...).
+        default: True
+    check_str_encoding : bool, optional
+        Checks strings for equality with respect to their encoding.
+        default: True
+    check_str_fixlen : bool, optional
+        Checks string for equality with respect to their fixlen.
+        default: True
+    check_record_order : bool, optional
+        Checks records for equality with respect to the order of the fields.
+        default: True
+
+    Raises
+    ------
+    AssertionError
+        Raised when the two dshapes are not equal.
+    """
+    ashape = a.shape
+    bshape = b.shape
+
+    if path is None:
+        path = ()
+
+    if check_dim:
+        for n, (adim, bdim) in enumerate(zip(ashape, bshape)):
+            if adim != bdim:
+                path += '.shape[%d]' % n,
+                raise AssertionError(
+                    'dimensions do not match: %s != %s%s\n%s' % (
+                        adim,
+                        bdim,
+                        ('\n%s != %s' % (
+                            ' * '.join(map(str, ashape)),
+                            ' * '.join(map(str, bshape)),
+                        )) if len(a.shape) > 1 else '',
+                        _fmt_path(path),
+                    ),
+                )
+
+    path += '.measure',
+    assert_dshape_equal(
+        a.measure,
+        b.measure,
+        check_dim=check_dim,
+        path=path,
+        **kwargs
+    )
+
+
+class Slotted(ABC):
+    @classmethod
+    def __subclasshook__(cls, subcls):
+        return hasattr(subcls, '__slots__')
+
+
+@assert_dshape_equal.register(Slotted, Slotted)
+def _check_slots(a, b, path=None, **kwargs):
+    if type(a) != type(b):
+        return _base_case(a, b, path=path, **kwargs)
+
+    assert a.__slots__ == b.__slots__, 'slots mismatch: %r != %r\n%s' % (
+        a.__slots__, b.__slots__, _fmt_path(path),
+    )
+    if path is None:
+        path = ()
+    for slot in a.__slots__:
+        assert getattr(a, slot) == getattr(b, slot), \
+            "%s %ss do not match: %r != %r\n%s" % (
+                type(a).__name__.lower(),
+                slot,
+                getattr(a, slot),
+                getattr(b, slot),
+                _fmt_path(path + ('.' + slot,)),
+            )
+
+
+@assert_dshape_equal.register(object, object)
+def _base_case(a, b, path=None, **kwargs):
+    assert a == b, '%s != %s\n%s' % (a, b, _fmt_path(path))
+
+
+@dispatch((DateTime, Time), (DateTime, Time))
+def assert_dshape_equal(a, b, path=None, check_tz=True, **kwargs):
+    if type(a) != type(b):
+        return _base_case(a, b)
+    if check_tz:
+        _check_slots(a, b, path)
+
+
+@dispatch(TimeDelta, TimeDelta)
+def assert_dshape_equal(a, b, path=None, check_timedelta_unit=True, **kwargs):
+    if check_timedelta_unit:
+        _check_slots(a, b, path)
+
+
+@dispatch(Units, Units)
+def assert_dshape_equal(a, b, path=None, **kwargs):
+    if path is None:
+        path = ()
+
+    assert a.unit == b.unit, '%s units do not match: %r != %s\n%s' % (
+        type(a).__name__.lower(), a.unit, b.unit, _fmt_path(path + ('.unit',)),
+    )
+
+    path.append('.tp')
+    assert_dshape_equal(a.tp, b.tp, **kwargs)
+
+
+@dispatch(String, String)
+def assert_dshape_equal(a,
+                        b,
+                        path=None,
+                        check_str_encoding=True,
+                        check_str_fixlen=True,
+                        **kwargs):
+    if path is None:
+        path = ()
+    if check_str_encoding:
+        assert a.encoding == b.encoding, \
+            'string encodings do not match: %r != %r\n%s' % (
+                a.encoding, b.encoding, _fmt_path(path + ('.encoding',)),
+            )
+
+    if check_str_fixlen:
+        assert a.fixlen == b.fixlen, \
+            'string fixlens do not match: %d != %d\n%s' % (
+                a.fixlen, b.fixlen, _fmt_path(path + ('.fixlen',)),
+            )
+
+
+@dispatch(Option, Option)
+def assert_dshape_equal(a, b, path=None, **kwargs):
+    if path is None:
+        path = ()
+    path += '.ty',
+    return assert_dshape_equal(a.ty, b.ty, path=path, **kwargs)
+
+
+@dispatch(Record, Record)
+def assert_dshape_equal(a, b, check_record_order=True, path=None, **kwargs):
+    afields = a.fields
+    bfields = b.fields
+
+    assert len(afields) == len(bfields), \
+        'records have mismatched field counts: %d != %d\n%r != %r\n%s' % (
+            len(afields), len(bfields), a.names, b.names, _fmt_path(path),
+        )
+
+    if not check_record_order:
+        afields = sorted(afields)
+        bfields = sorted(bfields)
+
+    if path is None:
+        path = ()
+    for n, ((aname, afield), (bname, bfield)) in enumerate(
+            zip(afields, bfields)):
+
+        assert aname == bname, \
+            'record field name at position %d does not match: %r != %r\n%s' % (
+                n, aname, bname, _fmt_path(path),
+            )
+
+        assert_dshape_equal(
+            afield,
+            bfield,
+            path=path + ('[%s]' % repr(aname),),
+            check_record_order=check_record_order,
+            **kwargs
+        )
+
+
+@dispatch(Tuple, Tuple)
+def assert_dshape_equal(a, b, path=None, **kwargs):
+    assert len(a.dshapes) == len(b.dshapes), \
+        'tuples have mismatched field counts: %d != %d\n%r != %r\n%s' % (
+            len(a.dshapes), len(b.dshapes), a, b, _fmt_path(path),
+        )
+
+    if path is None:
+        path = ()
+    path += '.dshapes',
+    for n, (ashape, bshape) in enumerate(zip(a.dshapes, b.dshapes)):
+        assert_dshape_equal(
+            ashape,
+            bshape,
+            path=path + ('[%d]' % n,),
+            **kwargs
+        )
+
+
+@dispatch(Function, Function)
+def assert_dshape_equal(a, b, path=None, **kwargs):
+    assert len(a.argtypes) == len(b.argtypes),\
+        'functions have different arities: %d != %d\n%r != %r\n%s' % (
+            len(a.argtypes), len(b.argtypes), a, b, _fmt_path(path),
+        )
+
+    if path is None:
+        path = ()
+    for n, (aarg, barg) in enumerate(zip(a.argtypes, b.argtypes)):
+        assert_dshape_equal(
+            aarg,
+            barg,
+            path=path + ('.argtypes[%d]' % n,), **kwargs
+        )
+    assert_dshape_equal(
+        a.restype,
+        b.restype,
+        path=path + ('.restype',),
+        **kwargs
+    )
diff --git a/datashader/datashape/util/tests/test_testing.py b/datashader/datashape/util/tests/test_testing.py
new file mode 100644
index 000000000..e4cf08537
--- /dev/null
+++ b/datashader/datashape/util/tests/test_testing.py
@@ -0,0 +1,239 @@
+"""Testing the test helpers.
+
+Kill me now.
+"""
+import pytest
+
+from datashader.datashape.coretypes import (
+    DateTime,
+    R,
+    String,
+    Time,
+    TimeDelta,
+    Tuple,
+    Option,
+    int32,
+    float32,
+)
+from datashader.datashape.util import dshape
+from datashader.datashape.util.testing import assert_dshape_equal
+
+
+def test_datashape_measure():
+    assert_dshape_equal(dshape('int'), dshape('int'))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(dshape('int'), dshape('string'))
+    assert 'int32 != string' in str(e.value)
+    assert '_.measure' in str(e.value)
+
+
+def test_dim():
+    assert_dshape_equal(dshape('var * int'), dshape('var * int'))
+    assert_dshape_equal(dshape('3 * string'), dshape('3 * string'))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(dshape('var * int'), dshape('3 * int'))
+    assert 'var != 3' in str(e.value)
+    assert '_.shape[0]' in str(e.value)
+
+    assert_dshape_equal(dshape('var * var * int'), dshape('var * var * int'))
+    assert_dshape_equal(dshape('var * 3 * string'), dshape('var * 3 * string'))
+    assert_dshape_equal(
+        dshape('3 * var * float32'),
+        dshape('3 * var * float32'),
+    )
+    assert_dshape_equal(
+        dshape('3 * 3 * datetime'),
+        dshape('3 * 3 * datetime'),
+    )
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            dshape('var * var * int'),
+            dshape('3 * var * int'),
+        )
+    assert 'var != 3' in str(e.value)
+    assert '_.shape[0]' in str(e.value)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            dshape('var * var * int'),
+            dshape('var * 3 * int'),
+        )
+    assert 'var != 3' in str(e.value)
+    assert '_.shape[1]' in str(e.value)
+
+
+def test_record():
+    assert_dshape_equal(
+        R['a': int32, 'b': float32],
+        R['a': int32, 'b': float32],
+    )
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            R['a': int32, 'b': float32],
+            R['a': int32, 'b': int32],
+        )
+    assert "'float32' != 'int32'" in str(e)
+    assert "_['b'].name" in str(e.value)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            R['a': int32, 'b': float32],
+            R['a': int32, 'c': float32],
+        )
+    assert "'b' != 'c'" in str(e.value)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            R['b': float32, 'a': float32],
+            R['a': int32, 'b': float32],
+            check_record_order=False,
+        )
+    assert "'float32' != 'int32'" in str(e.value)
+    assert "_['a']" in str(e.value)
+
+    assert_dshape_equal(
+        R['b': float32, 'a': int32],
+        R['a': int32, 'b': float32],
+        check_record_order=False,
+    )
+
+    # check a nested record with and without ordering
+    assert_dshape_equal(
+        R['a': R['b': float32, 'a': int32]],
+        R['a': R['a': int32, 'b': float32]],
+        check_record_order=False,
+    )
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            R['a': R['a': int32, 'b': float32]],
+            R['a': R['b': float32, 'a': int32]],
+        )
+
+    assert "'a' != 'b'" in str(e.value)
+    assert "_['a']" in str(e.value)
+
+
+def test_tuple():
+    assert_dshape_equal(Tuple((int32, float32)), Tuple((int32, float32)))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(Tuple((int32, float32)), Tuple((int32, int32)))
+    assert "'float32' != 'int32'" in str(e)
+    assert "_.dshapes[1].measure.name" in str(e.value)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(Tuple((int32, float32)), Tuple((int32, int32)))
+    assert "'float32' != 'int32'" in str(e)
+    assert '_.dshapes[1].measure.name' in str(e.value)
+
+
+def test_option():
+    assert_dshape_equal(Option(int32), Option(int32))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(Option(int32), Option(float32))
+    assert "'int32' != 'float32'" in str(e.value)
+    assert '_.ty' in str(e.value)
+
+
+def test_string():
+    assert_dshape_equal(String(), String())
+    assert_dshape_equal(String('U8'), String('U8'))
+    assert_dshape_equal(String(1), String(1))
+    assert_dshape_equal(String(1, 'U8'), String(1, 'U8'))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(String('U8'), String('U16'))
+
+    assert "'U8' != 'U16'" in str(e.value)
+    assert '_.encoding' in str(e.value)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(String(1), String(2))
+    assert '1 != 2' in str(e.value)
+    assert '_.fixlen' in str(e.value)
+
+
+def test_timedelta():
+    assert_dshape_equal(TimeDelta(), TimeDelta())
+    assert_dshape_equal(TimeDelta('ns'), TimeDelta('ns'))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(TimeDelta('us'), TimeDelta('ns'))
+    assert "'us' != 'ns'" in str(e.value)
+    assert '_.unit' in str(e.value)
+
+    assert_dshape_equal(
+        TimeDelta('us'),
+        TimeDelta('ns'),
+        check_timedelta_unit=False,
+    )
+
+
+@pytest.mark.parametrize('cls', (DateTime, Time))
+def test_datetime(cls):
+    assert_dshape_equal(cls(), cls())
+    assert_dshape_equal(cls('US/Eastern'), cls('US/Eastern'))
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(cls('US/Eastern'), cls('US/Central'))
+    assert "'US/Eastern' != 'US/Central'" in str(e.value)
+    assert '_.tz' in str(e.value)
+
+    assert_dshape_equal(
+        cls('US/Eastern'),
+        cls('US/Central'),
+        check_tz=False,
+    )
+
+
+def test_nested():
+    assert_dshape_equal(
+        dshape('var * {a: 3 * {b: int32}}'),
+        dshape('var * {a: 3 * {b: int32}}'),
+    )
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(
+            dshape('var * {a: 3 * {b: int32}}'),
+            dshape('var * {a: 3 * {b: float32}}'),
+        )
+    assert "'int32' != 'float32'" in str(e.value)
+    assert "_.measure['a'].measure['b'].name" in str(e.value)
+
+
+@pytest.mark.parametrize(
+    'dshape_,contains', (
+        (
+            '(string, int64) -> int64', (
+                'string != int32',
+                '_.measure.argtypes[0].measure',
+            ),
+        ),
+        (
+            '(int32, int32) -> int64', (
+                "'int32' != 'int64'",
+                '_.measure.argtypes[1].measure.name',
+            ),
+        ),
+        (
+            '(int32, int64) -> int32', (
+                "'int32' != 'int64'",
+                '_.measure.restype.measure.name',
+            ),
+        ),
+    ),
+)
+def test_function(dshape_, contains):
+    base = dshape('(int32, int64) -> int64')
+    assert_dshape_equal(base, base)
+
+    with pytest.raises(AssertionError) as e:
+        assert_dshape_equal(dshape(dshape_), base)
+    for c in contains:
+        assert c in str(e.value)
diff --git a/datashader/tests/test_glyphs.py b/datashader/tests/test_glyphs.py
index f8748d4dc..46dcd2c7f 100644
--- a/datashader/tests/test_glyphs.py
+++ b/datashader/tests/test_glyphs.py
@@ -1,11 +1,10 @@
 from __future__ import annotations
-from datashape import dshape
 import pandas as pd
 import numpy as np
 import pytest
 
+from datashader.datashape import dshape
 from datashader.glyphs import Point, LinesAxis1, Glyph
-
 from datashader.glyphs.area import _build_draw_trapezoid_y
 from datashader.glyphs.line import (
     _build_map_onto_pixel_for_line,
diff --git a/datashader/tests/test_utils.py b/datashader/tests/test_utils.py
index 39b273704..e4be2fa7a 100644
--- a/datashader/tests/test_utils.py
+++ b/datashader/tests/test_utils.py
@@ -1,8 +1,8 @@
 from __future__ import annotations
-from datashape import dshape
 import numpy as np
 from xarray import DataArray
 
+from datashader.datashape import dshape
 from datashader.utils import Dispatcher, apply, calc_res, isreal, orient_array