BDD

System\Text\RegularExpressions\Symbolic\BDD.cs (31)

22internal sealed class BDD : IComparable<BDD>, IEquatable<BDD> 37public static readonly BDD True = new BDD(TrueOrdinal, null, null); 42public static readonly BDD False = new BDD(FalseOrdinal, null, null); 48public readonly BDD? One; 54public readonly BDD? Zero; 66internal BDD(int ordinal, BDD? one, BDD? zero) 111BDD set = this; 144public override bool Equals(object? obj) => Equals(obj as BDD); 147public bool Equals(BDD? bdd) => 172BDD[] nodes = TopologicalSort(); 202var idmap = new Dictionary<BDD, long> 211BDD node = nodes[i]; 239private BDD[] TopologicalSort() 248var nonterminals = new List<BDD>[Ordinal + 1]; 249var sorted = new List<BDD>(); 250var toVisit = new Stack<BDD>(); 251var visited = new HashSet<BDD>(); 257BDD node = toVisit.Pop(); 271(nonterminals[node.Ordinal] ??= new List<BDD>()).Add(node); 342public static BDD Deserialize(ReadOnlySpan<byte> bytes) 365BDD[] nodes = new BDD[n]; 425BDD bdd = this; 443public bool IsEssentiallyBoolean([NotNullWhen(true)] out BDD? terminalActingAsTrue) 457var toVisit = new Stack<BDD>(); 458var visited = new HashSet<BDD>(); 463BDD? leaf = null; 467BDD node = toVisit.Pop(); 514public int CompareTo(BDD? other)

System\Text\RegularExpressions\Symbolic\BDDRangeConverter.cs (4)

17private readonly Dictionary<BDD, (uint, uint)[]> _rangeCache = new Dictionary<BDD, (uint, uint)[]>(); 25public static (uint, uint)[] ToRanges(BDD set) 97private (uint, uint)[] ToRangesFromOrdinal(BDD set)

System\Text\RegularExpressions\Symbolic\BitVectorSolver.cs (7)

9private readonly BDD[] _minterms; 13public BitVectorSolver(BDD[] minterms) 49public BitVector ConvertFromBDD(BDD set, CharSetSolver solver) 51BDD[] partition = _minterms; 71public BDD ConvertToBDD(BitVector set, CharSetSolver solver) 73BDD[] partition = _minterms; 76BDD result = solver.Empty;

System\Text\RegularExpressions\Symbolic\CharSetSolver.cs (98)

