tket 0.18.0

Quantinuum's TKET Quantum Compiler
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//! Dataflow analysis of Hugrs.

mod datalog;
pub use datalog::Machine;
mod value_row;

mod results;
pub use results::{AnalysisResults, TailLoopTermination};

mod partial_value;
pub use partial_value::{AbstractValue, AsConcrete, LoadedFunction, PartialSum, PartialValue, Sum};

use hugr_core::ops::constant::OpaqueValue;
use hugr_core::ops::{ExtensionOp, Value};

/// Clients of the dataflow framework (particular analyses, such as constant folding)
/// must implement this trait (including providing an appropriate domain type `V`).
pub trait DFContext<V>: ConstLoader<V> {
    /// Given lattice values for each input, update lattice values for the (dataflow) outputs.
    /// For extension ops only, excluding [`MakeTuple`] and [`UnpackTuple`] which are handled automatically.
    /// `_outs` is an array with one element per dataflow output, each initialized to [`PartialValue::Top`]
    /// which is the correct value to leave if nothing can be deduced about that output.
    /// (The default does nothing, i.e. leaves `Top` for all outputs.)
    ///
    /// [`MakeTuple`]: hugr_core::extension::prelude::MakeTuple
    /// [`UnpackTuple`]: hugr_core::extension::prelude::UnpackTuple
    fn interpret_leaf_op(
        &mut self,
        _node: Self::Node,
        _e: &ExtensionOp,
        _ins: &[PartialValue<V, Self::Node>],
        _outs: &mut [PartialValue<V, Self::Node>],
    ) {
    }
}

/// A location where a [Value] could be find in a Hugr. That is,
/// (perhaps deeply nested within [`Value::Sum`]s) within a node `N`
/// that is a [Const](hugr_core::ops::Const).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum ConstLocation<'a, N> {
    /// The specified-index'th field of the [`Value::Sum`] constant identified by the RHS
    Field(usize, &'a ConstLocation<'a, N>),
    /// The entire ([`Const::value`](hugr_core::ops::Const::value)) of the node.
    Node(N),
}

impl<N> From<N> for ConstLocation<'_, N> {
    fn from(value: N) -> Self {
        ConstLocation::Node(value)
    }
}

/// Trait for loading [`PartialValue`]s from constant [Value]s in a Hugr.
///
/// Implementors will likely want to override [`Self::value_from_opaque`]:
/// the default is "correct" but maximally conservative (minimally informative).
pub trait ConstLoader<V> {
    /// The type of nodes in the Hugr.
    type Node;

    /// Produces an abstract value from an [`OpaqueValue`], if possible.
    /// The default just returns `None`, which will be interpreted as [`PartialValue::Top`].
    fn value_from_opaque(&self, _loc: ConstLocation<Self::Node>, _val: &OpaqueValue) -> Option<V> {
        None
    }
}

/// Produces a [`PartialValue`] from a constant.
///
/// Traverses [Sum](Value::Sum) constants to their [`Value::Extension`] leaves,
/// converts these using [`ConstLoader::value_from_opaque`],
/// and builds nested [`PartialValue::new_variant`] to represent the structure.
pub fn partial_from_const<'a, V, CL: ConstLoader<V>>(
    cl: &CL,
    loc: impl Into<ConstLocation<'a, CL::Node>>,
    cst: &Value,
) -> PartialValue<V, CL::Node>
where
    CL::Node: 'a,
{
    let loc = loc.into();
    match cst {
        Value::Sum(hugr_core::ops::constant::Sum { tag, values, .. }) => {
            let elems = values
                .iter()
                .enumerate()
                .map(|(idx, elem)| partial_from_const(cl, ConstLocation::Field(idx, &loc), elem));
            PartialValue::new_variant(*tag, elems)
        }
        Value::Extension { e } => cl
            .value_from_opaque(loc, e)
            .map_or(PartialValue::Top, PartialValue::from),
    }
}

/// A row of inputs to a node contains bottom (can't happen, the node
/// can't execute) if any element [`contains_bottom`](PartialValue::contains_bottom).
pub fn row_contains_bottom<'a, V: 'a, N: 'a>(
    elements: impl IntoIterator<Item = &'a PartialValue<V, N>>,
) -> bool {
    elements.into_iter().any(PartialValue::contains_bottom)
}

#[cfg(test)]
mod test;