pint_pkg/
plan.rs

1//! Items related to construction of the compilation [`Plan`].
2
3use crate::{
4    manifest::{self, Dependency, ManifestFile},
5    source::{self, Source},
6};
7use manifest::ManifestFileError;
8use petgraph::{visit::EdgeRef, Directed, Direction};
9use serde::{Deserialize, Serialize};
10use std::{
11    collections::{hash_map, BTreeMap, HashMap, HashSet},
12    fmt,
13    hash::{Hash, Hasher},
14    path::{Path, PathBuf},
15    str,
16};
17use thiserror::Error;
18
19/// The type used to index into the graph.
20type GraphIx = u32;
21/// The package graph type, where the edge *a* -> *b* means that *a* depends on *b*.
22pub type Graph = petgraph::stable_graph::StableGraph<Pinned, Dep, Directed, GraphIx>;
23/// The package graph's edge index type.
24pub type EdgeIx = petgraph::graph::EdgeIndex<GraphIx>;
25/// The package graph's node index type.
26pub type NodeIx = petgraph::graph::NodeIndex<GraphIx>;
27/// Shorthand for the graph's edge reference type.
28type EdgeReference<'a> = petgraph::stable_graph::EdgeReference<'a, Dep, GraphIx>;
29
30/// A dependency edge.
31#[derive(Clone, Debug, Eq, PartialEq)]
32pub struct Dep {
33    /// The kind of dependency represented by the edge.
34    pub kind: DepKind,
35    /// The dependency name used to refer to the package.
36    ///
37    /// This is the name on the left hand side of the `=` in a dependency.
38    ///
39    /// Note that this might differ from the package name in the case that the
40    /// dependency specifies a `package` field.
41    pub name: String,
42}
43
44/// The kind of dependency represented by an edge.
45#[derive(Clone, Debug, Eq, PartialEq)]
46pub enum DepKind {
47    /// A library dependency, sharing items like types, constants and macros.
48    Library,
49    /// A contract dependency, providing the content address of the contract.
50    Contract,
51}
52
53/// An unpinned package.
54#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
55pub struct Pkg {
56    /// The name declared in the package manifest.
57    pub name: String,
58    /// The unpinned source of the package.
59    pub source: Source,
60}
61
62/// A pinned package.
63#[derive(Clone, Debug, Eq, Hash, PartialEq, Deserialize, Serialize)]
64pub struct Pinned {
65    /// The name declared in the package manifest.
66    pub name: String,
67    /// The pinned source of the package.
68    pub source: source::Pinned,
69}
70
71/// The ID of a pinned package.
72///
73/// Determined by hashing the package's name with its [`source::Pinned`].
74#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq, Deserialize, Serialize)]
75pub struct PinnedId(u64);
76
77/// A set of manifests that have been pinned during construction of the compilation plan.
78pub type PinnedManifests = HashMap<PinnedId, ManifestFile>;
79
80/// Manifests of the root packages being built.
81///
82/// This enables building more than one output package simultaneously, improving
83/// compilation times for cases where packages may share multiple dependencies.
84pub type MemberManifests = BTreeMap<String, ManifestFile>;
85
86/// The set of invalid deps discovered during a `check_graph` traversal.
87pub type InvalidDeps = BTreeMap<EdgeIx, InvalidDepCause>;
88
89/// A mapping from fetched packages to their location within the graph.
90type FetchedPkgs = HashMap<Pkg, NodeIx>;
91
92/// The context provided to the `fetch_deps` traversal.
93struct FetchCtx<'a> {
94    id: source::FetchId,
95    fetched: &'a mut FetchedPkgs,
96    visited: &'a mut HashSet<NodeIx>,
97}
98
99/// A compilation plan generated for one or more member package manifests.
100#[derive(Debug)]
101pub struct Plan {
102    /// The dependency graph of all packages.
103    graph: Graph,
104    /// A mapping from each package's pinned ID to its associated manifest.
105    manifests: PinnedManifests,
106    /// The topological order in which nodes should be built.
107    compilation_order: Vec<NodeIx>,
108}
109
110/// Failed to construct a compilation plan.
111#[derive(Debug, Error)]
112pub enum PlanError {
113    /// Failed to fetch the package graph.
114    #[error("failed to fetch the package graph: {0}")]
115    FetchGraph(#[from] FetchGraphError),
116    /// A cycle was detected in the package graph.
117    #[error("{0}")]
118    DependencyCycle(#[from] DependencyCycle),
119}
120
121#[derive(Debug, Error)]
122#[error("failed to fetch graph")]
123pub enum FetchGraphError {
124    #[error("{0}")]
125    MemberName(#[from] MemberNameNotUnique),
126    #[error("failed to source dependency package {0:?}: {1}")]
127    Source(String, source::SourceError),
128    #[error("failed to pin/fetch dependency package {0:?}: {1}")]
129    PinAndFetch(String, Box<source::PinAndFetchError>),
130    #[error("package {0:?}'s dependency named {1:?} failed the depenency manifest check: {2}")]
131    DepManifest(String, String, DepManifestError),
132}
133
134/// Error indicating that more than one member package was found with the same name.
135#[derive(Debug, Error)]
136#[error("more than one member package with name {0:?}")]
137pub struct MemberNameNotUnique(pub String);
138
139/// Errors produced by dependency manifest validation.
140#[derive(Debug, Error)]
141pub enum DepManifestError {
142    /// Expected a dependency of some kind (i.e. Library, Contract) but found some other kind.
143    #[error("declared as a {0:?} dependency, but is actually a {1:?}")]
144    UnexpectedKind(DepKind, manifest::PackageKind),
145    // A mismatch occurred between the dependency package name and the actual package name.
146    #[error(
147        "dependency name {0:?} must match the manifest project name {1:?} \
148        unless `package = {1:?}` is specified in the dependency declaration"
149    )]
150    UnexpectedName(String, String),
151}
152
153/// Failed to parse a pinned ID from its hex string representation.
154#[derive(Debug, Error)]
155#[error("failed to parse `PinnedId`: expected 16-char hex string, found {0:?}")]
156pub struct PinnedIdFromStrError(String);
157
158/// The reason the dependency was invalidated.
159#[derive(Debug, Error)]
160pub enum InvalidDepCause {
161    /// No members found in the graph for the given set.
162    #[error("graph contains none of the given members")]
163    NoMembersFound,
164    #[error("{0}")]
165    Check(#[from] CheckDepError),
166}
167
168/// Represents an invalid dependency.
169#[derive(Debug, Error)]
170pub enum CheckDepError {
171    /// Failed to resolve the dependency's path.
172    #[error("{0}")]
173    PathError(#[from] DepPathError),
174    /// Failed to load a dependency manifest.
175    #[error("{0}")]
176    DepManifestFileError(#[from] ManifestFileError),
177    /// The dependency has no entry in the parent manifest.
178    #[error("no entry in parent manifest")]
179    NoEntryInManifest,
180    /// Failed to construct the source.
181    #[error("{0}")]
182    Source(#[from] source::SourceError),
183    /// A source mismatch
184    #[error("the graph source {0:?} does not match the manifest entry {1:?}")]
185    SourceMismatch(Source, Source),
186    /// The dependency's manifest failed the dependency manifest check.
187    #[error("{0}")]
188    DepManifestError(#[from] DepManifestError),
189}
190
191/// Failed to find a path root for a given path node.
192///
193/// All path nodes must have some root in order to resolve their potentially relative path.
194#[derive(Debug, Error)]
195#[error("failed to find path root: `path` dependency {0:?} has no parent")]
196pub struct FindPathRootError(String);
197
198/// An error produced by a failed path root check.
199#[derive(Debug, Error)]
200pub enum CheckPathRootError {
201    #[error("{0}")]
202    NotFound(#[from] FindPathRootError),
203    #[error("invalid path root for dependency {0:?}: expected {1}, found {2}")]
204    Invalid(String, PinnedId, PinnedId),
205}
206
207/// Failed to resolve a dependency's path.
208#[derive(Debug, Error)]
209pub enum DepPathError {
210    /// Some source-specific error occurred.
211    #[error("{0}")]
212    Source(#[from] source::DepPathError),
213    /// The path root was not found or was invalid.
214    #[error("{0}")]
215    CheckPathRoot(#[from] CheckPathRootError),
216    /// The dependency has no entry in the parent manifest.
217    #[error("dependency named {0:?} does not appear in manifest of {1:?}")]
218    NoEntryInManifest(String, String),
219    /// A dependency declared as a member was not found in the member manifests.
220    #[error("supposed member dependency {0:?} not found in member manifests")]
221    MemberNotFound(String),
222    /// The dependency was specified as a path that does not exist.
223    #[error("dependency named {0:?} specified a path {0:?} that does not exist")]
224    PathDoesNotExist(String, PathBuf),
225}
226
227/// A cycle was detected while attempting to determine compilation order.
228#[derive(Debug, Error)]
229#[error("cycle detected between the following packages: {0:?}")]
230pub struct DependencyCycle(pub Vec<String>);
231
232impl Dep {
233    fn new(name: String, kind: DepKind) -> Self {
234        Self { name, kind }
235    }
236}
237
238impl Pinned {
239    /// A unique ID for the pinned package.
240    ///
241    /// The internal value is produced by hashing the package's name and `source::Pinned`.
242    pub fn id(&self) -> PinnedId {
243        PinnedId::new(&self.name, &self.source)
244    }
245
246    /// Retrieve the unpinned version of this source.
247    pub fn unpinned(&self, path: &Path) -> Pkg {
248        let source = self.source.unpinned(path);
249        let name = self.name.clone();
250        Pkg { name, source }
251    }
252}
253
254impl PinnedId {
255    /// Determine the sha256 hash of the given name and pinned source to produce
256    /// a unique pinned package ID.
257    pub fn new(name: &str, source: &source::Pinned) -> Self {
258        let mut hasher = hash_map::DefaultHasher::default();
259        name.hash(&mut hasher);
260        source.hash(&mut hasher);
261        Self(hasher.finish())
262    }
263}
264
265impl Plan {
266    /// The full package dependency graph.
267    pub fn graph(&self) -> &Graph {
268        &self.graph
269    }
270
271    /// The manifest (both in-memory and local file) for every package in the graph.
272    pub fn manifests(&self) -> &PinnedManifests {
273        &self.manifests
274    }
275
276    /// An order in which packages may be compiled so that all dependencies are
277    /// built before all dependents.
278    pub fn compilation_order(&self) -> &[NodeIx] {
279        &self.compilation_order
280    }
281}
282
283impl fmt::Display for PinnedId {
284    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
285        write!(f, "{:016x}", self.0)
286    }
287}
288
289impl str::FromStr for PinnedId {
290    type Err = PinnedIdFromStrError;
291    fn from_str(s: &str) -> Result<Self, Self::Err> {
292        let res = u64::from_str_radix(s, 16);
293        Ok(Self(res.map_err(|_| PinnedIdFromStrError(s.to_string()))?))
294    }
295}
296
297/// Construct a compilation plan from the given member manifests that we wish to build.
298///
299/// Fetches and pins all packages as a part of constructing the full compilation plan.
300pub fn from_members(members: &MemberManifests) -> Result<Plan, PlanError> {
301    // Fetch the graph and populate the pinned manifests.
302    let mut graph = Graph::default();
303    let mut pinned_manifests = PinnedManifests::default();
304    fetch_graph(members, &mut graph, &mut pinned_manifests)?;
305
306    // TODO: Remove this block, just a sanity check.
307    {
308        let (pinned_manifests2, invalid_deps) = check_graph(&graph, members);
309        assert!(invalid_deps.is_empty(), "{invalid_deps:?}");
310        assert_eq!(pinned_manifests, pinned_manifests2);
311    }
312
313    // Determine the order in which packages should be compiled.
314    // TODO: Remove this when enabling concurrent builds.
315    let compilation_order = compilation_order(&graph)?;
316
317    Ok(Plan {
318        graph,
319        manifests: pinned_manifests,
320        compilation_order,
321    })
322}
323
324/// Complete the given package graph (and associated `PinnedManifests` map) for the `root_manifest`.
325fn fetch_graph(
326    member_manifests: &MemberManifests,
327    graph: &mut Graph,
328    pinned_manifests: &mut PinnedManifests,
329) -> Result<HashSet<NodeIx>, FetchGraphError> {
330    let mut added_nodes = HashSet::default();
331    for name in member_manifests.keys() {
332        let added = fetch_graph_from_member(member_manifests, name, graph, pinned_manifests)?;
333        added_nodes.extend(added);
334    }
335    Ok(added_nodes)
336}
337
338/// Complete the given package graph (and associated `PinnedManifests` map) for
339/// the member.
340///
341/// First finds the root node associated with the given `root_manifest` within
342/// the graph, adding it if it does not already exist.
343///
344/// Next, recursively traverses the dependencies, fetching and pinning each
345/// package that does not exist within the graph.
346///
347/// Returns the set of nodes that were newly added.
348fn fetch_graph_from_member(
349    member_manifests: &MemberManifests,
350    member_name: &str,
351    graph: &mut Graph,
352    pinned_manifests: &mut PinnedManifests,
353) -> Result<HashSet<NodeIx>, FetchGraphError> {
354    // The manifest associated with the given member name.
355    let member_manifest = &member_manifests[member_name];
356
357    // Retrieve the member node, or create one if it does not exist.
358    let member_node = find_member_node(graph, &member_manifest.pkg.name)?
359        .unwrap_or_else(|| insert_member_pkg(member_manifest.clone(), graph, pinned_manifests));
360
361    // Traverse the rest of the graph from the root.
362    let fetch_ts = std::time::Instant::now();
363    let fetch_id = source::fetch_graph_id(member_manifest.dir(), fetch_ts);
364    let path_root = graph[member_node].id();
365
366    // Track already fetched packages and visited nodes.
367    let mut fetched = fetched_pkgs(graph, pinned_manifests);
368    let mut visited: HashSet<NodeIx> = HashSet::default();
369
370    let mut ctx = FetchCtx {
371        id: fetch_id,
372        fetched: &mut fetched,
373        visited: &mut visited,
374    };
375
376    fetch_deps(
377        member_manifests,
378        member_node,
379        path_root,
380        graph,
381        pinned_manifests,
382        &mut ctx,
383    )
384}
385
386/// Insert a member package into the graph and pinned manifest map.
387fn insert_member_pkg(
388    member_manifest: ManifestFile,
389    graph: &mut Graph,
390    pinned_manifests: &mut PinnedManifests,
391) -> NodeIx {
392    let name = member_manifest.pkg.name.clone();
393    let source = source::Pinned::MEMBER;
394    let pkg = Pinned { name, source };
395    let pkg_id = pkg.id();
396    pinned_manifests.insert(pkg_id, member_manifest);
397    graph.add_node(pkg)
398}
399
400/// Create a mapping from already fetched packages to their location within the graph.
401///
402/// Assumes `pinned_manifests` contains an entry for every pinned package within
403/// the graph and `panic!`s otherwise.
404fn fetched_pkgs(graph: &Graph, pinned_manifests: &PinnedManifests) -> FetchedPkgs {
405    graph
406        .node_indices()
407        .map(|n| {
408            let pinned = &graph[n];
409            let manifest = &pinned_manifests[&pinned.id()];
410            let pkg = pinned.unpinned(manifest.dir());
411            (pkg, n)
412        })
413        .collect()
414}
415
416/// Given a manifest, produces iterator yielding all named dependencies alongside their kind.
417fn manifest_deps(
418    manifest: &ManifestFile,
419) -> impl '_ + Iterator<Item = (String, Dependency, DepKind)> {
420    let deps = manifest
421        .deps
422        .iter()
423        .map(|(name, dep)| (name.clone(), dep.clone(), DepKind::Library));
424    let contract_deps = manifest
425        .contract_deps
426        .iter()
427        .map(|(name, dep)| (name.clone(), dep.clone(), DepKind::Contract));
428    deps.chain(contract_deps)
429}
430
431/// Traverse, fetch and pin unfetched, unpinned dependencies as required to complete the graph.
432fn fetch_deps(
433    member_manifests: &MemberManifests,
434    node: NodeIx,
435    path_root: PinnedId,
436    graph: &mut Graph,
437    pinned_manifests: &mut PinnedManifests,
438    ctx: &mut FetchCtx,
439) -> Result<HashSet<NodeIx>, FetchGraphError> {
440    let mut added = HashSet::default();
441    let parent_id = graph[node].id();
442    let deps: Vec<_> = manifest_deps(&pinned_manifests[&parent_id]).collect();
443    for (dep_name, dep, dep_kind) in deps {
444        let pkg_name = dep.package.as_ref().unwrap_or(&dep_name);
445        let parent_manifest_dir = pinned_manifests[&parent_id].dir();
446        let source =
447            Source::from_manifest_dep(parent_manifest_dir, &dep, member_manifests.values())
448                .map_err(|e| FetchGraphError::Source(pkg_name.to_string(), e))?;
449
450        // If we haven't yet fetched this dependency, fetch it, pin it and add it to the graph.
451        let dep_pkg = Pkg {
452            name: pkg_name.to_string(),
453            source,
454        };
455        let dep_node = match ctx.fetched.entry(dep_pkg) {
456            hash_map::Entry::Occupied(entry) => *entry.get(),
457            hash_map::Entry::Vacant(entry) => {
458                let pkg = entry.key();
459                let ctx = source::PinCtx {
460                    _fetch_id: ctx.id,
461                    path_root,
462                    pkg_name: &pkg.name,
463                };
464                let source = pkg
465                    .source
466                    .pin_and_fetch(ctx, pinned_manifests)
467                    .map_err(|e| FetchGraphError::PinAndFetch(pkg.name.clone(), Box::new(e)))?;
468                let name = pkg.name.clone();
469                let dep_pinned = Pinned { name, source };
470                let dep_node = graph.add_node(dep_pinned);
471                added.insert(dep_node);
472                *entry.insert(dep_node)
473            }
474        };
475
476        let dep_edge = Dep::new(dep_name.to_string(), dep_kind.clone());
477        // Ensure we have an edge to the dependency.
478        graph.update_edge(node, dep_node, dep_edge.clone());
479
480        // If we've visited this node during this traversal already, no need to traverse it again.
481        if !ctx.visited.insert(dep_node) {
482            continue;
483        }
484
485        // Check the dependency's manifest.
486        let dep_pinned = &graph[dep_node];
487        let dep_pkg_id = dep_pinned.id();
488        check_dep_manifest(dep_pinned, &pinned_manifests[&dep_pkg_id], &dep_edge)
489            .map_err(|e| FetchGraphError::DepManifest(graph[node].name.clone(), dep_name, e))?;
490
491        let path_root = match dep_pinned.source {
492            source::Pinned::Member(_) => dep_pkg_id,
493            source::Pinned::Path(_) => path_root,
494        };
495
496        // Recursively fetch this dependency's dependencies.
497        added.extend(fetch_deps(
498            member_manifests,
499            dep_node,
500            path_root,
501            graph,
502            pinned_manifests,
503            ctx,
504        )?);
505    }
506    Ok(added)
507}
508
509/// Find the member node with the given package name.
510///
511/// Returns an `Err` if more than one member node with the given name exists.
512fn find_member_node(g: &Graph, pkg_name: &str) -> Result<Option<NodeIx>, MemberNameNotUnique> {
513    let mut matching = member_nodes_with_name(g, pkg_name);
514    let node_opt = matching.next();
515    match matching.next() {
516        None => Ok(node_opt),
517        Some(_) => Err(MemberNameNotUnique(pkg_name.to_string())),
518    }
519}
520
521/// All member nodes within the graph.
522fn member_nodes(g: &Graph) -> impl '_ + Iterator<Item = NodeIx> {
523    g.node_indices()
524        .filter(|&n| g[n].source == source::Pinned::MEMBER)
525}
526
527/// All member nodes with the given name.
528fn member_nodes_with_name<'a>(
529    g: &'a Graph,
530    pkg_name: &'a str,
531) -> impl 'a + Iterator<Item = NodeIx> {
532    member_nodes(g).filter(move |&n| g[n].name == pkg_name)
533}
534
535/// Validate the graph against the given member manifests.
536///
537/// Returns a map of `PinnedManifests` for all valid nodes within the graph,
538/// alongside of all invalid dependencies as a set of edges.
539fn check_graph(graph: &Graph, members: &MemberManifests) -> (PinnedManifests, InvalidDeps) {
540    // Add all existing member manifests to the pinned manifests map.
541    let mut pinned_manifests = PinnedManifests::default();
542    let mut invalid_deps = InvalidDeps::default();
543    for n in member_nodes(graph) {
544        let pinned = &graph[n];
545        let name = &pinned.name;
546        let Some(manifest) = members.get(name) else {
547            continue;
548        };
549        pinned_manifests.insert(pinned.id(), manifest.clone());
550        invalid_deps.extend(check_deps(graph, members, n, &mut pinned_manifests));
551    }
552
553    // If no member nodes, we need to reconstruct the whole graph.
554    if pinned_manifests.is_empty() {
555        invalid_deps.extend(
556            graph
557                .edge_indices()
558                .map(|e| (e, InvalidDepCause::NoMembersFound)),
559        );
560    }
561
562    (pinned_manifests, invalid_deps)
563}
564
565/// Recursively validate all dependencies starting from the given node.
566///
567/// `pinned_manifests` must at least already contain the manifest of the given
568/// `node` whose dependencies are being checked.
569fn check_deps(
570    graph: &Graph,
571    members: &MemberManifests,
572    node: NodeIx,
573    pinned_manifests: &mut PinnedManifests,
574) -> InvalidDeps {
575    let mut remove = InvalidDeps::default();
576    for edge in graph.edges_directed(node, Direction::Outgoing) {
577        let dep_manifest = match check_dep(graph, members, edge, pinned_manifests) {
578            Ok(manifest) => manifest,
579            Err(err) => {
580                remove.insert(edge.id(), InvalidDepCause::Check(err));
581                continue;
582            }
583        };
584        let dep_node = edge.target();
585        let dep_id = graph[dep_node].id();
586        if pinned_manifests.insert(dep_id, dep_manifest).is_none() {
587            let rm = check_deps(graph, members, dep_node, pinned_manifests);
588            remove.extend(rm);
589        }
590    }
591    remove
592}
593
594/// Validate a dependency within the given graph.
595///
596/// Assumes that `PinnedManifests` contains the manifest for the `edge.source()`
597/// node and panics otherwise.
598fn check_dep(
599    graph: &Graph,
600    members: &MemberManifests,
601    edge: EdgeReference,
602    pinned_manifests: &PinnedManifests,
603) -> Result<ManifestFile, CheckDepError> {
604    let node = edge.source();
605    let dep_node = edge.target();
606    let dep = edge.weight();
607    let node_manifest = &pinned_manifests[&graph[node].id()];
608    let dep_path = dep_path(graph, members, node_manifest, dep_node)?;
609    let dep_manifest_path = dep_path.join(ManifestFile::FILE_NAME);
610    let dep_manifest = ManifestFile::from_path(&dep_manifest_path)?;
611    let dep_entry = node_manifest
612        .dep(&dep.name)
613        .ok_or(CheckDepError::NoEntryInManifest)?;
614    let dep_source = Source::from_manifest_dep(node_manifest.dir(), dep_entry, members.values())?;
615    let dep_pkg = graph[dep_node].unpinned(&dep_path);
616    if dep_pkg.source != dep_source {
617        return Err(CheckDepError::SourceMismatch(dep_pkg.source, dep_source));
618    }
619    check_dep_manifest(&graph[dep_node], &dep_manifest, dep)?;
620    Ok(dep_manifest)
621}
622
623/// Given a manifest and a node associated with one of its dependencies, returns
624/// the canonical local path to the directory containing the dependency's
625/// manifest.
626fn dep_path(
627    graph: &Graph,
628    members: &MemberManifests,
629    node_manifest: &ManifestFile,
630    dep_node: NodeIx,
631) -> Result<PathBuf, DepPathError> {
632    let dep = &graph[dep_node];
633    let dep_name = &dep.name;
634    match dep.source.dep_path(&dep.name)? {
635        source::DependencyPath::ManifestPath(path) => Ok(path),
636        source::DependencyPath::Member => members
637            .values()
638            .find(|m| m.pkg.name == *dep_name)
639            .map(|m| m.dir().to_path_buf())
640            .ok_or_else(|| DepPathError::MemberNotFound(dep_name.to_string())),
641        source::DependencyPath::Root(path_root) => {
642            check_path_root(graph, dep_node, path_root)?;
643            // Check if the path is directly from the dependency.
644            match node_manifest.dep_path(dep_name) {
645                None => Err(DepPathError::NoEntryInManifest(
646                    dep_name.to_string(),
647                    node_manifest.pkg.name.to_string(),
648                )),
649                Some(path) if !path.exists() => {
650                    Err(DepPathError::PathDoesNotExist(dep_name.to_string(), path))
651                }
652                Some(path) => Ok(path),
653            }
654        }
655    }
656}
657
658/// Validate the manifest of a depenency.
659fn check_dep_manifest(
660    dep: &Pinned,
661    dep_manifest: &ManifestFile,
662    dep_edge: &Dep,
663) -> Result<(), DepManifestError> {
664    // Ensure the dependency kind matches the expected kind.
665    match (&dep_edge.kind, &dep_manifest.pkg.kind) {
666        (DepKind::Contract, manifest::PackageKind::Contract)
667        | (DepKind::Library, manifest::PackageKind::Library) => (),
668        _ => {
669            let pkg_kind = dep_manifest.pkg.kind.clone();
670            return Err(DepManifestError::UnexpectedKind(
671                dep_edge.kind.clone(),
672                pkg_kind,
673            ));
674        }
675    }
676
677    // Ensure the name matches the manifest project name.
678    if dep.name != dep_manifest.pkg.name {
679        let pkg_name = dep_manifest.pkg.name.clone();
680        return Err(DepManifestError::UnexpectedName(dep.name.clone(), pkg_name));
681    }
682
683    Ok(())
684}
685
686/// Check that the given `path_root` is actually the path root of the given `path_dep`.
687fn check_path_root(
688    graph: &Graph,
689    path_dep: NodeIx,
690    path_root: PinnedId,
691) -> Result<(), CheckPathRootError> {
692    let path_root_node = find_path_root(graph, path_dep)?;
693    if graph[path_root_node].id() != path_root {
694        return Err(CheckPathRootError::Invalid(
695            graph[path_dep].name.to_string(),
696            path_root,
697            graph[path_root_node].id(),
698        ));
699    }
700    Ok(())
701}
702
703/// Find the node that is the path root for the given node.
704///
705/// Returns an `Err` in the case that the path root could not be resolved.
706fn find_path_root(graph: &Graph, mut node: NodeIx) -> Result<NodeIx, FindPathRootError> {
707    loop {
708        let pkg = &graph[node];
709        match pkg.source {
710            source::Pinned::Member(_) => return Ok(node),
711            source::Pinned::Path(ref src) => {
712                let parent = graph
713                    .edges_directed(node, Direction::Incoming)
714                    .next()
715                    .map(|edge| edge.source())
716                    .ok_or_else(|| FindPathRootError(format!("{src}")))?;
717                node = parent;
718            }
719        }
720    }
721}
722
723/// Perform a toposort on the reversed weights to determine compilation order.
724///
725/// This ensures all dependencies are compiled prior to their dependents.
726fn compilation_order(graph: &Graph) -> Result<Vec<NodeIx>, DependencyCycle> {
727    let rev_graph = petgraph::visit::Reversed(&graph);
728    petgraph::algo::toposort(rev_graph, None).map_err(|_cycle| {
729        let sccs = petgraph::algo::kosaraju_scc(graph);
730        let cycle = sccs
731            .into_iter()
732            .find(|path| path.len() > 1)
733            .expect("one cycle must exist")
734            .into_iter()
735            .map(|n| graph[n].name.to_string())
736            .collect();
737        DependencyCycle(cycle)
738    })
739}
pint_pkg/plan.rs

pint_pkg/
plan.rs
