ordec.core.ordb — Functional, relational, schema-based data model

ORDB is the core of ORDeC’s internal data model. It provides a functional, relational, schema-based mechanism to represent IC design data such as schematics, symbols, layouts and simulation results. IC design data is structured in subgraphs (Subgraph), which can comprise many nodes (Node) including a single special root node (SubgraphRoot). Nodes can reference other nodes within the same subgraph (LocalRef) or in other subgraphs (ExternalRef in combination with SubgraphRef). ORDB is primarily a in-memory database. Serialization and network support is planned but not currently implemented.

An example subgraph might represent a schematic comprising multiple nets, ports, drawn wires and symbol instances.

For a practical demonstration, view ORDB Demo.

ORDB is based on five principles:

1. Schema-based: ORDB design data must conform to a predefined schema, which defines a set of node types (tables) with attributes (columns), including relations between nodes. See Schema: nodes and attributes for details.

2. Relational queries: ORDB supports a basic form of relational queries and can loosely be seen as relational database. When node A references node B through a LocalRef attribute, this reference can not only be followed from A to B but also in the reverse direction from B to A, without having to explicitly add a second reference in the opposite direction. This is especially important in 1:n relations, where the reference by convention is always stored at the ‘1’ side, never at the ‘n’ side. Relational queries are powered by automatic indices.

3. Hierarchical tree organization: Names can be assigned to nodes. Those names can be arranged hierarchically in a tree. This makes it possible to group design objects in arrays, structs or other logical units.

4. Persistent data structures: The state of a ORDB subgraph is stored using persistent data structures (from the Pyrsistent library). Persistent data structures are immutable.

   Modifying a subgraph (i.e. adding, updating or removing nodes) replaces its old state with a new state, which is built upon the previous state. The old subgraph state remains unchanged. Due to this, logical copies of subgraphs are very cheap, as the underlying data structures are immutable and thus do not need to be copied.

   Persistence allows highly similar subgraphs to share memory. Examples: very similar symbols such as resistors with different values where only captions differ; evolving a schematic or layout for cross-technology mapping; placement or routing steps that evolve layouts; power grid generation; separate copies of the SimHierarchy when performing different simulations; reverting incremental changes.

5. Mutable and immutable interfaces: While constructing or transforming a subgraph, a mutable interface is used, which hides the aforementioned immutability and persistence. At functional boundaries, subgraphs can be frozen (made immutable). Frozen subgraphs are read-only and cannot be accidentally modified. Functions that return frozen subgraphs are well-suited for return value caching / memoization. For example, we can generate a Symbol once and then use it at many occasions. Side effects between independent users of the same frozen subgraph are eliminated.

Before the current design of ORDB, some other ideas were evaluated but discarded: ORDeC’s first data model layer was schema-based and had mutable and immutable interfaces, but lacked persistence and support for relational queries. Another alternative to the current ORDB could be an in-memory global relational database for each IC design. Such a system would be schema-based and support relational queries, but it would not provide a mutable and immutable interfaces on subgraph level (and the resulting functional encapsulation) and lack the advantages of persistent data structures. Lastly, plain Python objects, frozen dataclasses or similar approaches lack relational queries, mutable and immutable interfaces on subgraph level and persistence.

Schema: nodes and attributes

A schema defines node types and their attributes, including the special SubgraphRoot node types, of which there is exactly one per subgraph. As an example, see the following excerpt of ORDeC’s full schema for IC design data (ordec.core.schema):

class Symbol(SubgraphRoot):
    outline = Attr(Rect4R)

class Pin(Node):
    pintype = Attr(PinType, default=PinType.Inout)
    pos     = Attr(Vec2R)
    align   = Attr(D4, default=D4.R0)

Attribute values must be hashable and should be immutable. Thus, lists and dicts cannot be attributes. To take advantage of ORDB’s capabilities, it is also strongly encouraged to use atomic attributes rather than compound types (first normal form).

class ordec.core.ordb.Attr(type: type, default=None, optional: bool = True, factory: Callable = None, typecheck_custom: Callable = None)

Defines a node attribute of a primitive type such as string, int or Vec2R.

Parameters:

• type – Defines the type of attribute values.

• default – Default attribute value.

• factory – Function applied to each value before assignment to attribute.

• typecheck_custom – If this argument is not provided, type checking is performed through isinstance(val, type). If it is provided, typecheck_custom is called with val instead of the default type check. This is for example used in NPath to support both int and str values.

• name (str) – Name of the attribute.

indices

list of all indices associated with attribute

Type:

list[GenericIndex]

class ordec.core.ordb.LocalRef(refs_ntype: type, optional: bool = True, factory: Callable = None, refcheck_custom: Callable = None)

