summaryrefslogtreecommitdiff
path: root/chain/src/item/mod.rs
blob: 7fafcc824a751abede61a907ef50923b6f8d18a3 (plain)
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
#![warn(missing_docs)]
//! This module implements the type of items for the chain-rule
//! machine.
//!
//! More specifically, it implements the iten derivation forests for
//! the machine.

// TODO: Implement an enumeration for Parent or Segment, perhaps
// called PaSe.

// TODO: Move functions for handling forests, currently contained
// within the method derive to this module, and make them aware of the
// enumeration PaSe.

// TODO: Implement the Item trait from semirings for the item
// derivation forest, and then we can easily execute items later on.

use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph};

use core::borrow::Borrow;

/// A parent or a segment.
///
/// A parent is a node with an edge index, which represents a certain
/// edge.
///
/// A segment represents every edge from the root node to the single
/// terminating node.
#[allow(unused)]
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub enum PaSe {
    /// An edge from a node, as the n-th child.
    Parent(usize, usize),
    /// A segment from a root to the single terminating node.
    Segment(usize, usize),
}

impl From<Parent> for PaSe {
    fn from(value: Parent) -> Self {
        Self::Parent(value.node(), value.edge())
    }
}

impl Default for PaSe {
    fn default() -> Self {
        Self::Segment(0, 0)
    }
}

impl core::fmt::Display for PaSe {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Parent(node, edge) => write!(f, "the {edge}-th edge from {node}"),
            Self::Segment(root, leaf) => write!(f, "a segment from {root} to {leaf}"),
        }
    }
}

impl PaSe {
    fn parent(self) -> Option<Parent> {
        if let Self::Parent(node, edge) = self {
            Some(Parent::new(node, edge))
        } else {
            None
        }
    }

    fn segment(self) -> Option<(usize, usize)> {
        if let Self::Segment(root, leaf) = self {
            Some((root, leaf))
        } else {
            None
        }
    }
}

/// An internal type that indicates the status of a node as either a
/// packed, cloned, or plain node.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
enum ForestLabelType {
    Packed,
    #[default]
    Plain,
    Cloned(usize),
}

impl core::fmt::Display for ForestLabelType {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            Self::Packed => write!(f, "packed"),
            Self::Plain => write!(f, "plain"),
            Self::Cloned(index) => write!(f, "the {index}-th clone"),
        }
    }
}

/// A type that encodes the properties demanded by a forest.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct ForestLabel<T: GraphLabel> {
    label: T,
    status: ForestLabelType,
}

impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        writeln!(f, "label: {}, status: {}", self.label, self.status)
    }
}

/// The type of erros for converting forest labels.
#[non_exhaustive]
#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub enum ForestLabelError {
    /// Try to pack a cloned node.
    PackClone,
    /// Try to clone a packed node.
    ClonePack,
}

impl core::fmt::Display for ForestLabelError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            Self::PackClone => write!(f, "cannot pack a cloned node"),
            Self::ClonePack => write!(f, "cannot clone a packed node"),
        }
    }
}

impl std::error::Error for ForestLabelError {}

impl<T: GraphLabel> ForestLabel<T> {
    /// Retrieve the label.
    pub fn label(&self) -> T {
        self.label
    }

    /// Return true if and only if this node is packed.
    pub fn is_packed(&self) -> bool {
        matches!(self.status, ForestLabelType::Packed)
    }

    /// Retrieve the optional clone index.
    pub fn clone_index(&self) -> Option<usize> {
        match self.status {
            ForestLabelType::Cloned(index) => Some(index),
            _ => None,
        }
    }

    /// Try to clone a node.
    pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
    where
        F: Forest<T>,
    {
        if self.is_packed() {
            Err(ForestLabelError::ClonePack)
        } else {
            let clone_index = if let Some(old_index) = self.clone_index() {
                let mut new_index: usize = old_index + 1;

                let mut new_label = Self {
                    status: ForestLabelType::Cloned(new_index),
                    ..self
                };

                while forest.query_label(new_label).is_some() {
                    new_index += 1;
                    new_label = Self {
                        status: ForestLabelType::Cloned(new_index),
                        ..self
                    };
                }

                new_index
            } else {
                0
            };

            Ok(Self {
                status: ForestLabelType::Cloned(clone_index),
                ..self
            })
        }
    }

    /// Try to pack a node.
    pub fn pack(self) -> Result<Self, ForestLabelError> {
        if self.clone_index().is_some() {
            Err(ForestLabelError::PackClone)
        } else {
            let new_label = Self {
                status: ForestLabelType::Packed,
                ..self
            };

            Ok(new_label)
        }
    }
}

impl<T: GraphLabel> From<T> for ForestLabel<T> {
    fn from(label: T) -> Self {
        let status = ForestLabelType::default();
        Self { label, status }
    }
}

/// The expected behaviours of an item derivation forest.
///
/// Note that it requires only a subset of the functionalities of
/// labelled graphs.
pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
    /// The type of errors for operations on the forest.
    type Error: std::error::Error + From<GError> + From<ForestLabelError>;

    /// Return the root of the forest.
    ///
    /// A forest without a root is regarded as empty.
    fn root(&self) -> Option<usize>;

    /// Construct a forest consisting of one leaf node with the given
    /// label.
    fn new_leaf(label: T) -> Self;

    /// Detect if the fragment is a prefix of the sub-forest rooted at
    /// `node_id`.
    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
    where
        F: Borrow<Self>;

    /// Extend the forest by adjoining another forest at a given node.
    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
    where
        F: Borrow<Self>;

    /// Clone a node by making a new node and making all the nodes
    /// that previously pointed to the old node now point to the new
    /// node, and the new node points to the old node.  Return the
    /// index of the new node.  In addition, if the old node had
    /// already been cloned, just return the index of its
    /// representative.
    ///
    /// The labels of the representing node and of the cloned node
    /// will be handled automatically.
    fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>;
}

pub mod default;

pub mod genins;

pub use genins::generate_fragment;