1//! Plugin manager with dependency resolution.
2
3use derivative::Derivative;
4use once_cell::sync::OnceCell;
5use std::collections::{HashMap, HashSet};
6use std::fmt::Debug;
7use std::hash::Hash;
8use std::slice::Iter;
9
10///
11/// Ruler allows you to implement a plugin system with dependency management and ensure that
12/// your dependencies are called in the correct order.
13///
14/// You can use it like this:
15/// ```
16/// use markdown_it::common::ruler::Ruler;
17///
18/// // this example prints "[ hello, world! ]",
19/// // where each token is printed by separate closure
20/// let mut chain = Ruler::<&str, fn (&mut String)>::new();
21///
22/// // define rules printing "hello" and "world"
23/// chain.add("hello", |s| s.push_str("hello"));
24/// chain.add("world", |s| s.push_str("world"));
25///
26/// // open bracket should be before "hello", and closing one after "world"
27/// chain.add("open_bracket", |s| s.push_str("[ ")).before("hello");
28/// chain.add("close_bracket", |s| s.push_str(" ]")).after("world");
29///
30/// // between "hello" and "world" we shall have a comma
31/// chain.add("comma", |s| s.push_str(", ")).after("hello").before("world");
32///
33/// // after "world" we should have "!" as a first rule, but ensure "world" exists first
34/// chain.add("bang", |s| s.push_str("!")).require("world").after("world").before_all();
35///
36/// // now we run this chain
37/// let mut result = String::new();
38/// for f in chain.iter() { f(&mut result); }
39/// assert_eq!(result, "[ hello, world! ]");
40/// ```
41///
42/// This data structure contains any number of elements (M, T), where T is any type and
43/// M (mark) is its identifier.
44///
45/// - `M` is used for ordering and dependency checking, it must implement `Eq + Copy + Hash + Debug`
46/// . Common choices for `M` are `u32`, `&'static str`, or a special `Symbol` type
47/// designed for this purpose.
48///
49/// - `T` is any user-defined type. It's usually a function or boxed trait.
50///
51pub struct Ruler<M, T> {
52 deps: Vec<RuleItem<M, T>>,
53 compiled: OnceCell<(Vec<usize>, Vec<T>)>,
54}
55
56impl<M, T> Ruler<M, T> {
57 pub fn new() -> Self {
58 Self::default()
59 }
60}
61
62impl<M: Eq + Hash + Copy + Debug, T: Clone> Ruler<M, T> {
63 /// Add a new rule identified by `mark` with payload `value`.
64 pub fn add(&mut self, mark: M, value: T) -> &mut RuleItem<M, T> {
65 self.compiled = OnceCell::new();
66 let dep = RuleItem::new(mark, value);
67 self.deps.push(dep);
68 self.deps.last_mut().unwrap()
69 }
70
71 /// Remove all rules identified by `mark`.
72 pub fn remove(&mut self, mark: M) {
73 self.deps.retain(|dep| !dep.marks.contains(&mark));
74 }
75
76 /// Check if there are any rules identified by `mark`.
77 pub fn contains(&mut self, mark: M) -> bool {
78 self.deps.iter().any(|dep| dep.marks.contains(&mark))
79 }
80
81 /// Ordered iteration through rules.
82 #[inline]
83 pub fn iter(&self) -> Iter<T> {
84 self.compiled.get_or_init(|| self.compile()).1.iter()
85 }
86
87 fn compile(&self) -> (Vec<usize>, Vec<T>) {
88 // ID -> [RuleItem index]
89 let mut idhash = HashMap::<M, Vec<usize>>::new();
90
91 // RuleItem index -> [RuleItem index] - dependency graph, None if already inserted
92 let mut deps_graph = vec![HashSet::new(); self.deps.len()];
93
94 // additional level of indirection that takes into account item priority
95 let mut deps_order = vec![];
96 let mut beforeall_len = 0;
97 let mut afterall_len = 0;
98
99 // compiled result
100 let mut result = vec![];
101 let mut result_idx = vec![];
102
103 // track which rules have been added already
104 let mut deps_inserted = vec![false; self.deps.len()];
105 let mut deps_remaining = self.deps.len();
106
107 for (idx, dep) in self.deps.iter().enumerate() {
108 match dep.prio {
109 RuleItemPriority::Normal => {
110 deps_order.insert(deps_order.len() - afterall_len, idx);
111 }
112 RuleItemPriority::BeforeAll => {
113 deps_order.insert(beforeall_len, idx);
114 beforeall_len += 1;
115 }
116 RuleItemPriority::AfterAll => {
117 deps_order.insert(deps_order.len(), idx);
118 afterall_len += 1;
119 }
120 }
121 for mark in &dep.marks {
122 idhash.entry(*mark).or_default().push(idx);
123 }
124 }
125
126 // build dependency graph, replacing all after's with before's,
127 // i.e. B.after(A) -> A.before(B)
128 for idx in deps_order.iter().copied() {
129 let dep = self.deps.get(idx).unwrap();
130 for constraint in &dep.cons {
131 match constraint {
132 RuleItemConstraint::Before(v) => {
133 for depidx in idhash.entry(*v).or_default().iter() {
134 deps_graph.get_mut(*depidx).unwrap().insert(idx);
135 }
136 }
137 RuleItemConstraint::After(v) => {
138 for depidx in idhash.entry(*v).or_default().iter() {
139 deps_graph.get_mut(idx).unwrap().insert(*depidx);
140 }
141 }
142 RuleItemConstraint::Require(v) => {
143 assert!(
144 idhash.contains_key(v),
145 "missing dependency: {:?} requires {:?}", dep.marks.first().unwrap(), v
146 );
147 }
148 }
149 }
150 }
151
152 // now go through the deps and push whatever doesn't have any
153 'outer: while deps_remaining > 0 {
154 for idx in deps_order.iter().copied() {
155 let inserted = deps_inserted.get_mut(idx).unwrap();
156 if *inserted { continue; }
157
158 let dlist = deps_graph.get(idx).unwrap();
159 if dlist.is_empty() {
160 let dep = self.deps.get(idx).unwrap();
161 result.push(dep.value.clone());
162 result_idx.push(idx);
163 *inserted = true;
164 deps_remaining -= 1;
165 for d in deps_graph.iter_mut() {
166 d.remove(&idx);
167 }
168 continue 'outer;
169 }
170 }
171
172 #[cfg(debug_assertions)] {
173 // check cycles in dependency graph;
174 // this is very suboptimal, but only used to generate a nice panic message.
175 // in release mode we'll just simply panic
176 for idx in deps_order.iter().copied() {
177 let mut seen = HashMap::new();
178 let mut vec = vec![idx];
179 while let Some(didx) = vec.pop() {
180 let dlist = deps_graph.get(didx).unwrap();
181 for x in dlist.iter() {
182 if seen.contains_key(x) { continue; }
183 vec.push(*x);
184 seen.insert(*x, didx);
185 if *x == idx {
186 let mut backtrack = vec![];
187 let mut curr = idx;
188 while !backtrack.contains(&curr) {
189 backtrack.push(curr);
190 curr = *seen.get(&curr).unwrap();
191 }
192 backtrack.push(curr);
193 let path = backtrack.iter()
194 .rev()
195 .map(|x| format!("{:?}", self.deps.get(*x).unwrap().marks.first().unwrap()))
196 .collect::<Vec<String>>()
197 .join(" < ");
198 panic!("cyclic dependency: {}", path);
199 }
200 }
201 }
202 }
203 }
204
205 // if you see this in debug mode, report it as a bug
206 panic!("cyclic dependency: (use debug mode for more details)");
207 }
208
209 (result_idx, result)
210 }
211}
212
213impl<M: Eq + Hash + Copy + Debug, T: Clone> Debug for Ruler<M, T> {
214 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
215 let vec: Vec<(usize, M)> = self.compiled.get_or_init(|| self.compile()).0
216 .iter()
217 .map(|idx| (*idx, *self.deps.get(*idx).unwrap().marks.first().unwrap()))
218 .collect();
219
220 f.debug_struct("Ruler")
221 .field("deps", &self.deps)
222 .field("compiled", &vec)
223 .finish()
224 }
225}
226
227impl<M, T> Default for Ruler<M, T> {
228 fn default() -> Self {
229 Self {
230 deps: Vec::new(),
231 compiled: OnceCell::new(),
232 }
233 }
234}
235
236///
237/// Result of [Ruler::add](Ruler::add), allows to customize position of each rule.
238///
239#[derive(Derivative)]
240#[derivative(Debug)]
241pub struct RuleItem<M, T> {
242 marks: Vec<M>,
243 #[derivative(Debug="ignore")]
244 value: T,
245 prio: RuleItemPriority,
246 cons: Vec<RuleItemConstraint<M>>,
247}
248
249impl<M, T> RuleItem<M, T> {
250 fn new(mark: M, value: T) -> Self {
251 Self {
252 marks: vec![mark],
253 value,
254 prio: RuleItemPriority::Normal,
255 cons: vec![],
256 }
257 }
258}
259
260impl<M: Copy, T> RuleItem<M, T> {
261 /// Make sure this rule will be inserted before any rule defined by `mark` (if such rule exists).
262 /// ```
263 /// use markdown_it::common::ruler::Ruler;
264 /// let mut chain = Ruler::<&str, fn (&mut String)>::new();
265 ///
266 /// chain.add("a", |s| s.push_str("bar"));
267 /// chain.add("b", |s| s.push_str("foo")).before("a");
268 ///
269 /// let mut result = String::new();
270 /// for f in chain.iter() { f(&mut result); }
271 /// assert_eq!(result, "foobar");
272 /// ```
273 pub fn before(&mut self, mark: M) -> &mut Self {
274 self.cons.push(RuleItemConstraint::Before(mark));
275 self
276 }
277
278 /// Make sure this rule will be inserted after any rule defined by `mark` (if such rule exists).
279 /// Similar to [RuleItem::before](RuleItem::before).
280 pub fn after(&mut self, mark: M) -> &mut Self {
281 self.cons.push(RuleItemConstraint::After(mark));
282 self
283 }
284
285 /// This rule will be inserted as early as possible, while still taking into account dependencies,
286 /// i.e. `.after(X).before_all()` causes this to be first rule after X.
287 /// ```
288 /// use markdown_it::common::ruler::Ruler;
289 /// let mut chain = Ruler::<&str, fn (&mut String)>::new();
290 ///
291 /// chain.add("a", |s| s.push_str("A"));
292 /// chain.add("c", |s| s.push_str("C")).after("a");
293 /// chain.add("b", |s| s.push_str("B")).after("a").before_all();
294 ///
295 /// let mut result = String::new();
296 /// for f in chain.iter() { f(&mut result); }
297 /// // without before_all order will be ACB
298 /// assert_eq!(result, "ABC");
299 /// ```
300 pub fn before_all(&mut self) -> &mut Self {
301 self.prio = RuleItemPriority::BeforeAll;
302 self
303 }
304
305 /// This rule will be inserted as late as possible, while still taking into account dependencies,
306 /// i.e. `.before(X).after_all()` causes this to be last rule before X.
307 /// Similar to [RuleItem::before_all](RuleItem::before_all).
308 pub fn after_all(&mut self) -> &mut Self {
309 self.prio = RuleItemPriority::AfterAll;
310 self
311 }
312
313 /// Add another auxiliary identifier to this rule. It can be used to group together multiple
314 /// rules with similar functionality.
315 /// ```
316 /// use markdown_it::common::ruler::Ruler;
317 /// let mut chain = Ruler::<&str, fn (&mut String)>::new();
318 ///
319 /// chain.add("b", |s| s.push_str("B")).alias("BorC");
320 /// chain.add("c", |s| s.push_str("C")).alias("BorC");
321 /// chain.add("a", |s| s.push_str("A")).before("BorC");
322 ///
323 /// let mut result = String::new();
324 /// for f in chain.iter() { f(&mut result); }
325 /// assert_eq!(result, "ABC");
326 /// ```
327 pub fn alias(&mut self, mark: M) -> &mut Self {
328 self.marks.push(mark);
329 self
330 }
331
332 /// Require another rule identified by `mark`, panic if not found.
333 pub fn require(&mut self, mark: M) -> &mut Self {
334 self.cons.push(RuleItemConstraint::Require(mark));
335 self
336 }
337}
338
339#[derive(Debug)]
340enum RuleItemConstraint<M> {
341 Before(M),
342 After(M),
343 Require(M),
344}
345
346#[derive(Debug)]
347enum RuleItemPriority {
348 Normal,
349 BeforeAll,
350 AfterAll,
351}
352
353
354#[cfg(test)]
355mod tests {
356 use super::Ruler;
357
358 #[test]
359 #[should_panic(expected=r#"cyclic dependency: "A" < "B" < "C" < "D" < "E" < "F" < "A""#)]
360 #[cfg(debug_assertions)]
361 fn cyclic_dependency_debug() {
362 let mut r = Ruler::new();
363 r.add("%", ()).after("D");
364 r.add("A", ()).after("B");
365 r.add("E", ()).after("F");
366 r.add("C", ()).after("D");
367 r.add("B", ()).after("C");
368 r.add("D", ()).after("E");
369 r.add("F", ()).after("A");
370 r.compile();
371 }
372
373 #[test]
374 #[should_panic(expected=r#"cyclic dependency"#)]
375 fn cyclic_dependency() {
376 let mut r = Ruler::new();
377 r.add("A", ()).after("B");
378 r.add("B", ()).after("C");
379 r.add("C", ()).after("A");
380 r.compile();
381 }
382
383
384 #[test]
385 #[should_panic(expected=r#"missing dependency: "C" requires "Z"#)]
386 fn missing_require() {
387 let mut r = Ruler::new();
388 r.add("A", ());
389 r.add("B", ()).require("A");
390 r.add("C", ()).require("Z");
391 r.compile();
392 }
393}