Defines a node attribute referencing a node within the same subgraph. The reference is internally stored as integer nid. The Node interface hides the nid in two ways: On reading the LocalRef attribute, the Node object is returned instead of a nid. Node objects of the same subgraph can also be assigned directly to the attribute.

Parameters:

• refs_ntype – The Node subclass that this reference points to.

• optional – Specifies whether the reference can be None.

Note

In one instance, the above recommendation that attribute values should be immutable and primitive is violated: The ‘cell’ attribute of some SubgraphRoot classes such as ordec.core.schema.Schematic reference instances of ordec.core.cell.Cell, which are hashable but potentially mutable. The ‘cell’ attributes are currently needed to resolve symbols to schematics.

References to nodes within another subgraph require two attributes: a reference to another subgraph (ordec.core.ordb.SubgraphRef) and a reference to the the node within that subgraph (ordec.core.ordb.ExternalRef).

class ordec.core.ordb.SubgraphRef(type: type, default=None, optional: bool = True, factory: Callable = None, typecheck_custom: Callable = None)

References another subgraph. Can serve as base reference for zero or more ordec.core.ordb.ExternalRef attributes.

Either a SubgraphRoot or a FrozenSubgraph can be assigned to a SubgraphRef. Reading a SubgraphRef always returns a SubgraphRoot object.

The referenced subgraph must be frozen.

Parameters:

type – SubgraphRoot class of the referenced subgraph.

class ordec.core.ordb.ExternalRef(refs_ntype: type, of_subgraph: Callable[[Node], SubgraphRoot], optional: bool = True)

References a node in another subgraph.

Each ExternalRef is resolved using a corresponding SubgraphRef. The corresponding SubgraphRef can be an attribute of the same node or of another node. The of_subgraph argument defines which SubgraphRef corresponds to the ExternalRef.

Parameters:

• refs_ntype – The referenced node type.

• of_subgraph – Function receiving the current node as argument and returning the SubgraphRoot of the referenced subgraph by reading the SubgraphRef that corresponds to this instance of the ExternalRef.

• optional – Specifies whether the reference can be None.

Attributes are always defined as part of a Node subclass.

Each node instance (row) has a node ID (nid) that identifies it uniquely within its subgraph. Both nodes inside the subgraph and nodes in other subgraphs can use this nid to reference the node (LocalRef and ExternalRef).

class ordec.core.ordb.Node(**kwargs)

Subclass this class to define own node types (tables) for ORDB.

Calling/instantiating a Node subclass X does not return an object of type X, but an object of type X.Tuple, which is a implicitly created subclass of NodeTuple. A corresponding X object is only obtained when the the X.Tuple object is attached to a subgraph, for example using the modulo (‘%’) operator.

Node objects provides a cursor-like access layer to the NodeTuple objects that are stored within Subgraph objects. They are 3-tuples (subgraph, nid, npath_nid).

The hash() and == behviour of Node is implemented by tuple.__hash__ and tuple.__eq__. It relies on the hash() and == behavior of MutableSubgraph (for MutableNodes) or FrozenSubgraph (for FrozenNodes).

Tuple: type[NodeTuple]

auto-generated subclass of NodeTuple

Mutable: type[MutableNode]

auto-generated subclass of this Node subclass and MutableNode

Frozen: type[FrozenNode]

auto-generated subclass of this Node subclass and FrozenNode

property subgraph: Subgraph

The subgraph of the selected node.

property nid: int | None

The node ID (nid) of the selected node.

property tuple: NodeTuple

The node’s raw NodeTuple stored in subgraph.

property npath_nid: int | None

The nid of the NPath node matching the selected node.

property npath: Tuple

The raw NPath.Tuple matching the selected node.

full_path_list() → list[str | int]

Hierarchial path of the selected node in NPath hierarchy as list.

full_path_str() → str

Hierarchial path of the selected node in NPath hierarchy as string.

property parent: Node

Parent node of selected node in NPath hierarchy.

update(**kwargs)

Each key, value argument pair updates the attribute key of the selected node to the provided value.

update_byattr(attr: Attr, value)

Update single attribute to specified value.

remove()

Removes selected node from subgraph, including NPath if applicable.

remove_node(sgu: SubgraphUpdater)

Removes selected node from subgraph, exluding potential NPath.

replace(inserter: Inserter)

Replaces the current node with a one newly inserted by provided inserter, reusing the nid as primary_nid to the inserter. By reusing the nid, existing NPaths and LocalRefs should be left intact.

property root: SubgraphRoot

Returns SubgraphRoot of the selected subgraph.

