|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
namespace Microsoft.TemplateEngine.Utils
{
public class Glob : IPatternMatcher
{
/// <summary>
/// Instance of Matcher satisfying all patterns tests.
/// </summary>
public static readonly IPatternMatcher MatchAll = new MatchAllGlob();
private readonly IReadOnlyList<IMatcher> _matchers;
private readonly bool _negate;
private readonly bool _isNameOnlyMatch;
private Glob(bool negate, IReadOnlyList<IMatcher> matchers, bool canBeNameOnlyMatch)
{
_negate = negate;
_matchers = matchers;
_isNameOnlyMatch = canBeNameOnlyMatch && !_matchers.Any(x => x is PathMatcher || x is ExactPathMatcher || (x as LiteralMatcher)?.Char?.FirstOrDefault() == '/');
}
private interface IMatcher
{
int MinConsume { get; }
bool ProducesCheckpoint { get; }
bool CanConsume(string test, int startAt, out int endPosition);
}
public static Glob Parse(string pattern, bool canBeNameOnlyMatch = true)
{
List<IMatcher> matchers = new();
int start = 0;
bool negate = false;
if (pattern.Length > 0 && pattern[0] == '!')
{
negate = true;
start = 1;
}
for (int i = start; i < pattern.Length; ++i)
{
switch (pattern[i])
{
case '\\':
if (i < pattern.Length - 1)
{
switch (pattern[i + 1])
{
case '[':
case ' ':
matchers.Add(new LiteralMatcher(pattern[i + 1]));
++i;
break;
default:
matchers.Add(new LiteralMatcher('\\'));
break;
}
}
else
{
matchers.Add(new LiteralMatcher('\\'));
}
break;
case '[':
List<char> values = new();
for (; i < pattern.Length; ++i)
{
if (pattern[i] == '\\')
{
if (i < pattern.Length - 1)
{
switch (pattern[i + 1])
{
case ']':
case '[':
case ' ':
++i;
values.Add(pattern[i]);
continue;
default:
break;
}
}
}
if (pattern[i] == ']')
{
break;
}
values.Add(pattern[i]);
}
matchers.Add(new LiteralMatcher(values));
break;
case '*':
if (pattern.Length > i + 1 && pattern[i + 1] == '*')
{
if (pattern.Length > i + 2 && pattern[i + 2] == '/')
{
matchers.Add(new ExactPathMatcher());
i += 2;
}
else
{
matchers.Add(new PathMatcher());
++i;
}
}
else
{
matchers.Add(new NameMatcher());
}
break;
default:
matchers.Add(new LiteralMatcher(pattern[i]));
break;
}
}
return new Glob(negate, matchers, canBeNameOnlyMatch);
}
public bool IsMatch(string test)
{
return _negate ^ IsMatchCore(test);
}
private bool IsMatchCore(string test)
{
Stack<Checkpoint> checkpoints = new();
int currentMatcher = 0;
int i = 0;
//See if we can just do a name match
if (_isNameOnlyMatch)
{
i = test.LastIndexOf('/') + 1;
}
while (i < test.Length)
{
IMatcher matcher = _matchers[currentMatcher];
//If the matcher has a minimum zero width, isn't the last matcher and produces a checkpoint,
// we don't need to actually test for a match at this stage
//Otherwise, test whether the matcher can consume starting at the current position
if ((currentMatcher < _matchers.Count - 1 && matcher.ProducesCheckpoint && matcher.MinConsume == 0) || matcher.CanConsume(test, i, out i))
{
//If the current matcher isn't that last one and it produces a checkpoint, stash
// the checkpoint info
if (currentMatcher < _matchers.Count - 1 && matcher.ProducesCheckpoint)
{
checkpoints.Push(new Checkpoint(matcher, currentMatcher + 1, i));
}
++currentMatcher;
if (currentMatcher < _matchers.Count)
{
continue;
}
if (matcher.ProducesCheckpoint)
{
if (i < test.Length)
{
--currentMatcher;
}
continue;
}
}
if (currentMatcher == _matchers.Count && i == test.Length)
{
return true;
}
//If the match failed or we ran out of matchers, try to revert to an earlier checkpoint to re-evaluate
//If we've got checkpoints left, back up one and see if it's usable
while (checkpoints.Count > 0)
{
Checkpoint checkpoint = checkpoints.Pop();
//If the matcher is usable...
// restore the checkpoint
// advance the string position
// reset the current matcher to the one that followed the checkpoint
if (checkpoint.Matcher.CanConsume(test, checkpoint.StringPosition, out i))
{
checkpoint.StringPosition = i;
currentMatcher = checkpoint.NextMatcherIndex;
checkpoints.Push(checkpoint);
break;
}
}
//If we ran out of checkpoints, the match has failed
if (checkpoints.Count == 0)
{
return false;
}
}
return i == test.Length && currentMatcher == _matchers.Count;
}
private class Checkpoint
{
public Checkpoint(IMatcher matcher, int nextMatcherIndex, int stringPosition)
{
Matcher = matcher;
NextMatcherIndex = nextMatcherIndex;
StringPosition = stringPosition;
}
public IMatcher Matcher { get; }
public int NextMatcherIndex { get; }
public int StringPosition { get; set; }
}
private class ExactPathMatcher : IMatcher
{
public int MinConsume => 0;
public bool ProducesCheckpoint => true;
public bool CanConsume(string test, int startAt, out int endPosition)
{
int nextSlash = test.IndexOf('/', startAt);
if (nextSlash > -1)
{
endPosition = nextSlash + 1;
return true;
}
endPosition = startAt;
return false;
}
public override string ToString()
{
return "**/";
}
}
private class LiteralMatcher : IMatcher
{
public LiteralMatcher(IEnumerable<char> c)
{
Char = new HashSet<char>(c);
}
public LiteralMatcher(char c)
{
Char = new HashSet<char> { c };
}
public ISet<char> Char { get; }
public int MinConsume => 1;
public bool ProducesCheckpoint => false;
public bool CanConsume(string test, int startAt, out int endPosition)
{
if (Char.Contains(test[startAt]))
{
endPosition = startAt + 1;
return true;
}
endPosition = startAt;
return false;
}
public override string ToString()
{
return Char.ToString();
}
}
private class NameMatcher : IMatcher
{
public int MinConsume => 0;
public bool ProducesCheckpoint => true;
public bool CanConsume(string test, int startAt, out int endPosition)
{
if (test[startAt] != '/')
{
endPosition = startAt + 1;
return true;
}
endPosition = startAt;
return false;
}
public override string ToString()
{
return "*";
}
}
private class PathMatcher : IMatcher
{
public int MinConsume => 0;
public bool ProducesCheckpoint => true;
public bool CanConsume(string test, int startAt, out int endPosition)
{
endPosition = startAt + 1;
return true;
}
public override string ToString()
{
return "**";
}
}
private class MatchAllGlob : IPatternMatcher
{
public MatchAllGlob()
{ }
/// <inheritdoc />
public bool IsMatch(string test) => true;
}
}
}
|