3
\$\begingroup\$

I was feeling like writing a new Uri parser. The previous one was too limited and wasn't able to parse the authority part. This one is also based on the pretty image here and can tokenize all parts. I drew the image as an ascii art below.


follow-up


Core

The implementation has a single method Tokenize that is the state-machine. It's so short that I thought it's not necessary to move any functionality into other methods (would you agree?).

This is inspired by the Tutorial: Write a Finite State Machine to parse a custom language in pure Python. However, I find the original implementation was too complex for C# because we can define states and their transitions in a more convenient way with tuples, attributes and a little bit of reflection. So I use the PatternAttribute to decorate each token of an enum. Later, State<TToken> uses them with an enum reflection to try to match the current char.

State<TToken> and Token<TToken> are generic because I'm going to use this also for parsing of command-line arguments.

The process starts with the first state on the list. Would you say this is fine or should I create one more state for this like Start or NewUri etc.? The linked examples does that.

public static class Tokenizer
{
    public static IEnumerable<Token<TToken>> Tokenize<TToken>(string value, IEnumerable<State<TToken>> states, Func<Token<TToken>> createToken)
    {
        states = states.ToList(); // Materialize states.

        var state = states.First();
        var token = createToken();
        token.Type = state.Next;

        foreach (var (oneChar, index) in value.Select((c, i) => (c.ToString(), i)))
        {
            // The state matches itself.
            if (state.IsMatch(oneChar))
            {
                token.Text.Append(oneChar);
            }
            else
            {
                yield return token;
                var isMatch = false;
                // Find states where the current one is `Prev`.
                foreach (var next in states.Where(s => s.Prev.Equals(token.Type)))
                {
                    // There is a match. Use this state from now on.
                    if ((isMatch = next.IsMatch(oneChar)))
                    {
                        // Initialize the new token.
                        token = createToken();
                        token.StartIndex = index;
                        token.Type = next.Next;
                        token.Text.Append(oneChar);
                        state = next;
                        // Got to the next character.
                        break;
                    }
                }

                // There was no match. This means the current char is invalid.
                if (!isMatch)
                {
                    throw new ArgumentException($"Invalid character at: {index}.");
                }
            }
        }

        // Yield the last token.
        if (token.Text.Length > 0)
        {
            yield return token;
        }
    }
}

public class PatternAttribute : Attribute
{
    private readonly string _pattern;
    public PatternAttribute([RegexPattern] string pattern) => _pattern = pattern;
    public bool IsMatch(string value) => Regex.IsMatch(value, _pattern);
}

public class State<TToken>
{
    public TToken Prev { get; set; }

    public TToken Next { get; set; }

    public bool IsMatch(string value)
    {
        return
            typeof(TToken)
                .GetField(Next.ToString())
                .GetCustomAttribute<PatternAttribute>()
                .IsMatch(value);
    }

    public override string ToString() => $"<-- {Prev} | {Next} -->";
}

public class Token<TToken>
{
    public int StartIndex { get; set; }

    public StringBuilder Text { get; set; } = new StringBuilder();

    public TToken Type { get; set; }

    public override string ToString() => $"{StartIndex}: {Text} ({Type})";
}

UriStringTokenizer

I encapsulate the raw API with my UriStringTokenizer to make easier to use. It defines all tokens and state transitions.

public static class UriStringTokenizer
{
    /*

     scheme:[//[userinfo@]host[:port]]path[?key=value&key=value][#fragment]
            [ ----- authority ----- ]     [ ----- query ------ ]

     scheme: ------------------------- path -------------------------  --------- UriString
            \                         /    \                         /\         /
             // --------- host ---- '/'     ?key ------ &key ------ /  #fragment
               \         /    \     /           \      /    \      /
                userinfo@      :port             =value      =value             

    */

    public static readonly ICollection<State<UriToken>> States = new (UriToken Prev, UriToken Next)[]
    {
        // self

        (Scheme, Scheme),
        (UserInfo, UserInfo),
        (Host, Host),
        (Port, Port),
        (Path, Path),
        (Key, Key),
        (Value, Value),
        (Fragment, Fragment),

        // transitions

        (Scheme, SchemeSuffix),
        (SchemeSuffix, Path),
        (SchemeSuffix, AuthorityPrefix),
        (AuthorityPrefix, UserInfo),
        (AuthorityPrefix, Host),
        (UserInfo, UserInfoSuffix),
        (UserInfoSuffix, Host),
        (Host, PathPrefix),
        (Host, PortPrefix),
        (PortPrefix, Port),
        (Port, PathPrefix),
        (PathPrefix, Path),
        (Path, KeyPrefix),
        (KeyPrefix, Key),
        (Key, ValuePrefix),
        (ValuePrefix, Value),
        (Value, KeyPrefix),
        (Key, FragmentPrefix),
        (Value, FragmentPrefix),
        (FragmentPrefix, Fragment)

        // --
    }.Select(t => new State<UriToken> { Prev = t.Prev, Next = t.Next, }).ToList();

    public static IEnumerable<Token<UriToken>> Tokenize(string value)
    {
        return Tokenizer.Tokenize(value, States, () => new Token<UriToken>());
    }
}

