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
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
use bstr::{BString, ByteSlice};
use gix_glob::Pattern;
use kstring::{KString, KStringRef};

use crate::{
    search::{
        refmap::RefMapKey, Assignments, AttributeId, Attributes, MatchKind, Metadata, MetadataCollection, Outcome,
        TrackedAssignment, Value,
    },
    AssignmentRef, NameRef, StateRef,
};

/// Initialization
impl Outcome {
    /// Initialize this instance to collect outcomes for all names in `collection`, which represents all possible attributes
    /// or macros we may visit, and [`reset`][Self::reset()] it unconditionally.
    ///
    /// This must be called after each time `collection` changes.
    pub fn initialize(&mut self, collection: &MetadataCollection) {
        if self.matches_by_id.len() != collection.name_to_meta.len() {
            let global_num_attrs = collection.name_to_meta.len();

            self.matches_by_id.resize(global_num_attrs, Default::default());

            // NOTE: This works only under the assumption that macros remain defined.
            for (order, macro_attributes) in collection.iter().filter_map(|(_, meta)| {
                (!meta.macro_attributes.is_empty()).then_some((meta.id.0, &meta.macro_attributes))
            }) {
                self.matches_by_id[order].macro_attributes.clone_from(macro_attributes)
            }

            for (name, id) in self.selected.iter_mut().filter(|(_, id)| id.is_none()) {
                *id = collection.name_to_meta.get(name.as_str()).map(|meta| meta.id)
            }
        }
        self.reset();
    }

    /// Like [`initialize()`][Self::initialize()], but limits the set of attributes to look for and fill in
    /// to `attribute_names`.
    /// Users of this instance should prefer to limit their search as this would allow it to finish earlier.
    ///
    /// Note that `attribute_names` aren't validated to be valid names here, as invalid names definitely will always be unspecified.
    pub fn initialize_with_selection<'a>(
        &mut self,
        collection: &MetadataCollection,
        attribute_names: impl IntoIterator<Item = impl Into<KStringRef<'a>>>,
    ) {
        self.initialize_with_selection_inner(collection, &mut attribute_names.into_iter().map(Into::into))
    }

    fn initialize_with_selection_inner(
        &mut self,
        collection: &MetadataCollection,
        attribute_names: &mut dyn Iterator<Item = KStringRef<'_>>,
    ) {
        self.selected.clear();
        self.selected.extend(attribute_names.map(|name| {
            (
                name.to_owned(),
                collection.name_to_meta.get(name.as_str()).map(|meta| meta.id),
            )
        }));

        self.initialize(collection);
        self.reset_remaining();
    }

    /// Prepare for a new search over the known set of attributes by resetting our state.
    pub fn reset(&mut self) {
        self.matches_by_id.iter_mut().for_each(|item| item.r#match = None);
        self.attrs_stack.clear();
        self.reset_remaining();
    }

    fn reset_remaining(&mut self) {
        self.remaining = Some(if self.selected.is_empty() {
            self.matches_by_id.len()
        } else {
            self.selected.iter().filter(|(_name, id)| id.is_some()).count()
        });
    }

    /// A performance optimization which allows results from this instance to be efficiently copied over to `dest`.
    /// For this to work, `collection` must be the one used to initialize our state, and `dest` should not have been initialized
    /// with any meaningful collection initially, i.e. be empty the first time this method is called.
    ///
    /// Note that it's safe to call it multiple times, so that it can be called after this instance was used to store a search result.
    pub fn copy_into(&self, collection: &MetadataCollection, dest: &mut Self) {
        dest.initialize(collection);
        dest.matches_by_id.clone_from(&self.matches_by_id);
        if dest.patterns.len() != self.patterns.len() {
            dest.patterns = self.patterns.clone();
        }
        if dest.assignments.len() != self.assignments.len() {
            dest.assignments = self.assignments.clone();
        }
        if dest.source_paths.len() != self.source_paths.len() {
            dest.source_paths = self.source_paths.clone();
        }
        dest.remaining = self.remaining;
    }
}

/// Access
impl Outcome {
    /// Return an iterator over all filled attributes we were initialized with.
    ///
    /// ### Note
    ///
    /// If [`initialize_with_selection`][Self::initialize_with_selection()] was used,
    /// use [`iter_selected()`][Self::iter_selected()] instead.
    ///
    /// ### Deviation
    ///
    /// It's possible that the order in which the attribute are returned (if not limited to a set of attributes) isn't exactly
    /// the same as what `git` provides.
    /// Ours is in order of declaration, whereas `git` seems to list macros first somehow. Since the values are the same, this
    /// shouldn't be an issue.
    pub fn iter(&self) -> impl Iterator<Item = crate::search::Match<'_>> {
        self.matches_by_id
            .iter()
            .filter_map(|item| item.r#match.as_ref().map(|m| m.to_outer(self)))
    }