property mutable: bool

Returns whether the selected subgraph is mutable.

ctx()

Return a Context for use as a context manager: with node.ctx(): ...

class ordec.core.ordb.NonLeafNode(**kwargs)

Bases: Node

NonLeafNodes differ from other Nodes in that they can have children in the NPath hierarchy.

mkpath(k: str | int, ref=None)

Create empty NPath ‘k’ below selected node.

Deprecated since version Use: x.name = PathNode() (string key) or x[i] = PathNode() (integer key) instead.

children() → Iterable[Node]

Iterate over direct children in the NPath hierarchy.

class ordec.core.ordb.SubgraphRoot(**kwargs)

Bases: NonLeafNode

Each subgraph has a single SubgraphRoot node. The subclass of SubgraphRoot defines what kind of design data the subgraph represents.

updater() → SubgraphUpdater

Convenience wrapper for Subgraph.updater().

cursor_at(*args, **kwargs) → Node

Convenience wrapper for Subgraph.cursor_at().

all(*args, **kwargs) → Iterable[Node]

Convenience wrapper for Subgraph.all().

one(*args, **kwargs) → Node

Convenience wrapper for Subgraph.one().

matches(other)

Convenience wrapper for Subgraph.matches().

freeze()

Convenience wrapper for Subgraph.freeze().

thaw()

Convenience wrapper for Subgraph.thaw().

mutable_copy()

Convenience wrapper for Subgraph.mutable_copy().

tables(html=False) → str

Convenience wrapper for Subgraph.tables().

dump() → str

Convenience wrapper for Subgraph.dump().

copy() → Self

For convenience, SubgraphRoot.copy and SubgraphRoot.__copy__ copy the Subgraph itself (deep copy) and return the root cursor of the new subgraph.

Every SubgraphRoot is a subclass of NonLeafNode, i.e. SubgraphRoots always support child nodes:

The classes ordec.core.ordb.MutableNode and ordec.core.ordb.FrozenNode have an auxiliary function as base class for Node.Mutable and Node.Frozen.

class ordec.core.ordb.MutableNode(**kwargs)

Auxiliary base class for auto-generated Node.Mutable classes.

class ordec.core.ordb.FrozenNode(**kwargs)

Auxiliary base class for auto-generated Node.Frozen classes.

The following inheritance diagram around ordec.core.schema.Net exemplifies their role:

Note that the class ordec.core.schema.Net itself will never be instantiated. Instead, either Net.Frozen or Net.Mutable will be used, depending on whether a FrozenSubgraph or a MutableSubgraph is selected.

Inserters & indices

class ordec.core.ordb.Inserter

class ordec.core.ordb.FuncInserter(inserter_func)

class ordec.core.ordb.GenericIndex

abstractmethod index_add(sgu: SubgraphUpdater, node, nid)

This method must not fail on constraint violations!

abstractmethod index_remove(sgu: SubgraphUpdater, node, nid)

This method must not fail on constraint violations!

class ordec.core.ordb.Index(attr: Attr, unique: bool = False, sortkey: Callable = None)

query(key) → IndexQuery

Returns IndexQuery object for equivalence query with key.

class ordec.core.ordb.CombinedIndex(attrs: list[Attr], unique: bool = False, sortkey: Callable = None)

class ordec.core.ordb.IndexQuery(index_key: IndexKey)

Pass IndexQuery objects to SubgraphRoot.all() or SubgraphRoot.one() to run query on a specific subgraph.

Low-level stuff

class ordec.core.ordb.NodeTuple(**kwargs)

NodeTuples store the node data of a subgraph in Subgraph.nodes. It is recommended to acccess NodeTuples via the Node interface.

index_ntype = <ordec.core.ordb.NTypeIndex object>

Subgraph-wide index of nodes by their type (table)

Note

NodeTuple is a custom tuple subclass. Some alternatives to this were considered but discarded:

• NamedTuple classes do not support default values and cannot be subclassed, as they are not normal classes.

• For pyrsistent.PClass, the behaviour of field() is difficult to change without touching everything. Also, the performance overhead of mutating pyrsistent.PClass seems a bit high, just from reading its code. A downside of the current tuple subclass or NamedTuple compared to PClass is that all attribute references must be copied when a single attribute is updated, but this is probably not an issue as long as the number of attributes remains low.

• recordclass.dataobject would be an additional fragile dependency, and its readonly=True option seems to be a (buggy) afterthought only.

• pydantic is too heavyweight.

class ordec.core.ordb.Subgraph

node_dict(mode='canonical') → dict[int, NodeTuple]

Returns an ordered dict of nodes (values) by their nids (keys).