13/// Provides functionality to build character sets represented as <see cref="BDD"/>s 16internal sealed class CharSetSolver : ISolver<BDD> 20private static readonly BDD?[] s_asciiCache = new BDD[128]; 23private static BDD? s_nonAscii; 33private readonly Dictionary<(int ordinal, BDD? one, BDD? zero), BDD> _bddCache = new(); 39private readonly Dictionary<(int op, BDD a, BDD? b), BDD> _operationCache = new(); // op is BooleanOperation; using int to reuse generic instantiation with _bddCache 42public BDD NonAscii => 48public BDD CreateBDDFromChar(char c) 50BDD?[] ascii = s_asciiCache; 63BDD CreateBdd(ushort c) 65BDD bdd = BDD.True; 69GetOrCreateBDD(k, bdd, BDD.False) : 70GetOrCreateBDD(k, BDD.False, bdd); 77/// <summary>Identity function for <paramref name="set"/>, since <paramref name="set"/> is already a <see cref="BDD"/>.</summary> 78public BDD ConvertFromBDD(BDD set, CharSetSolver _) => set; 81BDD[]? ISolver<BDD>.GetMinterms() => null; 84/// <summary>Identity function for <paramref name="set"/>, since <paramref name="set"/> is already a <see cref="BDD"/>.</summary> 85public BDD ConvertToBDD(BDD set, CharSetSolver _) => set; 88internal BDD CreateBDDFromRanges(List<(char Lower, char Upper)> ranges) 90BDD bdd = Empty; 100string ISolver<BDD>.PrettyPrint(BDD characterClass, CharSetSolver solver) => PrettyPrint(characterClass); 103public string PrettyPrint(BDD set) 116BDD w = UnicodeCategoryConditions.WordLetter(this); 126BDD s = UnicodeCategoryConditions.WhiteSpace; 136BDD d = UnicodeCategoryConditions.GetCategory(UnicodeCategory.DecimalDigitNumber); 156/// <summary>Unions two <see cref="BDD"/>s to produce a new <see cref="BDD"/>.</summary> 157public BDD Or(BDD set1, BDD set2) => ApplyBinaryOp(BooleanOperation.Or, set1, set2); 159/// <summary>Unions <see cref="BDD"/>s to produce a new <see cref="BDD"/>.</summary> 160public BDD Or(ReadOnlySpan<BDD> sets) 167BDD result = sets[0]; 175/// <summary>Intersects two <see cref="BDD"/>s to produce a new <see cref="BDD"/>.</summary> 176public BDD And(BDD a, BDD b) => ApplyBinaryOp(BooleanOperation.And, a, b); 178/// <summary>Intersects <see cref="BDD"/>s to produce a new <see cref="BDD"/>.</summary> 179public BDD And(ReadOnlySpan<BDD> sets) 186BDD result = sets[0]; 194/// <summary>Negates a <see cref="BDD"/> to produce a new complement <see cref="BDD"/>.</summary> 195public BDD Not(BDD set) 208(int, BDD set, BDD?) key = ((int)BooleanOperation.Not, set, null); 209if (!_operationCache.TryGetValue(key, out BDD? result)) 219/// <see cref="BDD"/> recursively from <paramref name="set1"/> and <paramref name="set2"/>. 221private BDD ApplyBinaryOp(BooleanOperation op, BDD set1, BDD set2) 258if (!_operationCache.TryGetValue(((int)op, set1, set2), out BDD? result)) 260BDD one, two; 289public BDD Full => BDD.True; 292public BDD Empty => BDD.False; 295public bool IsFull(BDD set) => ApplyBinaryOp(BooleanOperation.Xor, set, Full) == Empty; 298public bool IsEmpty(BDD set) => set == Empty; 301/// Create a <see cref="BDD"/> representing the set of values in the range 304public BDD CreateBDDFromRange(char lower, char upper) 312BDD CreateBDDFromRangeImpl(uint lower, uint upper, int maxBit) 338BDD zero = CreateBDDFromRangeImpl(lower, upper, maxBit - 1); 344BDD one = CreateBDDFromRangeImpl(lower & ~mask, upper & ~mask, maxBit - 1); 350BDD zero = CreateBDDFromRangeImpl(lower, mask - 1, maxBit - 1); 352BDD one = CreateBDDFromRangeImpl(0, upper & ~mask, maxBit - 1); 362public BDD ReplaceTrue(BDD bdd, int terminal) 366BDD leaf = GetOrCreateBDD(terminal, null, null); 367return ReplaceTrueImpl(bdd, leaf, new Dictionary<BDD, BDD>()); 369BDD ReplaceTrueImpl(BDD bdd, BDD leaf, Dictionary<BDD, BDD> cache) 377if (!cache.TryGetValue(bdd, out BDD? result)) 379BDD one = ReplaceTrueImpl(bdd.One, leaf, cache); 380BDD zero = ReplaceTrueImpl(bdd.Zero, leaf, cache); 388private BDD GetOrCreateBDD(int ordinal, BDD? one, BDD? zero) 390ref BDD? bdd = ref CollectionsMarshal.GetValueRefOrAddDefault(_bddCache, (ordinal, one, zero), out _);

System\Text\RegularExpressions\Symbolic\ISolver.cs (5)

8/// <see cref="BDD"/> representations of those sets, and determining whether an element is in the set. 12/// <summary>Creates a set from a <see cref="BDD"/> representation.</summary> 13TSet ConvertFromBDD(BDD set, CharSetSolver solver); 46/// <summary>Converts the set into a <see cref="BDD"/> representation.</summary> 47BDD ConvertToBDD(TSet set, CharSetSolver solver);

System\Text\RegularExpressions\Symbolic\MintermClassifier.cs (2)

35public MintermClassifier(BDD[] minterms) 80static T[] CreateLookup<T>(BDD[] minterms, ReadOnlySpan<object> charRangesPerMinterm, int _maxChar) where T : IBinaryInteger<T>

