nmigen/hdl/ast.py

   1 from abc import ABCMeta, abstractmethod
   2 import builtins
   3 import traceback
   4 from collections import OrderedDict
   5 from collections.abc import Iterable, MutableMapping, MutableSet, MutableSequence
   6
   7 from .. import tracer
   8 from ..tools import *
   9
  10
  11 __all__ = [
  12     "Value", "Const", "C", "Operator", "Mux", "Part", "Slice", "Cat", "Repl",
  13     "Array", "ArrayProxy",
  14     "Signal", "ClockSignal", "ResetSignal",
  15     "Statement", "Assign", "Assert", "Assume", "Switch", "Delay", "Tick",
  16     "Passive", "ValueKey", "ValueDict", "ValueSet", "SignalKey", "SignalDict",
  17     "SignalSet",
  18 ]
  19
  20
  21 class DUID:
  22     """Deterministic Unique IDentifier"""
  23     __next_uid = 0
  24     def __init__(self):
  25         self.duid = DUID.__next_uid
  26         DUID.__next_uid += 1
  27
  28
  29 class Value(metaclass=ABCMeta):
  30     @staticmethod
  31     def wrap(obj):
  32         """Ensures that the passed object is an nMigen value. Booleans and integers
  33         are automatically wrapped into ``Const``."""
  34         if isinstance(obj, Value):
  35             return obj
  36         elif isinstance(obj, (bool, int)):
  37             return Const(obj)
  38         else:
  39             raise TypeError("Object '{!r}' is not an nMigen value".format(obj))
  40
  41     def __init__(self, src_loc_at=0):
  42         super().__init__()
  43         self.src_loc = tracer.get_src_loc(1 + src_loc_at)
  44
  45     def __bool__(self):
  46         raise TypeError("Attempted to convert nMigen value to boolean")
  47
  48     def __invert__(self):
  49         return Operator("~", [self])
  50     def __neg__(self):
  51         return Operator("-", [self])
  52
  53     def __add__(self, other):
  54         return Operator("+", [self, other])
  55     def __radd__(self, other):
  56         return Operator("+", [other, self])
  57     def __sub__(self, other):
  58         return Operator("-", [self, other])
  59     def __rsub__(self, other):
  60         return Operator("-", [other, self])
  61     def __mul__(self, other):
  62         return Operator("*", [self, other])
  63     def __rmul__(self, other):
  64         return Operator("*", [other, self])
  65     def __mod__(self, other):
  66         return Operator("%", [self, other])
  67     def __rmod__(self, other):
  68         return Operator("%", [other, self])
  69     def __div__(self, other):
  70         return Operator("/", [self, other])
  71     def __rdiv__(self, other):
  72         return Operator("/", [other, self])
  73     def __lshift__(self, other):
  74         return Operator("<<", [self, other])
  75     def __rlshift__(self, other):
  76         return Operator("<<", [other, self])
  77     def __rshift__(self, other):
  78         return Operator(">>", [self, other])
  79     def __rrshift__(self, other):
  80         return Operator(">>", [other, self])
  81     def __and__(self, other):
  82         return Operator("&", [self, other])
  83     def __rand__(self, other):
  84         return Operator("&", [other, self])
  85     def __xor__(self, other):
  86         return Operator("^", [self, other])
  87     def __rxor__(self, other):
  88         return Operator("^", [other, self])
  89     def __or__(self, other):
  90         return Operator("|", [self, other])
  91     def __ror__(self, other):
  92         return Operator("|", [other, self])
  93
  94     def __eq__(self, other):
  95         return Operator("==", [self, other])
  96     def __ne__(self, other):
  97         return Operator("!=", [self, other])
  98     def __lt__(self, other):
  99         return Operator("<", [self, other])
 100     def __le__(self, other):
 101         return Operator("<=", [self, other])
 102     def __gt__(self, other):
 103         return Operator(">", [self, other])
 104     def __ge__(self, other):
 105         return Operator(">=", [self, other])
 106
 107     def __len__(self):
 108         return self.shape()[0]
 109
 110     def __getitem__(self, key):
 111         n = len(self)
 112         if isinstance(key, int):
 113             if key not in range(-n, n):
 114                 raise IndexError("Cannot index {} bits into {}-bit value".format(key, n))
 115             if key < 0:
 116                 key += n
 117             return Slice(self, key, key + 1)
 118         elif isinstance(key, slice):
 119             start, stop, step = key.indices(n)
 120             if step != 1:
 121                 return Cat(self[i] for i in range(start, stop, step))
 122             return Slice(self, start, stop)
 123         else:
 124             raise TypeError("Cannot index value with {}".format(repr(key)))
 125
 126     def bool(self):
 127         """Conversion to boolean.
 128
 129         Returns
 130         -------
 131         Value, out
 132             Output ``Value``. If any bits are set, returns ``1``, else ``0``.
 133         """
 134         return Operator("b", [self])
 135
 136     def part(self, offset, width):
 137         """Indexed part-select.
 138
 139         Selects a constant width but variable offset part of a ``Value``.
 140
 141         Parameters
 142         ----------
 143         offset : Value, in
 144             start point of the selected bits
 145         width : int
 146             number of selected bits
 147
 148         Returns
 149         -------
 150         Part, out
 151             Selected part of the ``Value``
 152         """
 153         return Part(self, offset, width)
 154
 155     def eq(self, value):
 156         """Assignment.
 157
 158         Parameters
 159         ----------
 160         value : Value, in
 161             Value to be assigned.
 162
 163         Returns
 164         -------
 165         Assign
 166             Assignment statement that can be used in combinatorial or synchronous context.
 167         """
 168         return Assign(self, value)
 169
 170     @abstractmethod
 171     def shape(self):
 172         """Bit length and signedness of a value.
 173
 174         Returns
 175         -------
 176         int, bool
 177             Number of bits required to store `v` or available in `v`, followed by
 178             whether `v` has a sign bit (included in the bit count).
 179
 180         Examples
 181         --------
 182         >>> Value.shape(Signal(8))
 183         8, False
 184         >>> Value.shape(C(0xaa))
 185         8, False
 186         """
 187         pass # :nocov:
 188
 189     def _lhs_signals(self):
 190         raise TypeError("Value {!r} cannot be used in assignments".format(self))
 191
 192     @abstractmethod
 193     def _rhs_signals(self):
 194         pass # :nocov:
 195
 196     def _as_const(self):
 197         raise TypeError("Value {!r} cannot be evaluated as constant".format(self))
 198
 199     __hash__ = None
 200
 201
 202 class Const(Value):
 203     """A constant, literal integer value.
 204
 205     Parameters
 206     ----------
 207     value : int
 208     shape : int or tuple or None
 209         Either an integer `bits` or a tuple `(bits, signed)`
 210         specifying the number of bits in this `Const` and whether it is
 211         signed (can represent negative values). `shape` defaults
 212         to the minimum width and signedness of `value`.
 213
 214     Attributes
 215     ----------
 216     nbits : int
 217     signed : bool
 218     """
 219     src_loc = None
 220
 221     @staticmethod
 222     def normalize(value, shape):
 223         nbits, signed = shape
 224         mask = (1 << nbits) - 1
 225         value &= mask
 226         if signed and value >> (nbits - 1):
 227             value |= ~mask
 228         return value
 229
 230     def __init__(self, value, shape=None):
 231         self.value = int(value)
 232         if shape is None:
 233             shape = bits_for(self.value), self.value < 0
 234         if isinstance(shape, int):
 235             shape = shape, self.value < 0
 236         self.nbits, self.signed = shape
 237         if not isinstance(self.nbits, int) or self.nbits < 0:
 238             raise TypeError("Width must be a non-negative integer, not '{!r}'", self.nbits)
 239         self.value = self.normalize(self.value, shape)
 240
 241     def shape(self):
 242         return self.nbits, self.signed
 243
 244     def _rhs_signals(self):
 245         return ValueSet()
 246
 247     def _as_const(self):
 248         return self.value
 249
 250     def __repr__(self):
 251         return "(const {}'{}d{})".format(self.nbits, "s" if self.signed else "", self.value)
 252
 253
 254 C = Const  # shorthand
 255
 256
 257 class Operator(Value):
 258     def __init__(self, op, operands, src_loc_at=0):
 259         super().__init__(src_loc_at=1 + src_loc_at)
 260         self.op = op
 261         self.operands = [Value.wrap(o) for o in operands]
 262
 263     @staticmethod
 264     def _bitwise_binary_shape(a_shape, b_shape):
 265         a_bits, a_sign = a_shape
 266         b_bits, b_sign = b_shape
 267         if not a_sign and not b_sign:
 268             # both operands unsigned
 269             return max(a_bits, b_bits), False
 270         elif a_sign and b_sign:
 271             # both operands signed
 272             return max(a_bits, b_bits), True
 273         elif not a_sign and b_sign:
 274             # first operand unsigned (add sign bit), second operand signed
 275             return max(a_bits + 1, b_bits), True
 276         else:
 277             # first signed, second operand unsigned (add sign bit)
 278             return max(a_bits, b_bits + 1), True
 279
 280     def shape(self):
 281         op_shapes = list(map(lambda x: x.shape(), self.operands))
 282         if len(op_shapes) == 1:
 283             (a_bits, a_sign), = op_shapes
 284             if self.op in ("+", "~"):
 285                 return a_bits, a_sign
 286             if self.op == "-":
 287                 if not a_sign:
 288                     return a_bits + 1, True
 289                 else:
 290                     return a_bits, a_sign
 291             if self.op == "b":
 292                 return 1, False
 293         elif len(op_shapes) == 2:
 294             (a_bits, a_sign), (b_bits, b_sign) = op_shapes
 295             if self.op == "+" or self.op == "-":
 296                 bits, sign = self._bitwise_binary_shape(*op_shapes)
 297                 return bits + 1, sign
 298             if self.op == "*":
 299                 if not a_sign and not b_sign:
 300                     # both operands unsigned
 301                     return a_bits + b_bits, False
 302                 if a_sign and b_sign:
 303                     # both operands signed
 304                     return a_bits + b_bits - 1, True
 305                 # one operand signed, the other unsigned (add sign bit)
 306                 return a_bits + b_bits + 1 - 1, True
 307             if self.op in ("<", "<=", "==", "!=", ">", ">=", "b"):
 308                 return 1, False
 309             if self.op in ("&", "^", "|"):
 310                 return self._bitwise_binary_shape(*op_shapes)
 311             if self.op == "<<":
 312                 if b_sign:
 313                     extra = 2 ** (b_bits - 1) - 1
 314                 else:
 315                     extra = 2 ** (b_bits)     - 1
 316                 return a_bits + extra, a_sign
 317             if self.op == ">>":
 318                 if b_sign:
 319                     extra = 2 ** (b_bits - 1)
 320                 else:
 321                     extra = 0
 322                 return a_bits + extra, a_sign
 323         elif len(op_shapes) == 3:
 324             if self.op == "m":
 325                 s_shape, a_shape, b_shape = op_shapes
 326                 return self._bitwise_binary_shape(a_shape, b_shape)
 327         raise NotImplementedError("Operator {}/{} not implemented"
 328                                   .format(self.op, len(op_shapes))) # :nocov:
 329
 330     def _rhs_signals(self):
 331         return union(op._rhs_signals() for op in self.operands)
 332
 333     def __repr__(self):
 334         return "({} {})".format(self.op, " ".join(map(repr, self.operands)))
 335
 336
 337 def Mux(sel, val1, val0):
 338     """Choose between two values.
 339
 340     Parameters
 341     ----------
 342     sel : Value, in
 343         Selector.
 344     val1 : Value, in
 345     val0 : Value, in
 346         Input values.
 347
 348     Returns
 349     -------
 350     Value, out
 351         Output ``Value``. If ``sel`` is asserted, the Mux returns ``val1``, else ``val0``.
 352     """
 353     return Operator("m", [sel, val1, val0], src_loc_at=1)
 354
 355
 356 class Slice(Value):
 357     def __init__(self, value, start, end):
 358         if not isinstance(start, int):
 359             raise TypeError("Slice start must be an integer, not '{!r}'".format(start))
 360         if not isinstance(end, int):
 361             raise TypeError("Slice end must be an integer, not '{!r}'".format(end))
 362
 363         n = len(value)
 364         if start not in range(-(n+1), n+1):
 365             raise IndexError("Cannot start slice {} bits into {}-bit value".format(start, n))
 366         if start < 0:
 367             start += n
 368         if end not in range(-(n+1), n+1):
 369             raise IndexError("Cannot end slice {} bits into {}-bit value".format(end, n))
 370         if end < 0:
 371             end += n
 372         if start > end:
 373             raise IndexError("Slice start {} must be less than slice end {}".format(start, end))
 374
 375         super().__init__()
 376         self.value = Value.wrap(value)
 377         self.start = start
 378         self.end   = end
 379
 380     def shape(self):
 381         return self.end - self.start, False
 382
 383     def _lhs_signals(self):
 384         return self.value._lhs_signals()
 385
 386     def _rhs_signals(self):
 387         return self.value._rhs_signals()
 388
 389     def __repr__(self):
 390         return "(slice {} {}:{})".format(repr(self.value), self.start, self.end)
 391
 392
 393 class Part(Value):
 394     def __init__(self, value, offset, width):
 395         if not isinstance(width, int) or width < 0:
 396             raise TypeError("Part width must be a non-negative integer, not '{!r}'".format(width))
 397
 398         super().__init__()
 399         self.value  = value
 400         self.offset = Value.wrap(offset)
 401         self.width  = width
 402
 403     def shape(self):
 404         return self.width, False
 405
 406     def _lhs_signals(self):
 407         return self.value._lhs_signals()
 408
 409     def _rhs_signals(self):
 410         return self.value._rhs_signals() | self.offset._rhs_signals()
 411
 412     def __repr__(self):
 413         return "(part {} {} {})".format(repr(self.value), repr(self.offset), self.width)
 414
 415
 416 class Cat(Value):
 417     """Concatenate values.
 418
 419     Form a compound ``Value`` from several smaller ones by concatenation.
 420     The first argument occupies the lower bits of the result.
 421     The return value can be used on either side of an assignment, that
 422     is, the concatenated value can be used as an argument on the RHS or
 423     as a target on the LHS. If it is used on the LHS, it must solely
 424     consist of ``Signal`` s, slices of ``Signal`` s, and other concatenations
 425     meeting these properties. The bit length of the return value is the sum of
 426     the bit lengths of the arguments::
 427
 428         len(Cat(args)) == sum(len(arg) for arg in args)
 429
 430     Parameters
 431     ----------
 432     *args : Values or iterables of Values, inout
 433         ``Value`` s to be concatenated.
 434
 435     Returns
 436     -------
 437     Value, inout
 438         Resulting ``Value`` obtained by concatentation.
 439     """
 440     def __init__(self, *args):
 441         super().__init__()
 442         self.parts = [Value.wrap(v) for v in flatten(args)]
 443
 444     def shape(self):
 445         return sum(len(part) for part in self.parts), False
 446
 447     def _lhs_signals(self):
 448         return union(part._lhs_signals() for part in self.parts)
 449
 450     def _rhs_signals(self):
 451         return union(part._rhs_signals() for part in self.parts)
 452
 453     def _as_const(self):
 454         value = 0
 455         for part in reversed(self.parts):
 456             value <<= len(part)
 457             value |= part._as_const()
 458         return value
 459
 460     def __repr__(self):
 461         return "(cat {})".format(" ".join(map(repr, self.parts)))
 462
 463
 464 class Repl(Value):
 465     """Replicate a value
 466
 467     An input value is replicated (repeated) several times
 468     to be used on the RHS of assignments::
 469
 470         len(Repl(s, n)) == len(s) * n
 471
 472     Parameters
 473     ----------
 474     value : Value, in
 475         Input value to be replicated.
 476     count : int
 477         Number of replications.
 478
 479     Returns
 480     -------
 481     Repl, out
 482         Replicated value.
 483     """
 484     def __init__(self, value, count):
 485         if not isinstance(count, int) or count < 0:
 486             raise TypeError("Replication count must be a non-negative integer, not '{!r}'"
 487                             .format(count))
 488
 489         super().__init__()
 490         self.value = Value.wrap(value)
 491         self.count = count
 492
 493     def shape(self):
 494         return len(self.value) * self.count, False
 495
 496     def _rhs_signals(self):
 497         return self.value._rhs_signals()
 498
 499     def __repr__(self):
 500         return "(repl {!r} {})".format(self.value, self.count)
 501
 502
 503 class Signal(Value, DUID):
 504     """A varying integer value.
 505
 506     Parameters
 507     ----------
 508     shape : int or tuple or None
 509         Either an integer ``bits`` or a tuple ``(bits, signed)`` specifying the number of bits
 510         in this ``Signal`` and whether it is signed (can represent negative values).
 511         ``shape`` defaults to 1-bit and non-signed.
 512     name : str
 513         Name hint for this signal. If ``None`` (default) the name is inferred from the variable
 514         name this ``Signal`` is assigned to. Name collisions are automatically resolved by
 515         prepending names of objects that contain this ``Signal`` and by appending integer
 516         sequences.
 517     reset : int
 518         Reset (synchronous) or default (combinatorial) value.
 519         When this ``Signal`` is assigned to in synchronous context and the corresponding clock
 520         domain is reset, the ``Signal`` assumes the given value. When this ``Signal`` is unassigned
 521         in combinatorial context (due to conditional assignments not being taken), the ``Signal``
 522         assumes its ``reset`` value. Defaults to 0.
 523     reset_less : bool
 524         If ``True``, do not generate reset logic for this ``Signal`` in synchronous statements.
 525         The ``reset`` value is only used as a combinatorial default or as the initial value.
 526         Defaults to ``False``.
 527     min : int or None
 528     max : int or None
 529         If ``shape`` is ``None``, the signal bit width and signedness are
 530         determined by the integer range given by ``min`` (inclusive,
 531         defaults to 0) and ``max`` (exclusive, defaults to 2).
 532     attrs : dict
 533         Dictionary of synthesis attributes.
 534     decoder : function
 535         A function converting integer signal values to human-readable strings (e.g. FSM state
 536         names).
 537
 538     Attributes
 539     ----------
 540     nbits : int
 541     signed : bool
 542     name : str
 543     reset : int
 544     reset_less : bool
 545     attrs : dict
 546     """
 547
 548     def __init__(self, shape=None, name=None, reset=0, reset_less=False, min=None, max=None,
 549                  attrs=None, decoder=None, src_loc_at=0):
 550         super().__init__(src_loc_at=src_loc_at)
 551
 552         if name is None:
 553             try:
 554                 name = tracer.get_var_name(depth=2 + src_loc_at)
 555             except tracer.NameNotFound:
 556                 name = "$signal"
 557         self.name = name
 558
 559         if shape is None:
 560             if min is None:
 561                 min = 0
 562             if max is None:
 563                 max = 2
 564             max -= 1  # make both bounds inclusive
 565             if not min < max:
 566                 raise ValueError("Lower bound {} should be less than higher bound {}"
 567                                  .format(min, max))
 568             self.signed = min < 0 or max < 0
 569             self.nbits  = builtins.max(bits_for(min, self.signed), bits_for(max, self.signed))
 570
 571         else:
 572             if not (min is None and max is None):
 573                 raise ValueError("Only one of bits/signedness or bounds may be specified")
 574             if isinstance(shape, int):
 575                 self.nbits, self.signed = shape, False
 576             else:
 577                 self.nbits, self.signed = shape
 578
 579         if not isinstance(self.nbits, int) or self.nbits < 0:
 580             raise TypeError("Width must be a non-negative integer, not '{!r}'".format(self.nbits))
 581         self.reset = int(reset)
 582         self.reset_less = bool(reset_less)
 583
 584         self.attrs = OrderedDict(() if attrs is None else attrs)
 585         self.decoder = decoder
 586
 587     @classmethod
 588     def like(cls, other, src_loc_at=0, **kwargs):
 589         """Create Signal based on another.
 590
 591         Parameters
 592         ----------
 593         other : Value
 594             Object to base this Signal on.
 595         """
 596         kw = dict(shape=cls.wrap(other).shape(),
 597                   name=tracer.get_var_name(depth=2 + src_loc_at))
 598         if isinstance(other, cls):
 599             kw.update(reset=other.reset, reset_less=other.reset_less,
 600                       attrs=other.attrs, decoder=other.decoder)
 601         kw.update(kwargs)
 602         return cls(**kw, src_loc_at=1 + src_loc_at)
 603
 604     def shape(self):
 605         return self.nbits, self.signed
 606
 607     def _lhs_signals(self):
 608         return ValueSet((self,))
 609
 610     def _rhs_signals(self):
 611         return ValueSet((self,))
 612
 613     def __repr__(self):
 614         return "(sig {})".format(self.name)
 615
 616
 617 class ClockSignal(Value):
 618     """Clock signal for a clock domain.
 619
 620     Any ``ClockSignal`` is equivalent to ``cd.clk`` for a clock domain with the corresponding name.
 621     All of these signals ultimately refer to the same signal, but they can be manipulated
 622     independently of the clock domain, even before the clock domain is created.
 623
 624     Parameters
 625     ----------
 626     domain : str
 627         Clock domain to obtain a clock signal for. Defaults to ``"sync"``.
 628     """
 629     def __init__(self, domain="sync"):
 630         super().__init__()
 631         if not isinstance(domain, str):
 632             raise TypeError("Clock domain name must be a string, not '{!r}'".format(domain))
 633         self.domain = domain
 634
 635     def shape(self):
 636         return 1, False
 637
 638     def _rhs_signals(self):
 639         raise NotImplementedError("ClockSignal must be lowered to a concrete signal") # :nocov:
 640
 641     def __repr__(self):
 642         return "(clk {})".format(self.domain)
 643
 644
 645 class ResetSignal(Value):
 646     """Reset signal for a clock domain.
 647
 648     Any ``ResetSignal`` is equivalent to ``cd.rst`` for a clock domain with the corresponding name.
 649     All of these signals ultimately refer to the same signal, but they can be manipulated
 650     independently of the clock domain, even before the clock domain is created.
 651
 652     Parameters
 653     ----------
 654     domain : str
 655         Clock domain to obtain a reset signal for. Defaults to ``"sync"``.
 656     allow_reset_less : bool
 657         If the clock domain is reset-less, act as a constant ``0`` instead of reporting an error.
 658     """
 659     def __init__(self, domain="sync", allow_reset_less=False):
 660         super().__init__()
 661         if not isinstance(domain, str):
 662             raise TypeError("Clock domain name must be a string, not '{!r}'".format(domain))
 663         self.domain = domain
 664         self.allow_reset_less = allow_reset_less
 665
 666     def shape(self):
 667         return 1, False
 668
 669     def _rhs_signals(self):
 670         raise NotImplementedError("ResetSignal must be lowered to a concrete signal") # :nocov:
 671
 672     def __repr__(self):
 673         return "(rst {})".format(self.domain)
 674
 675
 676 class Array(MutableSequence):
 677     """Addressable multiplexer.
 678
 679     An array is similar to a ``list`` that can also be indexed by ``Value``s; indexing by an integer or a slice works the same as for Python lists, but indexing by a ``Value`` results
 680     in a proxy.
 681
 682     The array proxy can be used as an ordinary ``Value``, i.e. participate in calculations and
 683     assignments, provided that all elements of the array are values. The array proxy also supports
 684     attribute access and further indexing, each returning another array proxy; this means that
 685     the results of indexing into arrays, arrays of records, and arrays of arrays can all
 686     be used as first-class values.
 687
 688     It is an error to change an array or any of its elements after an array proxy was created.
 689     Changing the array directly will raise an exception. However, it is not possible to detect
 690     the elements being modified; if an element's attribute or element is modified after the proxy
 691     for it has been created, the proxy will refer to stale data.
 692
 693     Examples
 694     --------
 695
 696     Simple array::
 697
 698         gpios = Array(Signal() for _ in range(10))
 699         with m.If(bus.we):
 700             m.d.sync += gpios[bus.adr].eq(bus.dat_w)
 701         with m.Else():
 702             m.d.sync += bus.dat_r.eq(gpios[bus.adr])
 703
 704     Multidimensional array::
 705
 706         mult = Array(Array(x * y for y in range(10)) for x in range(10))
 707         a = Signal(max=10)
 708         b = Signal(max=10)
 709         r = Signal(8)
 710         m.d.comb += r.eq(mult[a][b])
 711
 712     Array of records::
 713
 714         layout = [
 715             ("re",     1),
 716             ("dat_r", 16),
 717         ]
 718         buses  = Array(Record(layout) for busno in range(4))
 719         master = Record(layout)
 720         m.d.comb += [
 721             buses[sel].re.eq(master.re),
 722             master.dat_r.eq(buses[sel].dat_r),
 723         ]
 724     """
 725     def __init__(self, iterable=()):
 726         self._inner    = list(iterable)
 727         self._proxy_at = None
 728         self._mutable  = True
 729
 730     def __getitem__(self, index):
 731         if isinstance(index, Value):
 732             if self._mutable:
 733                 self._proxy_at = tracer.get_src_loc()
 734                 self._mutable  = False
 735             return ArrayProxy(self, index)
 736         else:
 737             return self._inner[index]
 738
 739     def __len__(self):
 740         return len(self._inner)
 741
 742     def _check_mutability(self):
 743         if not self._mutable:
 744             raise ValueError("Array can no longer be mutated after it was indexed with a value "
 745                              "at {}:{}".format(*self._proxy_at))
 746
 747     def __setitem__(self, index, value):
 748         self._check_mutability()
 749         self._inner[index] = value
 750
 751     def __delitem__(self, index):
 752         self._check_mutability()
 753         del self._inner[index]
 754
 755     def insert(self, index, value):
 756         self._check_mutability()
 757         self._inner.insert(index, value)
 758
 759     def __repr__(self):
 760         return "(array{} [{}])".format(" mutable" if self._mutable else "",
 761                                        ", ".join(map(repr, self._inner)))
 762
 763
 764 class ArrayProxy(Value):
 765     def __init__(self, elems, index):
 766         super().__init__(src_loc_at=1)
 767         self.elems = elems
 768         self.index = Value.wrap(index)
 769
 770     def __getattr__(self, attr):
 771         return ArrayProxy([getattr(elem, attr) for elem in self.elems], self.index)
 772
 773     def __getitem__(self, index):
 774         return ArrayProxy([        elem[index] for elem in self.elems], self.index)
 775
 776     def _iter_as_values(self):
 777         return (Value.wrap(elem) for elem in self.elems)
 778
 779     def shape(self):
 780         bits, sign = 0, False
 781         for elem_bits, elem_sign in (elem.shape() for elem in self._iter_as_values()):
 782             bits = max(bits, elem_bits + elem_sign)
 783             sign = max(sign, elem_sign)
 784         return bits, sign
 785
 786     def _lhs_signals(self):
 787         signals = union((elem._lhs_signals() for elem in self._iter_as_values()), start=ValueSet())
 788         return signals
 789
 790     def _rhs_signals(self):
 791         signals = union((elem._rhs_signals() for elem in self._iter_as_values()), start=ValueSet())
 792         return self.index._rhs_signals() | signals
 793
 794     def __repr__(self):
 795         return "(proxy (array [{}]) {!r})".format(", ".join(map(repr, self.elems)), self.index)
 796
 797
 798 class _StatementList(list):
 799     def __repr__(self):
 800         return "({})".format(" ".join(map(repr, self)))
 801
 802
 803 class Statement:
 804     @staticmethod
 805     def wrap(obj):
 806         if isinstance(obj, Iterable):
 807             return _StatementList(sum((Statement.wrap(e) for e in obj), []))
 808         else:
 809             if isinstance(obj, Statement):
 810                 return _StatementList([obj])
 811             else:
 812                 raise TypeError("Object '{!r}' is not an nMigen statement".format(obj))
 813
 814
 815 class Assign(Statement):
 816     def __init__(self, lhs, rhs):
 817         self.lhs = Value.wrap(lhs)
 818         self.rhs = Value.wrap(rhs)
 819
 820     def _lhs_signals(self):
 821         return self.lhs._lhs_signals()
 822
 823     def _rhs_signals(self):
 824         return self.lhs._rhs_signals() | self.rhs._rhs_signals()
 825
 826     def __repr__(self):
 827         return "(eq {!r} {!r})".format(self.lhs, self.rhs)
 828
 829
 830 class Assert(Statement):
 831     def __init__(self, test, _check=None, _en=None):
 832         self.test = Value.wrap(test)
 833
 834         self._check = _check
 835         if self._check is None:
 836             self._check = Signal(reset_less=True, name="$assert$check")
 837             self._check.src_loc = self.test.src_loc
 838
 839         self._en = _en
 840         if _en is None:
 841             self._en = Signal(reset_less=True, name="$assert$en")
 842             self._en.src_loc = self.test.src_loc
 843
 844     def _lhs_signals(self):
 845         return ValueSet((self._en, self._check))
 846
 847     def _rhs_signals(self):
 848         return self.test._rhs_signals()
 849
 850     def __repr__(self):
 851         return "(assert {!r})".format(self.test)
 852
 853
 854 class Assume(Statement):
 855     def __init__(self, test, _check=None, _en=None):
 856         self.test = Value.wrap(test)
 857
 858         self._check = _check
 859         if self._check is None:
 860             self._check = Signal(reset_less=True, name="$assume$check")
 861             self._check.src_loc = self.test.src_loc
 862
 863         self._en = _en
 864         if self._en is None:
 865             self._en = Signal(reset_less=True, name="$assume$en")
 866             self._en.src_loc = self.test.src_loc
 867
 868     def _lhs_signals(self):
 869         return ValueSet((self._en, self._check))
 870
 871     def _rhs_signals(self):
 872         return self.test._rhs_signals()
 873
 874     def __repr__(self):
 875         return "(assume {!r})".format(self.test)
 876
 877
 878 class Switch(Statement):
 879     def __init__(self, test, cases):
 880         self.test  = Value.wrap(test)
 881         self.cases = OrderedDict()
 882         for key, stmts in cases.items():
 883             if isinstance(key, (bool, int)):
 884                 key = "{:0{}b}".format(key, len(self.test))
 885                 assert len(key) <= len(self.test)
 886             elif isinstance(key, str):
 887                 assert len(key) == len(self.test)
 888             else:
 889                 raise TypeError("Object '{!r}' cannot be used as a switch key"
 890                                 .format(key))
 891             if not isinstance(stmts, Iterable):
 892                 stmts = [stmts]
 893             self.cases[key] = Statement.wrap(stmts)
 894
 895     def _lhs_signals(self):
 896         signals = union((s._lhs_signals() for ss in self.cases.values() for s in ss),
 897                         start=ValueSet())
 898         return signals
 899
 900     def _rhs_signals(self):
 901         signals = union((s._rhs_signals() for ss in self.cases.values() for s in ss),
 902                         start=ValueSet())
 903         return self.test._rhs_signals() | signals
 904
 905     def __repr__(self):
 906         cases = ["(case {} {})".format(key, " ".join(map(repr, stmts)))
 907                  for key, stmts in self.cases.items()]
 908         return "(switch {!r} {})".format(self.test, " ".join(cases))
 909
 910
 911 class Delay(Statement):
 912     def __init__(self, interval=None):
 913         self.interval = None if interval is None else float(interval)
 914
 915     def _rhs_signals(self):
 916         return ValueSet()
 917
 918     def __repr__(self):
 919         if self.interval is None:
 920             return "(delay ε)"
 921         else:
 922             return "(delay {:.3}us)".format(self.interval * 10e6)
 923
 924
 925 class Tick(Statement):
 926     def __init__(self, domain="sync"):
 927         self.domain = str(domain)
 928
 929     def _rhs_signals(self):
 930         return ValueSet()
 931
 932     def __repr__(self):
 933         return "(tick {})".format(self.domain)
 934
 935
 936 class Passive(Statement):
 937     def _rhs_signals(self):
 938         return ValueSet()
 939
 940     def __repr__(self):
 941         return "(passive)"
 942
 943
 944 class _MappedKeyCollection(metaclass=ABCMeta):
 945     @abstractmethod
 946     def _map_key(self, key):
 947         pass # :nocov:
 948
 949     @abstractmethod
 950     def _unmap_key(self, key):
 951         pass # :nocov:
 952
 953
 954 class _MappedKeyDict(MutableMapping, _MappedKeyCollection):
 955     def __init__(self, pairs=()):
 956         self._storage = OrderedDict()
 957         for key, value in pairs:
 958             self[key] = value
 959
 960     def __getitem__(self, key):
 961         key = None if key is None else self._map_key(key)
 962         return self._storage[key]
 963
 964     def __setitem__(self, key, value):
 965         key = None if key is None else self._map_key(key)
 966         self._storage[key] = value
 967
 968     def __delitem__(self, key):
 969         key = None if key is None else self._map_key(key)
 970         del self._storage[key]
 971
 972     def __iter__(self):
 973         for key in self._storage:
 974             if key is None:
 975                 yield None
 976             else:
 977                 yield self._unmap_key(key)
 978
 979     def __eq__(self, other):
 980         if not isinstance(other, type(self)):
 981             return False
 982         if len(self) != len(other):
 983             return False
 984         for ak, bk in zip(sorted(self._storage), sorted(other._storage)):
 985             if ak != bk:
 986                 return False
 987             if self._storage[ak] != other._storage[bk]:
 988                 return False
 989         return True
 990
 991     def __len__(self):
 992         return len(self._storage)
 993
 994     def __repr__(self):
 995         pairs = ["({!r}, {!r})".format(k, v) for k, v in self.items()]
 996         return "{}.{}([{}])".format(type(self).__module__, type(self).__name__,
 997                                     ", ".join(pairs))
 998
 999