public enum UriToken
{
    [Pattern(@"[a-z]")]
    Scheme,

    [Pattern(@":")]
    SchemeSuffix,

    [Pattern(@"\/")]
    AuthorityPrefix,

    [Pattern(@"[a-z]")]
    UserInfo,

    [Pattern(@"@")]
    UserInfoSuffix,

    [Pattern(@"[a-z]")]
    Host,

    [Pattern(@":")]
    PortPrefix,

    [Pattern(@"[0-9]")]
    Port,

    [Pattern(@"\/")]
    PathPrefix,

    [Pattern(@"[a-z]")]
    Path,

    //QueryPrefix,

    [Pattern(@"[\?\&]")]
    KeyPrefix,

    [Pattern(@"[a-z]")]
    Key,

    [Pattern(@"=")]
    ValuePrefix,

    [Pattern(@"[a-z]")]
    Value,

    [Pattern(@"#")]
    FragmentPrefix,

    [Pattern(@"[a-z]")]
    Fragment,
}

Tests

Tests that I created are all green.

using static UriToken;

public class UriStringParserTest
{
    [Fact]
    public void Can_tokenize_full_URI()
    {
        // Using single letters for easier debugging.
        var uri = "s://u@h:1/p?k=v&k=v#f";
        var tokens = UriStringTokenizer.Tokenize(uri).ToList();

        var expectedTokens = new[]
        {
            Scheme,
            SchemeSuffix,
            AuthorityPrefix,
            UserInfo,
            UserInfoSuffix,
            Host,
            PortPrefix,
            Port,
            PathPrefix,
            Path,
            KeyPrefix,
            Key,
            ValuePrefix,
            Value,
            KeyPrefix,
            Key,
            ValuePrefix,
            Value,
            FragmentPrefix,
            Fragment
        };

        Assert.Equal(expectedTokens, tokens.Select(t => t.Type).ToArray());

        var actual = string.Join("", tokens.Select(t => t.Text));

        Assert.Equal(uri, actual);
    }

    [Theory]
    [InlineData("s://u@h:1/p?k=v&k=v#f")]
    [InlineData("s://u@h:1/p?k=v&k=v")]
    [InlineData("s://u@h:1/p?k=v")]
    [InlineData("s://u@h:1/p")]
    [InlineData("s:///p")]
    public void Can_tokenize_partial_URI(string uri)
    {
        // Using single letters for faster debugging.
        var tokens = UriStringTokenizer.Tokenize(uri).ToList();
        var actual = string.Join("", tokens.Select(t => t.Text));
        Assert.Equal(uri, actual);
    }

    [Fact]
    public void Throws_when_invalid_character()
    {
        var uri = "s://:u@h:1/p?k=v&k=v#f";
        //             ^ - invalid character

        var ex = Assert.Throws<ArgumentException>(() => UriStringTokenizer.Tokenize(uri).ToList());
        Assert.Equal("Invalid character at: 4.", ex.Message);
    }
}

Questions

Did I do anything terribly wrong? Does this solution have any obvious flaws that I have missed? How else would you improve it?


I use only basic patterns here because I was focused on the API and the state-machine. I will extend them later to match all characters that are valid for a Uri and its parts.

You can consider the input of the Tokenize method as already properly % encoded.

\$\endgroup\$
5
\$\begingroup\$

State Machine Review

This is an interesting, yet unorthodox implementation of a state machine. Your states are actually transitions. You don't really have a state, since the state machine (Tokenize method) processes input and performs all lifetime management of tokens itself. The only behavior dispatched to the transitions (unfortunately named State) is asking whether a match is available (IsMatch).


The problem with this approach, as VisualMelon has stated, is that you are walking each character at a time, which could lead to the wrong transition firing. The resolve this, you need to allow for look-ahead, and possibly also for backtracking. Rather than letting Tokenize traverse the input, you should let the current state handle the input. Each state is responsible for consuming as much characters it can. To allow this, wrap the input in a stream that supports look-ahead. Either create such class or use an existing API such as ANTLRInputStream.


Each state should have its own StringBuilder for building the current token. Once a token is completely built, create a token from the builder and store its result as immutable string in the result set of tokens.


The input of transitions should be cached, not in a global list, but dispatched to each state. Let each state store its own transitions (where transition.From == state). Whenever the state machine tells a state to process and cosume the input, the state should check its transitions whether a transition to a next state should be triggered. The self-transitions could be removed from the input and added in each state by default.


Creation of tokens and completing tokens should not be part of the state machine, but of entry and exit operations of the individual states. The state machine should only set the initial state and let that state consume the input. Whenever a transition fires from within a state, the state machine should set the current state to transition.To. The state machine should keep feeding the current state with the input until it's been completely processed.


As an overview:

  • let the state machine create the states and dispatch the provided transitions to each state
  • let the state machine set the initial state and feed the input to the current state
  • let each state create a token builder on entry
  • let each state process the input from current position and consume as much tokens possible
  • let each state check for transitions that could fire
  • let the state machine set the current state after a transition fired
  • let each state create a token from token builder on exit and store it in the result set

