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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
use std::collections::{HashSet, HashMap};

use core::{Source, SourceId, SourceMap, Summary, Dependency, PackageId, Package};
use core::PackageSet;
use util::{CargoResult, ChainError, Config, human, profile};

/// Source of information about a group of packages.
///
/// See also `core::Source`.
pub trait Registry {
    /// Attempt to find the packages that match a dependency request.
    fn query(&mut self, name: &Dependency) -> CargoResult<Vec<Summary>>;
}

impl Registry for Vec<Summary> {
    fn query(&mut self, dep: &Dependency) -> CargoResult<Vec<Summary>> {
        Ok(self.iter().filter(|summary| dep.matches(*summary))
               .cloned().collect())
    }
}

impl Registry for Vec<Package> {
    fn query(&mut self, dep: &Dependency) -> CargoResult<Vec<Summary>> {
        Ok(self.iter().filter(|pkg| dep.matches(pkg.summary()))
               .map(|pkg| pkg.summary().clone()).collect())
    }
}

/// This structure represents a registry of known packages. It internally
/// contains a number of `Box<Source>` instances which are used to load a
/// `Package` from.
///
/// The resolution phase of Cargo uses this to drive knowledge about new
/// packages as well as querying for lists of new packages. It is here that
/// sources are updated (e.g. network operations) and overrides are
/// handled.
///
/// The general idea behind this registry is that it is centered around the
/// `SourceMap` structure, contained within which is a mapping of a `SourceId` to
/// a `Source`. Each `Source` in the map has been updated (using network
/// operations if necessary) and is ready to be queried for packages.
pub struct PackageRegistry<'cfg> {
    sources: SourceMap<'cfg>,
    config: &'cfg Config,

    // A list of sources which are considered "overrides" which take precedent
    // when querying for packages.
    overrides: Vec<SourceId>,

    // Note that each SourceId does not take into account its `precise` field
    // when hashing or testing for equality. When adding a new `SourceId`, we
    // want to avoid duplicates in the `SourceMap` (to prevent re-updating the
    // same git repo twice for example), but we also want to ensure that the
    // loaded source is always updated.
    //
    // Sources with a `precise` field normally don't need to be updated because
    // their contents are already on disk, but sources without a `precise` field
    // almost always need to be updated. If we have a cached `Source` for a
    // precise `SourceId`, then when we add a new `SourceId` that is not precise
    // we want to ensure that the underlying source is updated.
    //
    // This is basically a long-winded way of saying that we want to know
    // precisely what the keys of `sources` are, so this is a mapping of key to
    // what exactly the key is.
    source_ids: HashMap<SourceId, (SourceId, Kind)>,

    locked: HashMap<SourceId, HashMap<String, Vec<(PackageId, Vec<PackageId>)>>>,
}

#[derive(PartialEq, Eq, Clone, Copy)]
enum Kind {
    Override,
    Locked,
    Normal,
}

impl<'cfg> PackageRegistry<'cfg> {
    pub fn new(config: &'cfg Config) -> PackageRegistry<'cfg> {
        PackageRegistry {
            sources: SourceMap::new(),
            source_ids: HashMap::new(),
            overrides: Vec::new(),
            config: config,
            locked: HashMap::new(),
        }
    }

    pub fn get(self, package_ids: &[PackageId]) -> PackageSet<'cfg> {
        trace!("getting packages; sources={}", self.sources.len());
        PackageSet::new(package_ids, self.sources)
    }