System\Text\RegularExpressions\Symbolic\MintermGenerator.cs (1)

11/// <typeparam name="TSet">The type of set of elements (typically <see cref="BDD"/>, <see cref="BitVector"/> for more than 64 elements, or <see cref="ulong"/> for 64 or fewer elements).</typeparam>

System\Text\RegularExpressions\Symbolic\RegexNodeConverter.cs (39)

System\Text\RegularExpressions\Symbolic\SymbolicRegexMatcher.cs (4)

144/// <param name="bddBuilder">The <see cref="BDD"/>-based builder.</param> 145/// <param name="rootBddNode">The root <see cref="BDD"/>-based node from the pattern.</param> 150SymbolicRegexBuilder<BDD> bddBuilder, SymbolicRegexNode<BDD> rootBddNode, ISolver<TSet> solver,

System\Text\RegularExpressions\Symbolic\SymbolicRegexMatcher.Sample.cs (7)

42BDD asciiWordCharacters = charSetSolver.Or( 50BDD ascii = charSetSolver.CreateBDDFromRange('\x20', '\x7E'); 51BDD asciiNonWordCharacters = charSetSolver.And(ascii, charSetSolver.Not(asciiWordCharacters)); 170static BDD ToBDD(TSet set, ISolver<TSet> solver, CharSetSolver charSetSolver) => solver.ConvertToBDD(set, charSetSolver); 174static char ChooseChar(Random random, BDD bdd, BDD ascii, CharSetSolver charSetSolver) 178BDD bdd1 = charSetSolver.And(bdd, ascii);

System\Text\RegularExpressions\Symbolic\SymbolicRegexRunnerFactory.cs (3)

20var bddBuilder = new SymbolicRegexBuilder<BDD>(charSetSolver, charSetSolver); 23SymbolicRegexNode<BDD> rootNode = converter.ConvertToSymbolicRegexNode(regexTree.Root); 40BDD[] minterms = rootNode.ComputeMinterms(bddBuilder);

System\Text\RegularExpressions\Symbolic\UInt64Solver.cs (8)

12private readonly BDD[] _minterms; 15public UInt64Solver(BDD[] minterms) 61public ulong ConvertFromBDD(BDD set, CharSetSolver solver) 63BDD[] partition = _minterms; 96public BDD ConvertToBDD(ulong set, CharSetSolver solver) 98BDD[] partition = _minterms; 101BDD result = BDD.False;

System\Text\RegularExpressions\Symbolic\UnicodeCategoryConditions.cs (16)

10/// <summary>Utility class providing singleton <see cref="BDD"/>s for evaluating whether a character is part of a particular Unicode category.</summary> 17private static readonly BDD?[] s_categories = new BDD[UnicodeCategoryValueCount]; 19private static volatile BDD? s_whiteSpace; 21private static volatile BDD? s_wordLetter; 23private static volatile BDD? s_wordLetterForAnchors; 34/// <summary>Gets a <see cref="BDD"/> that represents the specified <see cref="UnicodeCategory"/>.</summary> 35public static BDD GetCategory(UnicodeCategory category) => 37Interlocked.CompareExchange(ref s_categories[(int)category], BDD.Deserialize(UnicodeCategoryRanges.GetSerializedCategory(category)), null) ?? 40/// <summary>Gets a <see cref="BDD"/> that represents the \s character class.</summary> 41public static BDD WhiteSpace => 43Interlocked.CompareExchange(ref s_whiteSpace, BDD.Deserialize(UnicodeCategoryRanges.SerializedWhitespaceBDD), null) ?? 46/// <summary>Gets a <see cref="BDD"/> that represents the \w character class.</summary> 48public static BDD WordLetter(CharSetSolver solver) => 66/// Gets a <see cref="BDD"/> that represents <see cref="WordLetter"/> together with the characters 70public static BDD WordLetterForAnchors(CharSetSolver solver) =>

System\Text\RegularExpressions\Symbolic\UnicodeCategoryRangesGenerator.cs (2)

67BDD[] catBDDs = new BDD[catMap.Count];