1000 class _MappedKeySet(MutableSet, _MappedKeyCollection):
1001     def __init__(self, elements=()):
1002         self._storage = OrderedDict()
1003         for elem in elements:
1004             self.add(elem)
1005
1006     def add(self, value):
1007         self._storage[self._map_key(value)] = None
1008
1009     def update(self, values):
1010         for value in values:
1011             self.add(value)
1012
1013     def discard(self, value):
1014         if value in self:
1015             del self._storage[self._map_key(value)]
1016
1017     def __contains__(self, value):
1018         return self._map_key(value) in self._storage
1019
1020     def __iter__(self):
1021         for key in [k for k in self._storage]:
1022             yield self._unmap_key(key)
1023
1024     def __len__(self):
1025         return len(self._storage)
1026
1027     def __repr__(self):
1028         return "{}.{}({})".format(type(self).__module__, type(self).__name__,
1029                                   ", ".join(repr(x) for x in self))
1030
1031
1032 class ValueKey:
1033     def __init__(self, value):
1034         self.value = Value.wrap(value)
1035
1036     def __hash__(self):
1037         if isinstance(self.value, Const):
1038             return hash(self.value.value)
1039         elif isinstance(self.value, Signal):
1040             return hash(self.value.duid)
1041         elif isinstance(self.value, Operator):
1042             return hash((self.value.op, tuple(ValueKey(o) for o in self.value.operands)))
1043         elif isinstance(self.value, Slice):
1044             return hash((ValueKey(self.value.value), self.value.start, self.value.end))
1045         elif isinstance(self.value, Part):
1046             return hash((ValueKey(self.value.value), ValueKey(self.value.offset),
1047                          self.value.width))
1048         elif isinstance(self.value, Cat):
1049             return hash(tuple(ValueKey(o) for o in self.value.operands))
1050         elif isinstance(self.value, ArrayProxy):
1051             return hash((ValueKey(self.value.index),
1052                          tuple(ValueKey(e) for e in self.value._iter_as_values())))
1053         else: # :nocov:
1054             raise TypeError("Object '{!r}' cannot be used as a key in value collections"
1055                             .format(self.value))
1056
1057     def __eq__(self, other):
1058         if type(other) is not ValueKey:
1059             return False
1060         if type(self.value) is not type(other.value):
1061             return False
1062
1063         if isinstance(self.value, Const):
1064             return self.value.value == other.value.value
1065         elif isinstance(self.value, Signal):
1066             return self.value is other.value
1067         elif isinstance(self.value, Operator):
1068             return (self.value.op == other.value.op and
1069                     len(self.value.operands) == len(other.value.operands) and
1070                     all(ValueKey(a) == ValueKey(b)
1071                         for a, b in zip(self.value.operands, other.value.operands)))
1072         elif isinstance(self.value, Slice):
1073             return (ValueKey(self.value.value) == ValueKey(other.value.value) and
1074                     self.value.start == other.value.start and
1075                     self.value.end == other.value.end)
1076         elif isinstance(self.value, Part):
1077             return (ValueKey(self.value.value) == ValueKey(other.value.value) and
1078                     ValueKey(self.value.offset) == ValueKey(other.value.offset) and
1079                     self.value.width == other.value.width)
1080         elif isinstance(self.value, Cat):
1081             return all(ValueKey(a) == ValueKey(b)
1082                         for a, b in zip(self.value.operands, other.value.operands))
1083         elif isinstance(self.value, ArrayProxy):
1084             return (ValueKey(self.value.index) == ValueKey(other.value.index) and
1085                     len(self.value.elems) == len(other.value.elems) and
1086                     all(ValueKey(a) == ValueKey(b)
1087                         for a, b in zip(self.value._iter_as_values(),
1088                                         other.value._iter_as_values())))
1089         else: # :nocov:
1090             raise TypeError("Object '{!r}' cannot be used as a key in value collections"
1091                             .format(self.value))
1092
1093     def __lt__(self, other):
1094         if not isinstance(other, ValueKey):
1095             return False
1096         if type(self.value) != type(other.value):
1097             return False
1098
1099         if isinstance(self.value, Const):
1100             return self.value < other.value
1101         elif isinstance(self.value, Signal):
1102             return self.value.duid < other.value.duid
1103         elif isinstance(self.value, Slice):
1104             return (ValueKey(self.value.value) < ValueKey(other.value.value) and
1105                     self.value.start < other.value.start and
1106                     self.value.end < other.value.end)
1107         else: # :nocov:
1108             raise TypeError("Object '{!r}' cannot be used as a key in value collections")
1109
1110     def __repr__(self):
1111         return "<{}.ValueKey {!r}>".format(__name__, self.value)
1112
1113
1114 class ValueDict(_MappedKeyDict):
1115     _map_key   = ValueKey
1116     _unmap_key = lambda self, key: key.value
1117
1118
1119 class ValueSet(_MappedKeySet):
1120     _map_key   = ValueKey
1121     _unmap_key = lambda self, key: key.value
1122
1123
1124 class SignalKey:
1125     def __init__(self, signal):
1126         if type(signal) is not Signal:
1127             raise TypeError("Object '{!r}' is not an nMigen signal".format(signal))
1128         self.signal = signal
1129
1130     def __hash__(self):
1131         return hash(self.signal.duid)
1132
1133     def __eq__(self, other):
1134         if type(other) is not SignalKey:
1135             return False
1136         return self.signal is other.signal
1137
1138     def __lt__(self, other):
1139         if type(other) is not SignalKey:
1140             raise TypeError("Object '{!r}' cannot be compared to a SignalKey".format(signal))
1141         return self.signal.duid < other.signal.duid
1142
1143     def __repr__(self):
1144         return "<{}.SignalKey {!r}>".format(__name__, self.signal)
1145
1146
1147 class SignalDict(_MappedKeyDict):
1148     _map_key   = SignalKey
1149     _unmap_key = lambda self, key: key.signal
1150
1151
1152 class SignalSet(_MappedKeySet):
1153     _map_key   = SignalKey
1154     _unmap_key = lambda self, key: key.signal