swh_graph/
graph_builder.rs

1/*
2 * Copyright (C) 2024-2026  The Software Heritage developers
3 * See the AUTHORS file at the top-level directory of this distribution
4 * License: GNU General Public License version 3, or any later version
5 * See top-level LICENSE file for more information
6 */
7
8//! Utility to dynamically build a small graph in memory
9
10use std::collections::{HashMap, HashSet};
11use std::io::Write;
12
13use anyhow::{bail, ensure, Context, Result};
14use itertools::Itertools;
15use sux::traits::bit_vec_ops::{BitVecOps, BitVecOpsMut};
16use webgraph::graphs::vec_graph::LabeledVecGraph;
17
18use crate::graph::*;
19use crate::labels::{
20    Branch, DirEntry, EdgeLabel, LabelNameId, Permission, UntypedEdgeLabel, Visit, VisitStatus,
21    VisitType,
22};
23use crate::properties;
24use crate::views::{GraphAccessRecord, GraphSpy, PropertyAccess};
25use crate::SwhGraphProperties;
26use crate::{NodeType, SWHID};
27
28/// How to sort label names in the produced graph. Defaults to `Lexicographic`.
29#[derive(Default, Clone, Copy, Debug)]
30pub enum LabelNamesOrder {
31    #[default]
32    /// Sort label names in their lexicographic order, as for graphs compressed with Rust
33    /// (2023-09-06 and newer)
34    Lexicographic,
35    /// Sort label names in the lexicographic order of their base64-encoding, as for graphs
36    /// compressed with Java (2022-12-07 and older)
37    LexicographicBase64,
38}
39
40// Type (alias) of the graph built by the graph builder
41pub type BuiltGraph = SwhBidirectionalGraph<
42    SwhGraphProperties<
43        properties::VecMaps,
44        properties::VecTimestamps,
45        properties::VecPersons,
46        properties::VecContents,
47        properties::VecStrings,
48        properties::VecLabelNames,
49    >,
50    LabeledVecGraph<Vec<u64>>,
51    LabeledVecGraph<Vec<u64>>,
52>;
53
54/// Dynamically builds a small graph in memory
55///
56/// # Examples
57///
58/// ## Directories and contents
59///
60/// ```
61/// use swh_graph::swhid;
62/// use swh_graph::graph_builder::GraphBuilder;
63/// use swh_graph::labels::Permission;
64///
65/// let mut builder = GraphBuilder::default();
66/// let a = builder
67///     .node(swhid!(swh:1:dir:0000000000000000000000000000000000000010)).unwrap()
68///     .done();
69/// let b = builder
70///     .node(swhid!(swh:1:dir:0000000000000000000000000000000000000020)).unwrap()
71///     .done();
72/// let c = builder
73///     .node(swhid!(swh:1:cnt:0000000000000000000000000000000000000030)).unwrap()
74///     .done();
75/// builder.dir_arc(a, b, Permission::Directory, b"tests");
76/// builder.dir_arc(a, c, Permission::ExecutableContent, b"run.sh");
77/// builder.dir_arc(b, c, Permission::Content, b"test.c");
78/// let _ = builder.done().unwrap();
79/// ```
80///
81/// # Revisions and releases
82///
83/// ```
84/// use swh_graph::swhid;
85///
86/// use swh_graph::graph_builder::GraphBuilder;
87/// let mut builder = GraphBuilder::default();
88/// let a = builder
89///     .node(swhid!(swh:1:rev:0000000000000000000000000000000000000010)).unwrap()
90///     .author_timestamp(1708950743, 60)
91///     .done();
92/// let b = builder
93///     .node(swhid!(swh:1:rev:0000000000000000000000000000000000000020)).unwrap()
94///     .committer_timestamp(1708950821, 120)
95///     .done();
96/// builder.arc(a, b);
97/// let _ = builder.done().unwrap();
98/// ```
99#[derive(Clone, Debug, Default)]
100pub struct GraphBuilder {
101    pub label_names_order: LabelNamesOrder,
102
103    name_to_id: HashMap<Vec<u8>, u64>,
104    persons: HashMap<Vec<u8>, u32>,
105
106    arcs: Vec<((NodeId, NodeId), Option<EdgeLabel>)>,
107
108    swhids: Vec<SWHID>,
109    is_skipped_content: Vec<bool>,
110    content_lengths: Vec<Option<u64>>,
111    author_ids: Vec<Option<u32>>,
112    committer_ids: Vec<Option<u32>>,
113    messages: Vec<Option<Vec<u8>>>,
114    tag_names: Vec<Option<Vec<u8>>>,
115    author_timestamps: Vec<Option<i64>>,
116    author_timestamp_offsets: Vec<Option<i16>>,
117    committer_timestamps: Vec<Option<i64>>,
118    committer_timestamp_offsets: Vec<Option<i16>>,
119    label_names: Vec<Vec<u8>>,
120}
121
122impl GraphBuilder {
123    /// Adds a node to the graph.
124    ///
125    /// Returns `Err` if there is already a node with this SWHID.
126    pub fn node(&mut self, swhid: SWHID) -> Result<NodeBuilder<'_>> {
127        ensure!(!self.swhids.contains(&swhid), "Duplicate SWHID {swhid}");
128        let node_id = self.swhids.len();
129        self.swhids.push(swhid);
130        self.is_skipped_content.push(false);
131        self.content_lengths.push(None);
132        self.author_ids.push(None);
133        self.committer_ids.push(None);
134        self.messages.push(None);
135        self.tag_names.push(None);
136        self.author_timestamps.push(None);
137        self.author_timestamp_offsets.push(None);
138        self.committer_timestamps.push(None);
139        self.committer_timestamp_offsets.push(None);
140        Ok(NodeBuilder {
141            node_id,
142            graph_builder: self,
143        })
144    }
145
146    /// Returns `NodeId` that represents this SWHID in the graph, if it exists
147    #[inline(always)]
148    pub fn node_id(&self, swhid: SWHID) -> Option<NodeId> {
149        self.swhids.iter().position(|x| *x == swhid)
150    }
151
152    /// Adds an unlabeled arc to the graph
153    pub fn arc(&mut self, src: NodeId, dst: NodeId) {
154        self.arcs.push(((src, dst), None));
155    }
156
157    /// Adds a labeled dir->{cnt,dir,rev} arc to the graph
158    pub fn dir_arc<P: Into<Permission>, N: Into<Vec<u8>>>(
159        &mut self,
160        src: NodeId,
161        dst: NodeId,
162        permission: P,
163        name: N,
164    ) {
165        let permission = permission.into();
166        let name = name.into();
167        let name_id = *self.name_to_id.entry(name.clone()).or_insert_with(|| {
168            self.label_names.push(name);
169            (self.label_names.len() - 1)
170                .try_into()
171                .expect("label_names length overflowed u64")
172        });
173        self.l_arc(
174            src,
175            dst,
176            DirEntry::new(permission, LabelNameId(name_id))
177                .expect("label_names is larger than 2^61 items"),
178        );
179    }
180
181    /// Adds a labeled snp->{cnt,dir,rev,rel} arc to the graph
182    pub fn snp_arc<N: Into<Vec<u8>>>(&mut self, src: NodeId, dst: NodeId, name: N) {
183        let name = name.into();
184        let name_id = *self.name_to_id.entry(name.clone()).or_insert_with(|| {
185            self.label_names.push(name);
186            (self.label_names.len() - 1)
187                .try_into()
188                .expect("label_names length overflowed u64")
189        });
190        self.l_arc(
191            src,
192            dst,
193            Branch::new(LabelNameId(name_id)).expect("label_names is larger than 2^61 items"),
194        );
195    }
196
197    /// Adds a labeled ori->snp arc to the graph
198    pub fn ori_arc(
199        &mut self,
200        src: NodeId,
201        dst: NodeId,
202        status: VisitStatus,
203        timestamp: u64,
204        visit_type: VisitType,
205    ) {
206        self.l_arc(
207            src,
208            dst,
209            Visit::new(status, timestamp, visit_type).expect("invalid timestamp"),
210        );
211    }
212
213    /// Adds a labeled arc to the graph
214    pub fn l_arc<L: Into<EdgeLabel>>(&mut self, src: NodeId, dst: NodeId, label: L) {
215        self.arcs.push(((src, dst), Some(label.into())));
216    }
217
218    #[allow(clippy::type_complexity)]
219    pub fn done(&self) -> Result<BuiltGraph> {
220        let num_nodes = self.swhids.len();
221        let mut seen = sux::prelude::BitVec::new(num_nodes);
222        for ((src, dst), _) in self.arcs.iter() {
223            seen.set(*src, true);
224            seen.set(*dst, true);
225        }
226        for node in 0..num_nodes {
227            ensure!(
228                seen.get(node),
229                "VecGraph requires every node to have at least one arc, and node {} does not have any",
230                node
231            );
232        }
233
234        let mut label_names_with_index: Vec<_> =
235            self.label_names.iter().cloned().enumerate().collect();
236        match self.label_names_order {
237            LabelNamesOrder::Lexicographic => label_names_with_index
238                .sort_unstable_by_key(|(_index, label_name)| label_name.clone()),
239            LabelNamesOrder::LexicographicBase64 => {
240                let base64 = base64_simd::STANDARD;
241                label_names_with_index.sort_unstable_by_key(|(_index, label_name)| {
242                    base64.encode_to_string(label_name).into_bytes()
243                });
244            }
245        }
246        let mut label_permutation = vec![0; label_names_with_index.len()];
247        for (new_index, (old_index, _)) in label_names_with_index.iter().enumerate() {
248            label_permutation[*old_index] = new_index;
249        }
250        let label_names: Vec<_> = label_names_with_index
251            .into_iter()
252            .map(|(_index, label_name)| label_name)
253            .collect();
254
255        let mut arcs = self.arcs.clone();
256        arcs.sort_by_key(|((src, dst), _label)| (*src, *dst)); // stable sort, it makes tests easier to write
257
258        let arcs: Vec<((NodeId, NodeId), Vec<u64>)> = arcs
259            .into_iter()
260            .group_by(|((src, dst), _label)| (*src, *dst))
261            .into_iter()
262            .map(|((src, dst), arcs)| -> ((NodeId, NodeId), Vec<u64>) {
263                let labels = arcs
264                    .flat_map(|((_src, _dst), labels)| {
265                        labels.map(|label| {
266                            UntypedEdgeLabel::from(match label {
267                                EdgeLabel::Branch(branch) => EdgeLabel::Branch(
268                                    Branch::new(LabelNameId(
269                                        label_permutation[branch.label_name_id().0 as usize] as u64,
270                                    ))
271                                    .expect("Label name permutation overflowed"),
272                                ),
273                                EdgeLabel::DirEntry(entry) => EdgeLabel::DirEntry(
274                                    DirEntry::new(
275                                        entry.permission().expect("invalid permission"),
276                                        LabelNameId(
277                                            label_permutation[entry.label_name_id().0 as usize]
278                                                as u64,
279                                        ),
280                                    )
281                                    .expect("Label name permutation overflowed"),
282                                ),
283                                EdgeLabel::Visit(visit) => EdgeLabel::Visit(visit),
284                            })
285                            .0
286                        })
287                    })
288                    .collect();
289                ((src, dst), labels)
290            })
291            .collect();
292
293        let backward_arcs: Vec<((NodeId, NodeId), Vec<u64>)> = arcs
294            .iter()
295            .map(|((src, dst), labels)| ((*dst, *src), labels.clone()))
296            .collect();
297
298        SwhBidirectionalGraph::from_underlying_graphs(
299            std::path::PathBuf::default(),
300            LabeledVecGraph::from_arcs(arcs),
301            LabeledVecGraph::from_arcs(backward_arcs),
302        )
303        .init_properties()
304        .load_properties(|properties| {
305            properties
306                .with_maps(properties::VecMaps::new(self.swhids.clone()))
307                .context("Could not join maps")?
308                .with_contents(
309                    properties::VecContents::new(
310                        self.is_skipped_content
311                            .iter()
312                            .copied()
313                            .zip(self.content_lengths.iter().copied())
314                            .collect(),
315                    )
316                    .context("Could not build VecContents")?,
317                )
318                .context("Could not join VecContents")?
319                .with_label_names(
320                    properties::VecLabelNames::new(label_names.clone())
321                        .context("Could not build VecLabelNames")?,
322                )
323                .context("Could not join maps")?
324                .with_persons(
325                    properties::VecPersons::new(
326                        self.author_ids
327                            .iter()
328                            .copied()
329                            .zip(self.committer_ids.iter().copied())
330                            .collect(),
331                    )
332                    .context("Could not build VecPersons")?,
333                )
334                .context("Could not join persons")?
335                .with_strings(
336                    properties::VecStrings::new(
337                        self.messages
338                            .iter()
339                            .cloned()
340                            .zip(self.tag_names.iter().cloned())
341                            .collect(),
342                    )
343                    .context("Could not build VecStrings")?,
344                )
345                .context("Could not join strings")?
346                .with_timestamps(
347                    properties::VecTimestamps::new(
348                        self.author_timestamps
349                            .iter()
350                            .copied()
351                            .zip(self.author_timestamp_offsets.iter().copied())
352                            .zip(self.committer_timestamps.iter().copied())
353                            .zip(self.committer_timestamp_offsets.iter().copied())
354                            .map(|(((a_ts, a_ts_o), c_ts), c_ts_o)| (a_ts, a_ts_o, c_ts, c_ts_o))
355                            .collect(),
356                    )
357                    .context("Could not build VecTimestamps")?,
358                )
359                .context("Could not join timestamps")
360        })
361    }
362}
363
364pub struct NodeBuilder<'builder> {
365    node_id: NodeId,
366    graph_builder: &'builder mut GraphBuilder,
367}
368
369impl NodeBuilder<'_> {
370    #[inline(always)]
371    pub fn done(&self) -> NodeId {
372        self.node_id
373    }
374
375    pub fn content_length(&mut self, content_length: u64) -> &mut Self {
376        self.graph_builder.content_lengths[self.node_id] = Some(content_length);
377        self
378    }
379
380    pub fn is_skipped_content(&mut self, is_skipped_content: bool) -> &mut Self {
381        self.graph_builder.is_skipped_content[self.node_id] = is_skipped_content;
382        self
383    }
384
385    pub fn author(&mut self, author: Vec<u8>) -> &mut Self {
386        let next_author_id = self
387            .graph_builder
388            .persons
389            .len()
390            .try_into()
391            .expect("person names overflowed u32");
392        let author_id = self
393            .graph_builder
394            .persons
395            .entry(author)
396            .or_insert(next_author_id);
397        self.graph_builder.author_ids[self.node_id] = Some(*author_id);
398        self
399    }
400
401    pub fn committer(&mut self, committer: Vec<u8>) -> &mut Self {
402        let next_committer_id = self
403            .graph_builder
404            .persons
405            .len()
406            .try_into()
407            .expect("person names overflowed u32");
408        let committer_id = self
409            .graph_builder
410            .persons
411            .entry(committer)
412            .or_insert(next_committer_id);
413        self.graph_builder.committer_ids[self.node_id] = Some(*committer_id);
414        self
415    }
416
417    pub fn message(&mut self, message: Vec<u8>) -> &mut Self {
418        self.graph_builder.messages[self.node_id] = Some(message);
419        self
420    }
421
422    pub fn tag_name(&mut self, tag_name: Vec<u8>) -> &mut Self {
423        self.graph_builder.tag_names[self.node_id] = Some(tag_name);
424        self
425    }
426
427    pub fn author_timestamp(&mut self, ts: i64, offset: i16) -> &mut Self {
428        self.graph_builder.author_timestamps[self.node_id] = Some(ts);
429        self.graph_builder.author_timestamp_offsets[self.node_id] = Some(offset);
430        self
431    }
432
433    pub fn committer_timestamp(&mut self, ts: i64, offset: i16) -> &mut Self {
434        self.graph_builder.committer_timestamps[self.node_id] = Some(ts);
435        self.graph_builder.committer_timestamp_offsets[self.node_id] = Some(offset);
436        self
437    }
438}
439
440pub fn codegen_from_full_graph<
441    G: SwhLabeledForwardGraph
442        + SwhGraphWithProperties<
443            Maps: properties::Maps,
444            Timestamps: properties::Timestamps,
445            Persons: properties::Persons,
446            Contents: properties::Contents,
447            Strings: properties::Strings,
448            LabelNames: properties::LabelNames,
449        >,
450    W: Write,
451>(
452    graph: &G,
453    mut writer: W,
454) -> Result<(), std::io::Error> {
455    // Turns a Vec<u8> into an escaped bytestring
456    let bytestring = |b: Vec<u8>| b.into_iter().map(std::ascii::escape_default).join("");
457
458    writer.write_all(b"use swh_graph::swhid;\nuse swh_graph::graph_builder::GraphBuilder;\n")?;
459    writer.write_all(b"use swh_graph::labels::{Permission, VisitStatus};\n")?;
460    writer.write_all(b"\n")?;
461    writer.write_all(b"let mut builder = GraphBuilder::default();\n")?;
462    for node in 0..graph.num_nodes() {
463        writer.write_all(
464            format!(
465                "builder\n    .node(swhid!({}))\n    .unwrap()\n",
466                graph.properties().swhid(node)
467            )
468            .as_bytes(),
469        )?;
470        let mut write_line = |s: String| writer.write_all(format!("    {s}\n").as_bytes());
471        match graph.properties().node_type(node) {
472            NodeType::Content => {
473                write_line(format!(
474                    ".is_skipped_content({})",
475                    graph.properties().is_skipped_content(node),
476                ))?;
477            }
478            NodeType::Revision
479            | NodeType::Release
480            | NodeType::Directory
481            | NodeType::Snapshot
482            | NodeType::Origin => {}
483        }
484        if let Some(v) = graph.properties().content_length(node) {
485            write_line(format!(".content_length({v})"))?;
486        }
487        if let Some(v) = graph.properties().message(node) {
488            write_line(format!(".message(b\"{}\".to_vec())", bytestring(v)))?;
489        }
490        if let Some(v) = graph.properties().tag_name(node) {
491            write_line(format!(".tag_name(b\"{}\".to_vec())", bytestring(v)))?;
492        }
493        if let Some(v) = graph.properties().author_id(node) {
494            write_line(format!(".author(b\"{v}\".to_vec())"))?;
495        }
496        if let Some(ts) = graph.properties().author_timestamp(node) {
497            let offset = graph
498                .properties()
499                .author_timestamp_offset(node)
500                .expect("Node has author_timestamp but no author_timestamp_offset");
501            write_line(format!(".author_timestamp({ts}, {offset})"))?;
502        }
503        if let Some(v) = graph.properties().committer_id(node) {
504            write_line(format!(".committer(b\"{v}\".to_vec())"))?;
505        }
506        if let Some(ts) = graph.properties().committer_timestamp(node) {
507            let offset = graph
508                .properties()
509                .committer_timestamp_offset(node)
510                .expect("Node has committer_timestamp but no committer_timestamp_offset");
511            write_line(format!(".committer_timestamp({ts}, {offset})"))?;
512        }
513        writer.write_all(b"    .done();\n")?;
514    }
515
516    writer.write_all(b"\n")?;
517
518    for node in 0..graph.num_nodes() {
519        for (succ, labels) in graph.labeled_successors(node) {
520            let mut has_labels = false;
521            for label in labels {
522                writer.write_all(
523                    match label {
524                        EdgeLabel::DirEntry(label) => format!(
525                            "builder.dir_arc({}, {}, Permission::{:?}, b\"{}\".to_vec());\n",
526                            node,
527                            succ,
528                            label.permission().expect("Invalid permission"),
529                            bytestring(graph.properties().label_name(label.label_name_id())),
530                        ),
531                        EdgeLabel::Branch(label) => format!(
532                            "builder.snp_arc({}, {}, b\"{}\".to_vec());\n",
533                            node,
534                            succ,
535                            bytestring(graph.properties().label_name(label.label_name_id())),
536                        ),
537                        EdgeLabel::Visit(label) => format!(
538                            "builder.ori_arc({}, {}, VisitStatus::{:?}, {});\n",
539                            node,
540                            succ,
541                            label.status(),
542                            label.timestamp(),
543                        ),
544                    }
545                    .as_bytes(),
546                )?;
547                has_labels = true;
548            }
549            if !has_labels {
550                writer.write_all(format!("builder.arc({node}, {succ});\n").as_bytes())?;
551            }
552        }
553    }
554
555    writer.write_all(b"\nbuilder.done().expect(\"Could not build graph\")\n")?;
556
557    Ok(())
558}
559
560/// Builds a [`BuiltGraph`] from a [`GraphSpy`]'s recorded history
561///
562/// This analyzes which nodes, arcs, and properties were accessed during execution
563/// and builds a minimal graph containing just those elements for bug reproduction.
564pub fn build_graph_from_spy<G>(
565    spy: &GraphSpy<
566        G,
567        impl properties::MaybeMaps,
568        impl properties::MaybeTimestamps,
569        impl properties::MaybePersons,
570        impl properties::MaybeContents,
571        impl properties::MaybeStrings,
572        impl properties::MaybeLabelNames,
573    >,
574) -> Result<BuiltGraph>
575where
576    G: SwhLabeledForwardGraph
577        + SwhLabeledBackwardGraph
578        + SwhGraphWithProperties<
579            Maps: properties::Maps,
580            Timestamps: properties::Timestamps,
581            Persons: properties::Persons,
582            Contents: properties::Contents,
583            Strings: properties::Strings,
584            LabelNames: properties::LabelNames,
585        >,
586{
587    let history = spy.history.lock().unwrap();
588
589    // all accessed nodes and arcs from history
590    let mut nodes = HashSet::<NodeId>::new();
591    let mut arcs = HashMap::<(NodeId, NodeId), Vec<EdgeLabel>>::new();
592
593    for record in history.iter() {
594        match record {
595            // SwhGraph
596            GraphAccessRecord::HasNode(node) => {
597                nodes.insert(*node);
598            }
599            GraphAccessRecord::HasArc(src, dst) => {
600                nodes.insert(*src);
601                nodes.insert(*dst);
602                arcs.entry((*src, *dst)).or_default();
603            }
604            GraphAccessRecord::Path => {
605                // GraphBuilder does not allow configuring this, and it probably doesn't matter
606                // anyway
607            }
608            GraphAccessRecord::NumNodes
609            | GraphAccessRecord::NumArcs
610            | GraphAccessRecord::NumNodesByType
611            | GraphAccessRecord::NumArcsByType => {
612                // not much we can do about this one short of copying every node/arc, but it would
613                // make the codegened graph huge, so it would be useless.
614                // so we have to assume it's fine not to preserve the number of nodes.
615                // perhaps in the future we can find a way to add "ghost" nodes in the built graph.
616            }
617            GraphAccessRecord::IsTransposed => {
618                if spy.graph().is_transposed() {
619                    // TODO
620                    bail!("build_graph_from_spy does not support building transposed graphs yet");
621                }
622            }
623
624            // SwhForwardGraph
625            GraphAccessRecord::Successors(node) | GraphAccessRecord::Outdegree(node) => {
626                nodes.insert(*node);
627                for succ in spy.graph().successors(*node) {
628                    nodes.insert(succ);
629                    arcs.entry((*node, succ)).or_default();
630                }
631            }
632
633            // SwhBackwardGraph
634            GraphAccessRecord::Predecessors(node) | GraphAccessRecord::Indegree(node) => {
635                nodes.insert(*node);
636                for pred in spy.graph().predecessors(*node) {
637                    nodes.insert(pred);
638                    arcs.entry((pred, *node)).or_default();
639                }
640            }
641
642            // SwhLabeledForwardGraph
643            GraphAccessRecord::UntypedLabeledSuccessors(node)
644            | GraphAccessRecord::LabeledSuccessors(node) => {
645                nodes.insert(*node);
646                for (succ, labels) in spy.graph().labeled_successors(*node) {
647                    nodes.insert(succ);
648                    arcs.entry((*node, succ))
649                        .or_insert_with(|| labels.into_iter().collect());
650                }
651            }
652
653            // SwhLabeledBackwardGraph
654            GraphAccessRecord::UntypedLabeledPredecessors(node)
655            | GraphAccessRecord::LabeledPredecessors(node) => {
656                nodes.insert(*node);
657                for (pred, labels) in spy.graph().labeled_predecessors(*node) {
658                    nodes.insert(pred);
659                    arcs.entry((pred, *node))
660                        .or_insert_with(|| labels.into_iter().collect());
661                }
662            }
663
664            // SwhGraphWithProperties
665            GraphAccessRecord::Property(PropertyAccess::Swhid(node))
666            | GraphAccessRecord::Property(PropertyAccess::NodeType(node))
667            | GraphAccessRecord::Property(PropertyAccess::IsSkippedContent(node))
668            | GraphAccessRecord::Property(PropertyAccess::ContentLength(node))
669            | GraphAccessRecord::Property(PropertyAccess::AuthorId(node))
670            | GraphAccessRecord::Property(PropertyAccess::CommitterId(node))
671            | GraphAccessRecord::Property(PropertyAccess::Message(node))
672            | GraphAccessRecord::Property(PropertyAccess::TagName(node))
673            | GraphAccessRecord::Property(PropertyAccess::AuthorTimestamp(node))
674            | GraphAccessRecord::Property(PropertyAccess::AuthorTimestampOffset(node))
675            | GraphAccessRecord::Property(PropertyAccess::CommitterTimestamp(node))
676            | GraphAccessRecord::Property(PropertyAccess::CommitterTimestampOffset(node)) => {
677                nodes.insert(*node);
678            }
679            GraphAccessRecord::Property(PropertyAccess::NodeId(swhid)) => {
680                if let Ok(node) = spy.graph().properties().node_id(*swhid) {
681                    nodes.insert(node);
682                }
683            }
684            GraphAccessRecord::Property(PropertyAccess::NodeIdForInvalidBytes(_))
685            | GraphAccessRecord::Property(PropertyAccess::NodeIdForInvalidString(_))
686            | GraphAccessRecord::Property(PropertyAccess::NodeIdForInvalidStrArray(_)) => {
687                // nothing to do about those; they come from strings/bytes that can't be parsed as
688                // SWHID, independently of what nodes are in te graph
689            }
690            GraphAccessRecord::Property(PropertyAccess::LabelNames) => {
691                // we'll catch the needed ones from the arc label accesses
692            }
693        }
694    }
695
696    let mut builder = GraphBuilder::default();
697
698    let mut new2old: Vec<_> = nodes.iter().copied().collect();
699    new2old.sort();
700
701    let old2new: HashMap<_, _> = new2old
702        .iter()
703        .enumerate()
704        .map(|(new, &old)| (old, new))
705        .collect();
706
707    // Build nodes
708    for &old_id in &new2old {
709        let swhid = spy.graph().properties().swhid(old_id);
710        let mut node_builder = builder
711            .node(swhid)
712            .with_context(|| format!("Could add node {swhid}"))?;
713
714        node_builder.is_skipped_content(spy.graph().properties().is_skipped_content(old_id));
715
716        if let Some(v) = spy.graph().properties().content_length(old_id) {
717            node_builder.content_length(v);
718        }
719
720        if let Some(v) = spy.graph().properties().message(old_id) {
721            node_builder.message(v);
722        }
723
724        if let Some(v) = spy.graph().properties().tag_name(old_id) {
725            node_builder.tag_name(v);
726        }
727
728        if let Some(v) = spy.graph().properties().author_id(old_id) {
729            // Convert PersonId to bytes (placeholder, since we don't have access to actual names)
730            node_builder.author(format!("{v}").into_bytes());
731        }
732
733        if let Some(ts) = spy.graph().properties().author_timestamp(old_id) {
734            let offset = spy
735                .graph()
736                .properties()
737                .author_timestamp_offset(old_id)
738                .expect("Node has author_timestamp but no author_timestamp_offset");
739            node_builder.author_timestamp(ts, offset);
740        }
741
742        if let Some(v) = spy.graph().properties().committer_id(old_id) {
743            // Convert PersonId to bytes (placeholder, since we don't have access to actual names)
744            node_builder.committer(format!("{v}").into_bytes());
745        }
746
747        if let Some(ts) = spy.graph().properties().committer_timestamp(old_id) {
748            let offset = spy
749                .graph()
750                .properties()
751                .committer_timestamp_offset(old_id)
752                .expect("Node has committer_timestamp but no committer_timestamp_offset");
753            node_builder.committer_timestamp(ts, offset);
754        }
755
756        let new_id = node_builder.done();
757        assert_eq!(new2old[new_id], old_id);
758        assert_eq!(old2new.get(&old_id), Some(&new_id));
759    }
760
761    // Build arcs
762    for ((old_src, old_dst), labels) in arcs {
763        let new_src = old2new[&old_src];
764        let new_dst = old2new[&old_dst];
765
766        if labels.is_empty() {
767            // unlabeled node, or node whose labels we never tried to read
768            builder.arc(new_src, new_dst)
769        } else {
770            for label in labels {
771                match label {
772                    EdgeLabel::DirEntry(label) => {
773                        builder.dir_arc(
774                            new_src,
775                            new_dst,
776                            label.permission().expect("Invalid permission"),
777                            spy.graph().properties().label_name(label.label_name_id()),
778                        );
779                    }
780                    EdgeLabel::Branch(label) => {
781                        builder.snp_arc(
782                            new_src,
783                            new_dst,
784                            spy.graph().properties().label_name(label.label_name_id()),
785                        );
786                    }
787                    EdgeLabel::Visit(label) => {
788                        builder.ori_arc(
789                            new_src,
790                            new_dst,
791                            label.status(),
792                            label.timestamp(),
793                            label.visit_type(),
794                        );
795                    }
796                }
797            }
798        }
799    }
800
801    builder.done()
802}
swh_graph/graph_builder.rs

swh_graph/
graph_builder.rs