General Review

If you're materializing the states, why allowing the argument to be possibly lazy (IEnumerable)?

states = states.ToList(); // Materialize states.

Picking the initial state is by convention the first state. This should be well documented. Another option is provide a pseudo initial state with initial transitions. This way, you allow for multiple possible initial states (if more than just Scheme could start an URI, or when you want to reuse the API for other purposes).

var state = states.First();

The single character loop has been discussed by VisualMelon, and I have suggested an alternative where each state should consume the input stream at own expense.

foreach (var (oneChar, index) in value.Select((c, i) => (c.ToString(), i)))

A state machine should not need to care about handling actions on state and/or transition changes. Let states handle entry and exit (Moore machine). And let transitions handle their transition guard and optionally action (Mealy machine). UML specifies both Moore and Mealy support.

if (state.IsMatch(oneChar))
{
    token.Text.Append(oneChar);
}

Each state should have its own transitions, so this global lookup should no longer be required:

foreach (var next in states.Where(s => s.Prev.Equals(token.Type)))

The following part should be split into entry and exit behavior of the current state.

token = createToken();
token.StartIndex = index;
token.Type = next.Next;
token.Text.Append(oneChar);

On entry: create a token and token text builder, store the index, type. On exit: set the token builder's result as Text on the token and add the token to the result set.

\$\endgroup\$
  • 1
    \$\begingroup\$ digesting... but this much more complex then I expected it to be/have o_O I'm still not convinced that this is the only right way... I'll do it my way ;-P at least I'll try... this will be the lookahead... I migh have to backtrack later lol \$\endgroup\$ – t3chb0t Aug 24 at 15:18
  • \$\begingroup\$ When the behavior is well distributed over states and transitions, you can make a mature API for modelling many and complex use cases. You should at least taste such pattern ;-) \$\endgroup\$ – dfhwze Aug 24 at 15:22
  • 1
    \$\begingroup\$ I have rewritten my tokenizer by implementing many of your suggestion. I'm not sure you'll be proud of me however :-P some parts may still be unorthodox. \$\endgroup\$ – t3chb0t Aug 25 at 8:14
  • \$\begingroup\$ I am happy you considered my approach :p Now I have to rewrite my change trackers according to your suggestions! o_0 \$\endgroup\$ – dfhwze Aug 25 at 8:15
6
\$\begingroup\$

This isn't exhaustive, because I don't have much time now, so I might add some more later.


As I said in a comment, I don't buy the idea of looping over one char at a time: it's not documented that the patterns should match exactly one character, and it complicates the definitions of things like Scheme, which could be [a-z]+ and everyone would be happy. Of course, anytime you allow the user to use non-trivial regexes you have to take precautions, but this would allow things like look-aheads which could be useful.

My main complaint would be that it means you can't realisticly parse surrogate pairs, and if you expect to use this for anything other than URL-encoded URIs, then I think you need something more powerful. You could of course deal with surrogate pairs specifically, but that would just add complexity.

It also means that comments like // Using single letters for easier debugging are somewhat frighening, because they fail to test that the thing copes with non-single-length tokens. Most importantly, AuthorityPrefix appears to be required to be //, but your system will match / as well: this would require two states to parse one-char-at-a-time.

This seems like a grand oportunity to exploit the Regex.Match(string, int) overload, and parse the whole token at once, which may even simplify the implementation. I'll leave you the fun of implementing it... ;)


I don't like this:

foreach (var next in states.Where(s => s.Prev.Equals(token.Type)))

You should build a dictionary of prev/next pairs so that this things can hope with large numbers of transitions.

I'd be inclined to make Tokenize an instance member, so you can initialise a Tokenizer and reuse it. In my opinion this would provide a clearer API, and would make it easier to extend in future.


I'm not wild about Token having a StringBuilder. Rather, it looks like a good candidate for an immutable class with a string. This would complicate the token creation.

Either way, you should initialize the first token fully: there is no guarentee that createToken will set the StateIndex to 0.


It would be nice if the invalid character exception gave some more information (e.g. what the current state is, how much has already been parsed).


State.Next is a confusing name: I think this is what dfhwze was getting at in the comments: all your states are tied to a transition, and the naming goes a bit funky as a result.


The implemention of State.IsMatch is horrifying! I have no complaint with reflection, but this really should be cached, and you should probably build a single Regex object to reuse. Pre-loading the pattern would also create an exception somewhere useful (when the State is initialised) rather than when it is used. I also don't like that State is tied to the "enum with attribute" pattern: I'd rather it just had a regex attached, and a static method was provided to build it from the "enum with attribute" pattern. This would make the thing much more reusable. I'd actually be inclined to make IState (or whatever you call the thing that does the matching) an interface, so that it is completely general.

\$\endgroup\$
  • 1
    \$\begingroup\$ this is pretty convincing ;-] back to the drawing board \$\endgroup\$ – t3chb0t Aug 24 at 14:00
  • 2
    \$\begingroup\$ Wait for my addendum on this fine answer, or it's back to the drawing board again :p \$\endgroup\$ – dfhwze Aug 24 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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