    /// Iterate over all matches of the attribute selection in their original order.
    ///
    /// This only yields values if this instance was initialized with [`Outcome::initialize_with_selection()`].
    pub fn iter_selected(&self) -> impl Iterator<Item = crate::search::Match<'_>> {
        static DUMMY: Pattern = Pattern {
            text: BString::new(Vec::new()),
            mode: gix_glob::pattern::Mode::empty(),
            first_wildcard_pos: None,
        };
        self.selected.iter().map(|(name, id)| {
            id.and_then(|id| self.matches_by_id[id.0].r#match.as_ref().map(|m| m.to_outer(self)))
                .unwrap_or_else(|| crate::search::Match {
                    pattern: &DUMMY,
                    assignment: AssignmentRef {
                        name: NameRef::try_from(name.as_bytes().as_bstr())
                            .unwrap_or_else(|_| NameRef("invalid".into())),
                        state: StateRef::Unspecified,
                    },
                    kind: MatchKind::Attribute { macro_id: None },
                    location: crate::search::MatchLocation {
                        source: None,
                        sequence_number: 0,
                    },
                })
        })
    }

    /// Obtain a match by the order of its attribute, if the order exists in our initialized attribute list and there was a match.
    pub fn match_by_id(&self, id: AttributeId) -> Option<crate::search::Match<'_>> {
        self.matches_by_id
            .get(id.0)
            .and_then(|m| m.r#match.as_ref().map(|m| m.to_outer(self)))
    }

    /// Return `true` if there is nothing more to be done as all attributes were filled.
    pub fn is_done(&self) -> bool {
        self.remaining() == 0
    }
}

/// Mutation
impl Outcome {
    /// Fill all `attrs` and resolve them recursively if they are macros. Return `true` if there is no attribute left to be resolved and
    /// we are totally done.
    /// `pattern` is what matched a patch and is passed for contextual information,
    /// providing `sequence_number` and `source` as well.
    pub(crate) fn fill_attributes<'a>(
        &mut self,
        attrs: impl Iterator<Item = &'a TrackedAssignment>,
        pattern: &gix_glob::Pattern,
        source: Option<&std::path::PathBuf>,
        sequence_number: usize,
    ) -> bool {
        self.attrs_stack.extend(
            attrs
                .filter(|attr| self.matches_by_id[attr.id.0].r#match.is_none())
                .map(|attr| (attr.id, attr.inner.clone(), None)),
        );
        while let Some((id, assignment, parent_order)) = self.attrs_stack.pop() {
            let slot = &mut self.matches_by_id[id.0];
            if slot.r#match.is_some() {
                continue;
            }
            // Let's be explicit - this is only non-empty for macros.
            let is_macro = !slot.macro_attributes.is_empty();

            slot.r#match = Some(Match {
                pattern: self.patterns.insert(pattern),
                assignment: self.assignments.insert_owned(assignment),
                kind: if is_macro {
                    MatchKind::Macro {
                        parent_macro_id: parent_order,
                    }
                } else {
                    MatchKind::Attribute { macro_id: parent_order }
                },
                location: MatchLocation {
                    source: source.map(|path| self.source_paths.insert(path)),
                    sequence_number,
                },
            });
            if self.reduce_and_check_if_done(id) {
                return true;
            }

            if is_macro {
                // TODO(borrowchk): one fine day we should be able to re-borrow `slot` without having to redo the array access.
                let slot = &self.matches_by_id[id.0];
                self.attrs_stack.extend(
                    slot.macro_attributes
                        .iter()
                        .filter(|attr| self.matches_by_id[attr.id.0].r#match.is_none())
                        .map(|attr| (attr.id, attr.inner.clone(), Some(id))),
                );
            }
        }
        false
    }
}

impl Outcome {
    /// Given a list of `attrs` by order, return true if at least one of them is not set
    pub(crate) fn has_unspecified_attributes(&self, mut attrs: impl Iterator<Item = AttributeId>) -> bool {
        attrs.any(|order| self.matches_by_id[order.0].r#match.is_none())
    }
    /// Return the amount of attributes haven't yet been found.
    ///
    /// If this number reaches 0, then the search can be stopped as there is nothing more to fill in.
    pub(crate) fn remaining(&self) -> usize {
        self.remaining
            .expect("BUG: instance must be initialized for each search set")
    }

    fn reduce_and_check_if_done(&mut self, attr: AttributeId) -> bool {
        if self.selected.is_empty()
            || self
                .selected
                .iter()
                .any(|(_name, id)| id.map_or(false, |id| id == attr))
        {
            *self.remaining.as_mut().expect("initialized") -= 1;
        }
        self.is_done()
    }
}

impl std::fmt::Debug for Outcome {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        struct AsDisplay<'a>(&'a dyn std::fmt::Display);
        impl std::fmt::Debug for AsDisplay<'_> {
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                self.0.fmt(f)
            }
        }

        let mut dbg = f.debug_tuple("Outcome");
        if self.selected.is_empty() {
            for match_ in self.iter() {
                dbg.field(&AsDisplay(&match_.assignment));
            }
        } else {
            for match_ in self.iter_selected() {
                dbg.field(&AsDisplay(&match_.assignment));
            }
        }
        dbg.finish()
    }
}