Parameters:

mode – If ‘canonical’, the return dict is ordered by nid. If ‘pretty’, the return dict is ordered by node type and nid.

matches(other: Subgraph) → bool

Check whether two subgraphs match regardless of nid numbers. While the nids and LocalRefs are ignored, the nid order (i.e. insertion order) must match for equivalence.

This operation is based on canonical node lists.

TODO: It is not clear whether this function is needed at all. Furthermore, ExternalRefs are not handled.

property nodes: PMap

A persistent mapping of nids to NodeTuple instances.

property index: PMap

A persistent mapping of index keys to index values.

property nid_alloc: range

An allocation range from which new nids must be generated.

property root_cursor: Node

Root cursor pointing to subgraph root.

abstract property mutable: bool

Returns True if Subgraph is mutable, False if frozen.

abstractmethod freeze() → FrozenSubgraph

Create FrozenSubgraph from MutableSubgraph. Future modifications of the original MutableSubgraph are not visible at the FrozenSubgraph.

abstractmethod thaw() → MutableSubgraph

Create MutableSubgraph from FrozenSubgraph. Future modifications of the MutableSubgraph are not visible at the original FrozenSubgraph.

abstractmethod mutable_copy() → MutableSubgraph

Create MutableSubgraph copy. Future modifications of the MutableSubgraph are not visible at the original FrozenSubgraph.

abstractmethod copy() → Self

Returns a copy of the subgraph.

abstractmethod mutate(nodes, index, nid_alloc)

Low-level function used by SubgraphUpdater to update state of MutableSubgraph.

add(node: Inserter) → int

Inserts node and returns nid.

class ordec.core.ordb.MutableSubgraph

Bases: Subgraph

MutableSubgraph does not override object.__eq__ and object.__hash__. Thus, hash() and == behavior is based purely on the id() / address of a MutableSubgraph. In contrast to the FrozenSubgraphs, a copy of a MutableSubgraph is not equal to the original and has a different hash.

An alternative approach here would be to use the same __eq__ as FrozenSubgraph does. In this case, we would end up with with an unhashable type, which we can for example not use as key in dictionaries. We want MutableSubgraphs and MutableNodes (which reference MutableSubgraphs) to be hashable. Therefore, the default object behavior is the one that seems most sensible.

To compare two MutableSubgraphs a and b for internal equivalence, either do a.freeze() == b.freeze() or subgraphs_match(a, b).

class ordec.core.ordb.FrozenSubgraph(subgraph)

Bases: Subgraph

FrozenSubgraph has custom __hash__ and __eq__ methods, which treat subgraphs with the equal nodes and nid_alloc as equal. Thus, its hash() and == behavior matches that of immutable types like tuple and str. ‘index’ is not checked for equivalence, as it should be equal by construction.

class ordec.core.ordb.SubgraphUpdater(target_subgraph: Subgraph)

A SubgraphUpdater collects changes to a subgraph as a kind of transaction. The SubgraphUpdater is used in a ‘with’ context. When this context is exited, the current state of SubgraphUpdater is checked for consistency. When no problem is found, the MutableSubgraph from which the SubgraphUpdater was created is updated.

NPath and PathNode implement the path hierarchy of subgraphs:

class ordec.core.ordb.NPath(**kwargs)

NPath.Tuple is used to build a subgraph’s path hierarchy. NPath itself (rather than NPath.Tuple) is never instantiated. Instead, reference an empty path (NPath with ref = None) use PathNode. Non-empty paths (NPath.Tuple X with X.ref is not None) are referenced through the Node class correponding to X.ref.

class ordec.core.ordb.PathNode(**kwargs)

PathNode represents an empty path of a subgraph. Its selected nid is None, but it selects some path_nid.

PathNode.Tuple has always length zero and is never inserted into a subgraph.

Exceptions

class ordec.core.ordb.OrdbException

Base class for all ORDB custom exceptions.

class ordec.core.ordb.QueryException

Bases: OrdbException

Raised when a query fails.

class ordec.core.ordb.ModelViolation

Bases: OrdbException

Raised when a data integrity condition is violated, e.g. UniqueViolation, DanglingLocalRef.

class ordec.core.ordb.UniqueViolation(index: GenericIndex, value: tuple)

Bases: ModelViolation

Exception raised when a unique constraint is violated.

class ordec.core.ordb.DanglingLocalRef(nid: int)

Bases: ModelViolation

Exception raised when a LocalRef attribute ends up referencing an inexistent nid.

Design patterns

There are two ways to build upon an immutable subgraph: The subgraph can be thawed and modified, or a new subgraph that references it can be created, keeping the original subgraph immutable.