1 files changed, 280 insertions, 0 deletions
diff --git a/development/tools/cargo-workspace2/src/query/mod.rs b/development/tools/cargo-workspace2/src/query/mod.rs
new file mode 100644
index 000000000000..a888f6571663
--- /dev/null
+++ b/development/tools/cargo-workspace2/src/query/mod.rs
@@ -0,0 +1,280 @@
+//! Parse the query language for the CLI and other tools
+//!
+//! The `cargo-ws2` query language (`ws2ql`) allows users to specify a
+//! set of inputs, and an operation to execute on it.
+//!
+//! ## Basic rules
+//!
+//! * Inside `[]` are sets (meaning items de-dup) that don't require
+//!   reparations
+//! * IF `[]` contains a `/` anywhere _but_ the beginning AND end,
+//!   query becomes a path glob
+//! * IF `[]` contains `/` at start and end, query becomes a regex
+//! * An operation is parsed in the order of the fields in it's struct
+//!   (so publish order is `type mod devel`, etc)
+//! * Inside `{}` you can create dependency maps with arrows.
+//! * `{ foo < }` represents all crates that depend on `foo`
+//! * `{ foo < bar < }` represents all crates that depend on `foo` AND `bar`
+//! * `{ foo < bar |< }` represents all crates that depend on `foo` but NOT on `bar`
+//!
+//! ... etc.
+
+use crate::models::{CrateId, DepGraph};
+
+mod executor;
+
+/// A query on the dependency graph
+#[derive(Debug)]
+pub enum Query {
+    /// Simple set of names `[ a b c ]`
+    Set(Vec<String>),
+    /// Simple path glob query `./foo/*`
+    Path(String),
+    /// Regular expression done on paths in tree `/foo\$/`
+    Regex(String),
+    /// A dependency graph query (see documentation for rules)
+    DepGraph(Vec<DepConstraint>),
+}
+
+impl Query {
+    /// Parse an argument iterator (provided by `std::env::args`)
+    pub fn parse<'a>(line: impl Iterator<Item = String>) -> (Self, Vec<String>) {
+        let parser = QueryParser::new(line.skip(1).collect());
+        match parser.run() {
+            Some((q, rest)) => (q, rest),
+            None => {
+                eprintln!("Failed to parse query!");
+                std::process::exit(2);
+            }
+        }
+    }
+
+    /// Execute a query with a dependency graph
+    pub fn execute(self, g: &DepGraph) -> Vec<CrateId> {
+        match self {
+            Self::Set(ref crates) => executor::set(crates, g),
+            Self::DepGraph(deps) => executor::deps(deps, g),
+            _ => todo!(),
+        }
+    }
+}
+
+/// Express a dependency constraint
+#[derive(Debug)]
+pub struct DepConstraint {
+    pub _crate: String,
+    pub constraint: Constraint,
+}
+
+/// All constraints can be negated
+#[derive(Debug)]
+pub enum Constraint {
+    Initial(bool),
+    And(bool),
+    Or,
+}
+
+struct QueryParser {
+    line: Vec<String>,
+}
+
+impl QueryParser {
+    fn new(line: Vec<String>) -> Self {
+        Self { line }
+    }
+
+    /// Run the parser until it yields an error or finished query
+    fn run(mut self) -> Option<(Query, Vec<String>)> {
+        let line: Vec<String> =
+            std::mem::replace(&mut self.line, vec![])
+                .into_iter()
+                .fold(vec![], |mut vec, line| {
+                    line.split(" ").for_each(|seg| {
+                        vec.push(seg.into());
+                    });
+                    vec
+                });
+
+        // This is here to get around infinately sized enums
+        #[derive(Debug)]
+        enum Brace {
+            Block,
+            Curly,
+        }
+
+        // Track the state of the query braces
+        #[derive(Debug)]
+        enum BraceState {
+            Missing,
+            BlockOpen,
+            CurlyOpen,
+            Done(Brace),
+        }
+        use {Brace::*, BraceState::*};
+        let mut bs = Missing;
+        let mut buf = vec![];
+        let mut cbuf = String::new(); // Store a single crate name as a buffer
+        let mut skip = 1;
+
+        // Parse the crate set
+        for elem in &line {
+            match (&bs, elem.as_str()) {
+                // The segment starts with a [
+                (Missing, e) if e.starts_with("[") => {
+                    bs = BlockOpen;
+                    // Handle the case where we need to grab the crate from this segment
+                    if let Some(_crate) = e.strip_prefix("[") {
+                        if _crate != "" {
+                            buf.push(_crate.to_string());
+                        }
+                    }
+                }
+                // The segment starts with a {
+                (Missing, e) if e.starts_with("{") => {
+                    bs = CurlyOpen;
+
+                    if let Some(_crate) = e.strip_prefix("{") {
+                        if _crate != "" {
+                            cbuf = _crate.into();
+                        }
+                    }
+                }
+                (BlockOpen, e) if e.ends_with("]") => {
+                    if let Some(_crate) = e.strip_suffix("]") {
+                        if _crate != "" {
+                            buf.push(_crate.to_string());
+                        }
+                    }
+
+                    bs = Done(Block);
+                    break;
+                }
+                (BlockOpen, _crate) => buf.push(_crate.to_string()),
+                (CurlyOpen, e) if e.ends_with("}") && cbuf == "" => {
+                    bs = Done(Curly);
+                    break;
+                }
+                (CurlyOpen, e) if e.ends_with("}") && cbuf != "" => {
+                    eprintln!("[ERROR]: Out of place `}}`, expected operand!");
+                    std::process::exit(2);
+                }
+                (CurlyOpen, op) if cbuf != "" => {
+                    buf.push(format!("{} $ {}", cbuf, op));
+                    cbuf = "".into();
+                }
+                (CurlyOpen, _crate) => {
+                    cbuf = _crate.into();
+                }
+                (_, _) => {}
+            }
+            skip += 1;
+        }
+
+        let rest = line.into_iter().skip(skip).collect();
+        match bs {
+            Done(Block) => Some((Query::Set(buf), rest)),
+            Done(Curly) => {
+                let mut init = true;
+
+                let c: Vec<_> = buf
+                    .into_iter()
+                    .map(|val| {
+                        let mut s: Vec<_> = val.split("$").collect();
+                        let _crate = s.remove(0).trim().to_string();
+                        let c = s.remove(0).trim().to_string();
+
+                        DepConstraint {
+                            _crate,
+                            constraint: match c.as_str() {
+                                "<" if init => {
+                                    init = false;
+                                    Constraint::Initial(true)
+                                }
+                                "!<" if init => {
+                                    init = false;
+                                    Constraint::Initial(false)
+                                }
+                                "&<" => Constraint::And(true),
+                                "!&<" => Constraint::And(false),
+                                "|<" => Constraint::Or,
+                                c => {
+                                    eprintln!("[ERROR]: Invalid constraint: `{}`", c);
+                                    std::process::exit(2);
+                                }
+                            },
+                        }
+                    })
+                    .collect();
+
+                if c.len() < 1 {
+                    eprintln!("[ERROR]: Provided an empty graph set: {{ }}.  At least one dependency required!");
+                    std::process::exit(2);
+                }
+
+                Some((Query::DepGraph(c), rest))
+            }
+            _ if rest.len() < 1 => crate::cli::render_help(2),
+            _line => {
+                eprintln!("[ERROR]: You reached some unimplemented code in cargo-ws2! \
+                           This might be a bug, or it might be a missing feature.  Contact me with your query, \
+                           and we can see which one it is :)");
+                std::process::exit(2);
+            }
+        }
+    }
+}
+
+#[test]
+fn block_parser_spaced() {
+    let _ = QueryParser::new(
+        vec!["", "[", "foo", "bar", "baz", "]", "publish", "minor"]
+            .into_iter()
+            .map(Into::into)
+            .collect(),
+    )
+    .run();
+}
+
+#[test]
+fn block_parser_offset_front() {
+    let _ = QueryParser::new(
+        vec!["my-program", "[foo", "bar", "baz", "]", "publish", "minor"]
+            .into_iter()
+            .map(Into::into)
+            .collect(),
+    )
+    .run();
+}
+
+#[test]
+fn block_parser_offset_back() {
+    let _ = QueryParser::new(
+        vec!["my-program", "[", "foo", "bar", "baz]", "publish", "minor"]
+            .into_iter()
+            .map(Into::into)
+            .collect(),
+    )
+    .run();
+}
+
+#[test]
+fn block_parser_offset_both() {
+    let _ = QueryParser::new(
+        vec!["my-program", "[foo", "bar", "baz]", "publish", "minor"]
+            .into_iter()
+            .map(Into::into)
+            .collect(),
+    )
+    .run();
+}
+
+#[test]
+fn curly_parser_simple() {
+    let _ = QueryParser::new(
+        vec!["my-program", "{ foo < bar &< }", "print"]
+            .into_iter()
+            .map(Into::into)
+            .collect(),
+    )
+    .run();
+}