1
\$\begingroup\$

A while ago, I wrote a small Rust crate for parsing & generating URLs for GitHub repositories in various formats (HTTPS, SSH, git://, etc.), with the parsing done using regular expressions with the fancy-regex crate. However, the regular expressions weren't all that complicated, and so, in an effort to cut down on dependencies and streamline the size of the resulting binary, I eventually decided to hand-roll a parser instead, reducing the size of the binary by more than half.

The parsing uses a state machine for switching between the parts of the various URL formats, and the data-to-be-parsed is managed by a pull parser. This is my first time writing a state machine, and I'm mainly wondering how idiomatic/conventional/standard the code is.

I'm also wondering if the Rust can be made more idiomatic in some places (mostly around extracting substrings from strings, plus the big iteration through an array of pairs), as I'm still new to Rust.

Tests have been omitted for brevity, but you can see them in the full source file here.

Any and all critiques are welcome!

/// Split a string into a maximal prefix of chars that match `pred` and the
/// remainder of the string
fn span<P>(s: &str, mut pred: P) -> (&str, &str)
where
    P: FnMut(char) -> bool,
{
    match s.find(|c| !pred(c)) {
        Some(i) => s.split_at(i),
        None => s.split_at(s.len()),
    }
}

/// If `s` starts with a valid GitHub owner (i.e., user or organization) name,
/// return the owner and the remainder of `s`.
pub(crate) fn split_owner(s: &str) -> Option<(&str, &str)> {
    let (owner, rem) = span(s, is_owner_char);
    if owner.is_empty() || owner.eq_ignore_ascii_case("none") {
        None
    } else {
        Some((owner, rem))
    }
}

fn is_owner_char(c: char) -> bool {
    c.is_ascii_alphanumeric() || c == '-' || c == '_'
}

/// If `s` starts with a valid GitHub repository name, return the name and the
/// remainder of `s`.
pub(crate) fn split_name(s: &str) -> Option<(&str, &str)> {
    let (name, rem) = span(s, is_name_char);
    let (name, rem) = match name.len().checked_sub(4) {
        Some(i) if name.get(i..).unwrap_or("").eq_ignore_ascii_case(".git") => s.split_at(i),
        _ => (name, rem),
    };
    if name.is_empty() || name == "." || name == ".." {
        None
    } else {
        Some((name, rem))
    }
}

fn is_name_char(c: char) -> bool {
    c.is_ascii_alphanumeric() || c == '-' || c == '_' || c == '.'
}

/// If `s` starts with a prefix of the form `OWNER/NAME`, where `OWNER` is a
/// valid GitHub owner and `NAME` is a valid GitHub repository name, return the
/// owner, the name, and the remainder of `s`.
pub(crate) fn split_owner_name(s: &str) -> Option<(&str, &str, &str)> {
    let (owner, s) = split_owner(s)?;
    let s = s.strip_prefix('/')?;
    let (name, s) = split_name(s)?;
    Some((owner, name, s))
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
enum State {
    Start,
    Http,
    Web,
    OwnerName,
    OwnerNameGit,
    End,
}

#[derive(Copy, Clone, Debug, Eq, PartialEq)]
enum Token {
    /// A string to match exactly
    Literal(&'static str),
    /// A string to match regardless of differences in ASCII case
    CaseFold(&'static str),
}

impl From<&'static str> for Token {
    fn from(s: &'static str) -> Token {
        Token::Literal(s)
    }
}

/// If `s` is a valid GitHub repository URL, return the repository owner &
/// name.  The following URL formats are recognized:
///
/// - `[http[s]://[<username>[:<password>]@]][www.]github.com/<owner>/<name>[.git][/]`
/// - `[http[s]://]api.github.com/repos/<owner>/<name>`
/// - `git://github.com/<owner>/<name>[.git]`
/// - `[email protected]:<owner>/<name>[.git]`
/// - `ssh://[email protected]/<owner>/<name>[.git]`
pub(crate) fn parse_github_url(s: &str) -> Option<(&str, &str)> {
    // Notes on case sensitivity:
    // - Schemes & hostnames in URLs are case insensitive per RFC 3986 (though
    //   `git clone` as of Git 2.38.1 doesn't actually accept non-lowercase
    //   schemes).
    // - The "repos" in an API URL is case sensitive; changing the case results
    //   in a 404.
    // - The "git" username in SSH URLs (both forms) is case sensitive;
    //   changing the case results in a permissions error.
    // - The optional ".git" suffix is case sensitive; changing the case (when
    //   cloning with `git clone`, at least) results in either a credentials
    //   prompt for HTTPS URLs (the same as if you'd specified a nonexistent
    //   repo) or a "repository not found" message for SSH URLs.
    let mut parser = PullParser::new(s);
    let mut state = State::Start;
    let mut result: Option<(&str, &str)> = None;
    loop {
        state = match state {
            State::Start => [
                (vec![Token::CaseFold("https://")], State::Http),
                (vec![Token::CaseFold("http://")], State::Http),
                (
                    vec![Token::CaseFold("api.github.com"), "/repos/".into()],
                    State::OwnerName,
                ),
                (
                    vec![Token::CaseFold("git://github.com/")],
                    State::OwnerNameGit,
                ),
                (
                    vec!["git@".into(), Token::CaseFold("github.com:")],
                    State::OwnerNameGit,
                ),
                (
                    vec![
                        Token::CaseFold("ssh://"),
                        "git@".into(),
                        Token::CaseFold("github.com/"),
                    ],
                    State::OwnerNameGit,
                ),
            ]
            .into_iter()
            .find_map(|(token, transition)| parser.consume_seq(token).and(Some(transition)))
            .unwrap_or(State::Web),
            State::Http => {
                if parser
                    .consume_seq([Token::CaseFold("api.github.com"), "/repos/".into()])
                    .is_some()
                {
                    State::OwnerName
                } else {
                    parser.maybe_consume_userinfo();
                    State::Web
                }
            }
            State::Web => {
                parser.maybe_consume(Token::CaseFold("www."));
                parser.consume(Token::CaseFold("github.com/"))?;
                result = Some(parser.get_owner_name()?);
                parser.maybe_consume(".git".into());
                parser.maybe_consume("/".into());
                State::End
            }
            State::OwnerName => {
                result = Some(parser.get_owner_name()?);
                State::End
            }
            State::OwnerNameGit => {
                result = Some(parser.get_owner_name()?);
                parser.maybe_consume(".git".into());
                State::End
            }
            State::End => return if parser.at_end() { result } else { None },
        }
    }
}

struct PullParser<'a> {
    data: &'a str,
}

impl<'a> PullParser<'a> {
    fn new(data: &'a str) -> Self {
        Self { data }
    }

    fn consume_seq<I>(&mut self, tokens: I) -> Option<()>
    where
        I: IntoIterator<Item = Token>,
    {
        let orig = self.data;
        for t in tokens.into_iter() {
            if self.consume(t).is_none() {
                self.data = orig;
                return None;
            }
        }
        Some(())
    }

    fn consume(&mut self, token: Token) -> Option<()> {
        match token {
            Token::Literal(s) => match self.data.strip_prefix(s) {
                Some(t) => {
                    self.data = t;
                    Some(())
                }
                None => None,
            },
            Token::CaseFold(s) => {
                let i = s.len();
                match self.data.get(..i).zip(self.data.get(i..)) {
                    Some((t, u)) if t.eq_ignore_ascii_case(s) => {
                        self.data = u;
                        Some(())
                    }
                    _ => None,
                }
            }
        }
    }

    fn maybe_consume(&mut self, token: Token) {
        let _ = self.consume(token);
    }

    fn get_owner_name(&mut self) -> Option<(&'a str, &'a str)> {
        let (owner, name, s) = split_owner_name(self.data)?;
        self.data = s;
        Some((owner, name))
    }

    /// If the current state starts with a (possibly empty) URL userinfo field
    /// followed by a `@`, consume them both.
    fn maybe_consume_userinfo(&mut self) {
        // cf. <https://datatracker.ietf.org/doc/html/rfc3986#section-3.2.1>
        if let Some((userinfo, s)) = self.data.split_once('@') {
            if userinfo.chars().all(is_userinfo_char) {
                self.data = s;
            }
        }
    }

    fn at_end(&self) -> bool {
        self.data.is_empty()
    }
}

fn is_userinfo_char(c: char) -> bool {
    // RFC 3986 requires that percent signs be followed by two hex digits, but
    // we're not going to bother enforcing that.
    c.is_ascii_alphanumeric() || "-._~!$&'()*+,;=%:".contains(c)
}
```
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

First of all, it's a well-structured program. It's easy to read, and the various comments are helpful. Neat!

I still have a few nitpicks, but not much!

Function scopes are cool

In Rust, it's possible to define a new item (struct, trait, impl, trait impl, function, etc...) at any scope, even inside a function.

You have a number of functions that are only ever used by one other function. You could make it clearer that they have only one user by defining them straight within the function that use them.

pub(crate) fn split_owner(s: &str) -> Option<(&str, &str)> {
    fn is_owner_char(c: char) -> bool {
        c.is_ascii_alphanumeric() || c == '-' || c == '_'
    }

    let (owner, rem) = span(s, is_owner_char);
    if owner.is_empty() || owner.eq_ignore_ascii_case("none") {
        None
    } else {
        Some((owner, rem))
    }
}

Make more string manipulation functions

str has pretty nifty struct manipulation functions, in particular: strip_suffix.

Unfortunately, it misses the case-insensitive version, but you can write it to simplify your code:

    fn strip_suffix_ignore_ascii_case<'a>(this: &'a str, suffix: &str)
        -> Option<&'a str>
    {
        let index = this.len().checked_sub(suffix.len())?;
        let suffix = this.get(index..);

        suffix.eq_ignore_ascii_case(".git").then(|| this.get(..index))
    }

And simplify that split_name a bit.

Avoid allocations

Try to avoid allocations in parse_github_url by using slices &[Token::...][..] instead of vec![Token:...].

\$\endgroup\$
2
  • \$\begingroup\$ I tried to follow your last bit of advice and change vec![Token...] to &[Token...][..], but that gave me the error "type mismatch resolving <&[parser::Token] as std::iter::IntoIterator>::Item == parser::Token". \$\endgroup\$
    – jwodder
    Nov 24, 2022 at 17:12
  • \$\begingroup\$ @jwodder: Indeed, in that case the iterator will yield &Token instead. Is that a problem? \$\endgroup\$ Nov 24, 2022 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.