    fn ensure_loaded(&mut self, namespace: &SourceId, kind: Kind) -> CargoResult<()> {
        match self.source_ids.get(namespace) {
            // We've previously loaded this source, and we've already locked it,
            // so we're not allowed to change it even if `namespace` has a
            // slightly different precise version listed.
            Some(&(_, Kind::Locked)) => {
                debug!("load/locked   {}", namespace);
                return Ok(())
            }

            // If the previous source was not a precise source, then we can be
            // sure that it's already been updated if we've already loaded it.
            Some(&(ref previous, _)) if previous.precise().is_none() => {
                debug!("load/precise  {}", namespace);
                return Ok(())
            }

            // If the previous source has the same precise version as we do,
            // then we're done, otherwise we need to need to move forward
            // updating this source.
            Some(&(ref previous, _)) => {
                if previous.precise() == namespace.precise() {
                    debug!("load/match    {}", namespace);
                    return Ok(())
                }
                debug!("load/mismatch {}", namespace);
            }
            None => {
                debug!("load/missing  {}", namespace);
            }
        }

        try!(self.load(namespace, kind));
        Ok(())
    }

    pub fn add_sources(&mut self, ids: &[SourceId]) -> CargoResult<()> {
        for id in ids.iter() {
            try!(self.ensure_loaded(id, Kind::Locked));
        }
        Ok(())
    }

    pub fn add_preloaded(&mut self, id: &SourceId, source: Box<Source + 'cfg>) {
        self.add_source(id, source, Kind::Locked);
    }

    fn add_source(&mut self, id: &SourceId, source: Box<Source + 'cfg>,
                  kind: Kind) {
        self.sources.insert(id, source);
        self.source_ids.insert(id.clone(), (id.clone(), kind));
    }

    pub fn add_override(&mut self, id: &SourceId, source: Box<Source + 'cfg>) {
        self.add_source(id, source, Kind::Override);
        self.overrides.push(id.clone());
    }

    pub fn register_lock(&mut self, id: PackageId, deps: Vec<PackageId>) {
        let sub_map = self.locked.entry(id.source_id().clone())
                                 .or_insert(HashMap::new());
        let sub_vec = sub_map.entry(id.name().to_string())
                             .or_insert(Vec::new());
        sub_vec.push((id, deps));
    }

    fn load(&mut self, source_id: &SourceId, kind: Kind) -> CargoResult<()> {
        (|| {
            // Save off the source
            let source = source_id.load(self.config);
            if kind == Kind::Override {
                self.overrides.push(source_id.clone());
            }
            self.add_source(source_id, source, kind);

            // Ensure the source has fetched all necessary remote data.
            let _p = profile::start(format!("updating: {}", source_id));
            self.sources.get_mut(source_id).unwrap().update()
        }).chain_error(|| human(format!("Unable to update {}", source_id)))
    }

    fn query_overrides(&mut self, dep: &Dependency)
                       -> CargoResult<Vec<Summary>> {
        let mut seen = HashSet::new();
        let mut ret = Vec::new();
        for s in self.overrides.iter() {
            let src = self.sources.get_mut(s).unwrap();
            let dep = Dependency::new_override(dep.name(), s);
            ret.extend(try!(src.query(&dep)).into_iter().filter(|s| {
                seen.insert(s.name().to_string())
            }));
        }
        Ok(ret)
    }

