Repository: holoviz/datashader

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:
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz) Report
> Merging [#1284](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz) (aa8ea30) into [main](https://app.codecov.io/gh/holoviz/datashader/commit/f79f47ab43b23f8c8d820c2eef3ff98af26f862d?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz) (f79f47a) will **increase** coverage by `2.20%`.
> The diff coverage is `97.39%`.

```diff
@@            Coverage Diff             @@
##             main    #1284      +/-   ##
==========================================
+ Coverage   83.52%   85.72%   +2.20%     
==========================================
  Files          35       52      +17     
  Lines        9145    10870    +1725     
==========================================
+ Hits         7638     9318    +1680     
- Misses       1507     1552      +45     
```


| [Files](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz) | Coverage Δ | |
|---|---|---|
| [datashader/datashape/\_\_init\_\_.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvX19pbml0X18ucHk=) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/dispatch.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvZGlzcGF0Y2gucHk=) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/lexer.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvbGV4ZXIucHk=) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/predicates.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvcHJlZGljYXRlcy5weQ==) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/promote.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvcHJvbW90ZS5weQ==) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/py2help.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvcHkyaGVscC5weQ==) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/type\_symbol\_table.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvdHlwZV9zeW1ib2xfdGFibGUucHk=) | `100.00% <100.00%> (ø)` | |
| [datashader/datashape/util/\_\_init\_\_.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9kYXRhc2hhcGUvdXRpbC9fX2luaXRfXy5weQ==) | `100.00% <100.00%> (ø)` | |
| [datashader/reductions.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci9yZWR1Y3Rpb25zLnB5) | `80.62% <100.00%> (ø)` | |
| [datashader/utils.py](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz#diff-ZGF0YXNoYWRlci91dGlscy5weQ==) | `76.64% <100.00%> (ø)` | |
| ... and [9 more](https://app.codecov.io/gh/holoviz/datashader/pull/1284?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz) | |

:mega: We’re building smart automated test selection to slash your CI/CD build times. [Learn more](https://about.codecov.io/iterative-testing/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=holoviz)

ianthomas23: Passes CI and successfully builds packages and docs.

Patch:
diff --git a/datashader/datashape/__init__.py b/datashader/datashape/__init__.py
new file mode 100644
index 0000000..beb8c0f
--- /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 0000000..eaf4d2a
--- /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 0000000..c33be5e
--- /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 0000000..0e92cbf
--- /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 0000000..7fe0b75
--- /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 0000000..701d2a9
--- /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 0000000..b3e1935
--- /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 0000000..aecab52
--- /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 0000000..bacc45d
--- /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 0000000..2403a44
--- /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 0000000..4eaabe1
--- /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 0000000..1032100
--- /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 0000000..bfcec97
--- /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 0000000..0aa9b47
--- /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 0000000..5aa4d07
--- /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 0000000..a608672
--- /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 e6ce7a0..dd1b3ab 100644
--- a/datashader/reductions.py
+++ b/datashader/reductions.py
@@ -3,8 +3,8 @@ import copy
 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 0fb7c37..70667b1 100644
--- a/datashader/utils.py
+++ b/datashader/utils.py
@@ -13,7 +13,7 @@ from toolz import memoize
 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 d46b689..0f4d438 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 7889101..ef35712 100644
--- a/setup.py
+++ b/setup.py
@@ -11,7 +11,7 @@ import pyct.build
 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 0000000..e69de29
diff --git a/datashader/datashape/tests/test_coretypes.py b/datashader/datashape/tests/test_coretypes.py
new file mode 100644
index 0000000..dfb91ce
--- /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 0000000..e7872fe
--- /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 0000000..9ecc5d1
--- /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 0000000..e56e6a4
--- /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 0000000..32a6282
--- /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 0000000..6258b72
--- /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 0000000..93ec7f0
--- /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 0000000..9d619ee
--- /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 0000000..d6aef8b
--- /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 0000000..9f5562e
--- /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 0000000..39136bd
--- /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 0000000..a3b901f
--- /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 0000000..c60e8c9
--- /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 0000000..e4cf085
--- /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 f8748d4..46dcd2c 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 39b2737..e4be2fa 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