/// Mutation
impl MetadataCollection {
    /// Assign order ids to each attribute either in macros (along with macros themselves) or attributes of patterns, and store
    /// them in this collection.
    ///
    /// Must be called before querying matches.
    pub fn update_from_list(&mut self, list: &mut gix_glob::search::pattern::List<Attributes>) {
        for pattern in &mut list.patterns {
            match &mut pattern.value {
                Value::MacroAssignments { id: order, assignments } => {
                    *order = self.id_for_macro(
                        pattern
                            .pattern
                            .text
                            .to_str()
                            .expect("valid macro names are always UTF8 and this was verified"),
                        assignments,
                    );
                }
                Value::Assignments(assignments) => {
                    self.assign_order_to_attributes(assignments);
                }
            }
        }
    }
}

/// Access
impl MetadataCollection {
    /// Return an iterator over the contents of the map in an easy-to-consume form.
    pub fn iter(&self) -> impl Iterator<Item = (&str, &Metadata)> {
        self.name_to_meta.iter().map(|(k, v)| (k.as_str(), v))
    }
}

impl MetadataCollection {
    pub(crate) fn id_for_macro(&mut self, name: &str, attrs: &mut Assignments) -> AttributeId {
        let order = match self.name_to_meta.get_mut(name) {
            Some(meta) => meta.id,
            None => {
                let order = AttributeId(self.name_to_meta.len());
                self.name_to_meta.insert(
                    KString::from_ref(name),
                    Metadata {
                        id: order,
                        macro_attributes: Default::default(),
                    },
                );
                order
            }
        };

        self.assign_order_to_attributes(attrs);
        self.name_to_meta
            .get_mut(name)
            .expect("just added")
            .macro_attributes
            .clone_from(attrs);

        order
    }
    pub(crate) fn id_for_attribute(&mut self, name: &str) -> AttributeId {
        match self.name_to_meta.get(name) {
            Some(meta) => meta.id,
            None => {
                let order = AttributeId(self.name_to_meta.len());
                self.name_to_meta.insert(KString::from_ref(name), order.into());
                order
            }
        }
    }
    pub(crate) fn assign_order_to_attributes(&mut self, attributes: &mut [TrackedAssignment]) {
        for TrackedAssignment {
            id: order,
            inner: crate::Assignment { name, .. },
        } in attributes
        {
            *order = self.id_for_attribute(&name.0);
        }
    }
}

impl From<AttributeId> for Metadata {
    fn from(order: AttributeId) -> Self {
        Metadata {
            id: order,
            macro_attributes: Default::default(),
        }
    }
}

impl MatchKind {
    /// return the id of the macro that resolved us, or `None` if that didn't happen.
    pub fn source_id(&self) -> Option<AttributeId> {
        match self {
            MatchKind::Attribute { macro_id: id } | MatchKind::Macro { parent_macro_id: id } => *id,
        }
    }
}

/// A version of `Match` without references.
#[derive(Clone, PartialEq, Eq, Debug, Hash, Ord, PartialOrd)]
pub struct Match {
    /// The glob pattern itself, like `/target/*`.
    pub pattern: RefMapKey,
    /// The key=value pair of the attribute that matched at the pattern. There can be multiple matches per pattern.
    pub assignment: RefMapKey,
    /// Additional information about the kind of match.
    pub kind: MatchKind,
    /// Information about the location of the match.
    pub location: MatchLocation,
}

impl Match {
    fn to_outer<'a>(&self, out: &'a Outcome) -> crate::search::Match<'a> {
        crate::search::Match {
            pattern: out.patterns.resolve(self.pattern).expect("pattern still present"),
            assignment: out
                .assignments
                .resolve(self.assignment)
                .expect("assignment present")
                .as_ref(),
            kind: self.kind,
            location: self.location.to_outer(out),
        }
    }
}

/// A version of `MatchLocation` without references.
#[derive(Clone, PartialEq, Eq, Debug, Hash, Ord, PartialOrd)]
pub struct MatchLocation {
    /// The path to the source from which the pattern was loaded, or `None` if it was specified by other means.
    pub source: Option<RefMapKey>,
    /// The line at which the pattern was found in its `source` file, or the occurrence in which it was provided.
    pub sequence_number: usize,
}

impl MatchLocation {
    fn to_outer<'a>(&self, out: &'a Outcome) -> crate::search::MatchLocation<'a> {
        crate::search::MatchLocation {
            source: self
                .source
                .and_then(|source| out.source_paths.resolve(source).map(AsRef::as_ref)),
            sequence_number: self.sequence_number,
        }
    }
}