    // This function is used to transform a summary to another locked summary if
    // possible. This is where the concept of a lockfile comes into play.
    //
    // If a summary points at a package id which was previously locked, then we
    // override the summary's id itself, as well as all dependencies, to be
    // rewritten to the locked versions. This will transform the summary's
    // source to a precise source (listed in the locked version) as well as
    // transforming all of the dependencies from range requirements on imprecise
    // sources to exact requirements on precise sources.
    //
    // If a summary does not point at a package id which was previously locked,
    // we still want to avoid updating as many dependencies as possible to keep
    // the graph stable. In this case we map all of the summary's dependencies
    // to be rewritten to a locked version wherever possible. If we're unable to
    // map a dependency though, we just pass it on through.
    fn lock(&self, summary: Summary) -> Summary {
        let pair = self.locked.get(summary.source_id()).and_then(|map| {
            map.get(summary.name())
        }).and_then(|vec| {
            vec.iter().find(|&&(ref id, _)| id == summary.package_id())
        });

        // Lock the summary's id if possible
        let summary = match pair {
            Some(&(ref precise, _)) => summary.override_id(precise.clone()),
            None => summary,
        };
        summary.map_dependencies(|dep| {
            match pair {
                // If we've got a known set of overrides for this summary, then
                // one of a few cases can arise:
                //
                // 1. We have a lock entry for this dependency from the same
                //    source as it's listed as coming from. In this case we make
                //    sure to lock to precisely the given package id.
                //
                // 2. We have a lock entry for this dependency, but it's from a
                //    different source than what's listed, or the version
                //    requirement has changed. In this case we must discard the
                //    locked version because the dependency needs to be
                //    re-resolved.
                //
                // 3. We don't have a lock entry for this dependency, in which
                //    case it was likely an optional dependency which wasn't
                //    included previously so we just pass it through anyway.
                Some(&(_, ref deps)) => {
                    match deps.iter().find(|d| d.name() == dep.name()) {
                        Some(lock) => {
                            if dep.matches_id(lock) {
                                dep.lock_to(lock)
                            } else {
                                dep
                            }
                        }
                        None => dep,
                    }
                }

                // If this summary did not have a locked version, then we query
                // all known locked packages to see if they match this
                // dependency. If anything does then we lock it to that and move
                // on.
                None => {
                    let v = self.locked.get(dep.source_id()).and_then(|map| {
                        map.get(dep.name())
                    }).and_then(|vec| {
                        vec.iter().find(|&&(ref id, _)| dep.matches_id(id))
                    });
                    match v {
                        Some(&(ref id, _)) => dep.lock_to(id),
                        None => dep
                    }
                }
            }
        })
    }
}

impl<'cfg> Registry for PackageRegistry<'cfg> {
    fn query(&mut self, dep: &Dependency) -> CargoResult<Vec<Summary>> {
        let overrides = try!(self.query_overrides(&dep));

        let ret = if overrides.is_empty() {
            // Ensure the requested source_id is loaded
            try!(self.ensure_loaded(dep.source_id(), Kind::Normal));

            match self.sources.get_mut(dep.source_id()) {
                Some(src) => try!(src.query(&dep)),
                None => Vec::new(),
            }
        } else {
            overrides
        };

        // post-process all returned summaries to ensure that we lock all
        // relevant summaries to the right versions and sources
        Ok(ret.into_iter().map(|summary| self.lock(summary)).collect())
    }
}

#[cfg(test)]
pub mod test {
    use core::{Summary, Registry, Dependency};
    use util::{CargoResult};

    pub struct RegistryBuilder {
        summaries: Vec<Summary>,
        overrides: Vec<Summary>
    }

    impl RegistryBuilder {
        pub fn new() -> RegistryBuilder {
            RegistryBuilder { summaries: vec![], overrides: vec![] }
        }

        pub fn summary(mut self, summary: Summary) -> RegistryBuilder {
            self.summaries.push(summary);
            self
        }

        pub fn summaries(mut self, summaries: Vec<Summary>) -> RegistryBuilder {
            self.summaries.extend(summaries.into_iter());
            self
        }

        pub fn add_override(mut self, summary: Summary) -> RegistryBuilder {
            self.overrides.push(summary);
            self
        }

        pub fn overrides(mut self, summaries: Vec<Summary>) -> RegistryBuilder {
            self.overrides.extend(summaries.into_iter());
            self
        }

        fn query_overrides(&self, dep: &Dependency) -> Vec<Summary> {
            self.overrides.iter()
                .filter(|s| s.name() == dep.name())
                .map(|s| s.clone())
                .collect()
        }
    }

    impl Registry for RegistryBuilder {
        fn query(&mut self, dep: &Dependency) -> CargoResult<Vec<Summary>> {
            debug!("querying; dep={:?}", dep);

            let overrides = self.query_overrides(dep);

            if overrides.is_empty() {
                self.summaries.query(dep)
            } else {
                Ok(overrides)
            }
        }
    }
}