Implement a least upper bound for marks.

This is useful when trying to compute when something is lexically before
something else, but they aren't necessarily in the same SyntaxContext

1 files changed, 27 insertions, 0 deletions

diff --git a/src/libsyntax_pos/hygiene.rs b/src/libsyntax_pos/hygiene.rs
index 6eb662744c3..8e9564d0ac1 100644
--- a/src/libsyntax_pos/hygiene.rs
+++ b/src/libsyntax_pos/hygiene.rs
@@ -21,6 +21,7 @@ use symbol::{Ident, Symbol};
 
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 use std::collections::HashMap;
+use rustc_data_structures::fx::FxHashSet;
 use std::fmt;
 
 /// A SyntaxContext represents a chain of macro expansions (represented by marks).
@@ -117,6 +118,32 @@ impl Mark {
             true
         })
     }
+
+    /// Computes a mark such that both input marks are descendants of (or equal to) the returned
+    /// mark. That is, the following holds:
+    ///
+    /// ```rust
+    /// let lub = lub(a, b);
+    /// assert!(a.is_descendant_of(lub))
+    /// assert!(b.is_descendant_of(lub))
+    /// ```
+    pub fn lub(mut a: Mark, mut b: Mark) -> Mark {
+        HygieneData::with(|data| {
+            // Compute the path from a to the root
+            let mut a_path = FxHashSet::<Mark>();
+            while a != Mark::root() {
+                a_path.insert(a);
+                a = data.marks[a.0 as usize].parent;
+            }
+
+            // While the path from b to the root hasn't intersected, move up the tree
+            while !a_path.contains(&b) {
+                b =  data.marks[b.0 as usize].parent;
+            }
+
+            b
+        })
+    }
 }
 
 pub struct HygieneData {