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

/*
 * @Copyright 2020 Jason Carr
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */

use super::types::Entry;
use crate::types::{HasIx, Ix};

/**
 * A Strategy allows for controlling
 * the method and order for mark-based
 * traversals.
 *
 * While for a standard depth-first-search,
 * the CallStack strategy is sufficient, this
 * is vulnerable to stack overflows,
 * and does not allow traversals in anything
 * other than the order given by HasIx::foreach_ix
 */
pub trait Strategy<T: 'static, State> {
    /**
     * Runs the traversal for a given starting point and
     * function to get next entries by index. Should
     * visit a corresponding state of the visitor
     * for each entry.
     *
     * This should run the entire traversal. The state
     * needed for that may be stored in any way possible.
     */
    fn run<'a, F, V>(&self, get_next: &mut F, visitor: &mut V, start: Entry<T>)
    where
        F: FnMut(Ix<T>) -> Option<Entry<'a, T>>,
        V: Visitor<T, State>;
}

/**
 * A Visitor contains the callbacks for each position
 * in the traversal. The State parameter is open
 * so that it can be reported by the particular
 * choice of Strategy.
 */
pub trait Visitor<T, State> {
    fn visit(&mut self, st: State, e: Entry<T>);
}

/**
 * A state enum for pre- and post-order actions.
 */
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum PreAndPost {
    Pre,
    Post,
}
/**
 * A state enum for pre-order only. This can
 * slighty reduce the amount of state needed
 * for some traversals.
 */
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum PreOnly {
    Pre,
}
/**
 * A visitor which contains a pre and post function.
 * It can be used both for PreAndPost and PreOnly
 * states.
 */
pub struct PrePostVisitor<Pre, Post> {
    pub pre: Pre,
    pub post: Post,
}

impl<Pre, Post, T> Visitor<T, PreAndPost> for PrePostVisitor<Pre, Post>
where
    Pre: FnMut(Entry<T>),
    Post: FnMut(Entry<T>),
{
    fn visit(&mut self, st: PreAndPost, e: Entry<T>) {
        match st {
            PreAndPost::Pre => (self.pre)(e),
            PreAndPost::Post => (self.post)(e),
        }
    }
}
impl<Pre, Post, T> Visitor<T, PreOnly> for PrePostVisitor<Pre, Post>
where
    Pre: FnMut(Entry<T>),
{
    fn visit(&mut self, st: PreOnly, e: Entry<T>) {
        match st {
            PreOnly::Pre => (self.pre)(e),
        }
    }
}

/**
 * A simple traversal using the call stack as memory, with iteration
 * using HasIx::foreach_ix. While very general and performant, this
 * means that these traversals are succeptible to stack overflows,
 * and that only the greatest common denominator of features is supported.
 */
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct CallStack;

impl<T: 'static + HasIx<T>> Strategy<T, PreAndPost> for CallStack {
    fn run<'a, F, V>(&self, get_next: &mut F, visitor: &mut V, mut next: Entry<T>)
    where
        F: FnMut(Ix<T>) -> Option<Entry<'a, T>>,
        V: Visitor<T, PreAndPost>,
    {
        visitor.visit(PreAndPost::Pre, next.reborrow());
        next.get_mut().foreach_ix(|ix| {
            if let Some(next) = get_next(*ix) {
                self.run(get_next, visitor, next);
            }
        });
        visitor.visit(PreAndPost::Post, next.reborrow());
    }
}
impl<T: 'static + HasIx<T>> Strategy<T, PreOnly> for CallStack {
    fn run<'a, F, V>(&self, get_next: &mut F, visitor: &mut V, mut next: Entry<T>)
    where
        F: FnMut(Ix<T>) -> Option<Entry<'a, T>>,
        V: Visitor<T, PreOnly>,
    {
        visitor.visit(PreOnly::Pre, next.reborrow());
        next.get_mut().foreach_ix(|ix| {
            if let Some(next) = get_next(*ix) {
                self.run(get_next, visitor, next);
            }
        });
    }
}
impl<T: 'static + HasIx<T>, St, Str: Strategy<T, St>> Strategy<T, St> for &Str {
    fn run<'a, F, V>(&self, get_next: &mut F, visitor: &mut V, start: Entry<T>)
    where
        F: FnMut(Ix<T>) -> Option<Entry<'a, T>>,
        V: Visitor<T, St>,
    {
        <Str as Strategy<_, _>>::run(*self, get_next, visitor, start);
    }
}

pub(crate) fn no_process<T>(_: Entry<T>) {}