implab/ImplabNet Commit - r183:4f82e0f161c3

fixed DFA optimization, JSON is fully functional

cin -

r183:4f82e0f161c3 ref20160224

parent child

Context file:

r183:4f82e0f161c3

Collapse all files

The requested changes are too big and content was truncated. Show full diff

MonoPlay/packages.config created 644 +4 0

@@ -0,0 +1,4
	1	<?xml version="1.0" encoding="utf-8"?>
	2	<packages>
	3	<package id="System.Text.Json" version="2.0.0.11" targetFramework="net45" />
	4	</packages> No newline at end of file

packages/NUnit.2.6.4/NUnit.2.6.4.nupkg created 644 binary 0 0

NO CONTENT: new file 100644, binary diff hidden

packages/NUnit.2.6.4/lib/nunit.framework.dll created 644 binary 0 0

NO CONTENT: new file 100644, binary diff hidden

packages/NUnit.2.6.4/lib/nunit.framework.xml created 644 0 0

	1	NO CONTENT: new file 100644			NO CONTENT: new file 100644
The requested commit or file is too big and content was truncated. Show full diff

packages/NUnit.2.6.4/license.txt created 644 0 0

	1	NO CONTENT: new file 100644			NO CONTENT: new file 100644
The requested commit or file is too big and content was truncated. Show full diff

packages/System.Text.Json.2.0.0.11/System.Text.Json.2.0.0.11.nupkg created 644 binary 0 0

NO CONTENT: new file 100644, binary diff hidden

packages/System.Text.Json.2.0.0.11/lib/net40/System.Text.Json.dll created 644 binary 0 0

NO CONTENT: new file 100644, binary diff hidden

Implab.Test/Implab.Format.Test/JsonTests.cs +72 -34

@@ -1,49 +1,87
1	using NUnit.Framework;	1	using NUnit.Framework;
2	using System;	2	using System;
3	using Implab.Formats.JSON;	3	using Implab.Formats.JSON;
		4	using Implab.Automaton;
4		5
5	namespace Implab.Format.Test {	6	namespace Implab.Format.Test {
6	[TestFixture]	7	[TestFixture]
7	public class JsonTests {	8	public class JsonTests {
8	[Test]	9	[Test]
9	public void TestScannerValidTokens() {	10	public void TestScannerValidTokens() {
10	var scanner = new JSONScanner(@"9123, -123, 0, 0.1, -0.2, -0.1e3, 1.3E-3, ""some \t\n\u0020 text"", literal []{}:");	11	using (var scanner = new JSONScanner(@"9123, -123, 0, 0.1, -0.2, -0.1e3, 1.3E-3, ""some \t\n\u0020 text"", literal []{}:")) {
		12
		13	Tuple<JsonTokenType,object>[] expexted = new [] {
		14	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 9123d),
		15	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		16	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -123d),
		17	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		18	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0d),
		19	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		20	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0.1d),
		21	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		22	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.2d),
		23	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		24	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.1e3d),
		25	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		26	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 1.3E-3d),
		27	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		28	new Tuple<JsonTokenType,object>(JsonTokenType.String, "some \t\n text"),
		29	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
		30	new Tuple<JsonTokenType,object>(JsonTokenType.Literal, "literal"),
		31	new Tuple<JsonTokenType,object>(JsonTokenType.BeginArray, " ["),
		32	new Tuple<JsonTokenType,object>(JsonTokenType.EndArray, "]"),
		33	new Tuple<JsonTokenType,object>(JsonTokenType.BeginObject, "{"),
		34	new Tuple<JsonTokenType,object>(JsonTokenType.EndObject, "}"),
		35	new Tuple<JsonTokenType,object>(JsonTokenType.NameSeparator, ":")
		36	};
11		37
12	Tuple<JsonTokenType,object>[] expexted = new [] {	38	object value;
13	~~new~~ ~~Tuple~~<~~JsonTokenType~~,~~objec~~t>(~~JsonT~~okenType.~~Number~~, ~~9123d~~),	39	JsonTokenType tokenType;
14	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	40	for (var i = 0; i < expexted.Length; i++) {
15	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -123d ),	41
16	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	42	Assert.IsTrue(scanner.ReadToken(out value, out tokenType));
17	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0d ),	43	Assert.AreEqual(expexted[i].Item1, tokenType);
18	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	44	Assert.AreEqual(expexted[i].Item2, value);
19	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0.1d ),	45	}
20	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	46
21	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.2d ),	47	Assert.IsFalse(scanner.ReadToken(out value, out tokenType));
22	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	48	}
23	new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.1e3d ),	49	}
24	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	50
25	new Tuple<JsonTokenType,object>(JsonTokenType.Number, 1.3E-3d ),	51	[Test]
26	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	52	public void TestScannerBadTokens() {
27	new Tuple<JsonTokenType,object>(JsonTokenType.String, "some \t\n text" ),	53	var bad = new [] {
28	new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", " ),	54	" 1",
29	new Tuple<JsonTokenType,object>(JsonTokenType.Literal, "literal" ),	55	" literal",
30	new Tuple<JsonTokenType,object>(JsonTokenType.BeginArray, " [" ),	56	" \"",
31	new Tuple<JsonTokenType,object>(JsonTokenType.EndArray, "]" ),	57	"\"unclosed string",
32	new Tuple<JsonTokenType,object>(JsonTokenType.BeginObject, "{" ),	58	"1.bad",
33	new Tuple<JsonTokenType,object>(JsonTokenType.EndObject, "}" ),	59	"001", // should be read as three numbers
34	new Tuple<JsonTokenType,object>(JsonTokenType.NameSeparator, ":" )	60	"--10",
		61	"+10",
		62	"1.0.0",
		63	"1e1.0",
		64	"l1teral0",
		65	".123",
		66	"-.123"
35	};	67	};
36		68
37	object value;	69	foreach (var json in bad)
38	JsonTokenType tokenType;	70	using (var scanner = new JSONScanner(json)) {
39	for (var i = 0; i < expexted.Length; i++) {	71	try {
40		72	object value;
41	Assert.IsTrue(scanner.ReadToken(out value, out tokenType));	73	JsonTokenType token;
42	Assert.AreEqual(expexted[i].Item1, tokenType);	74	scanner.ReadToken(out value, out token);
43	Assert.AreEqual(expexted[i].Item2, value);	75	if (!Object.Equals(value,json)) {
44	}	76	Console.WriteLine("'{0}' is read as {1}", json, value is String ? String.Format("'{0}'", value) : value );
45		77	continue;
46	Assert.IsFalse(scanner.ReadToken(out value, out tokenType));	78	}
		79	Assert.Fail("Token '{0}' shouldn't pass", json);
		80	} catch (ParserException e) {
		81	Console.WriteLine(e.Message);
		82	}
		83	}
		84
47	}	85	}
48	}	86	}
49	}	87	}

Implab/Automaton/DFATable.cs +20 -15

                     /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
                     /// </remarks>
                     /// <returns>The final states.</returns>
-                    protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
+                    protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
-                        return new HashSet<int>[] { m_finalStates };
+                        return new [] { new HashSet<int>(states) };
                     }
                     protected void Optimize(
                         var optimalStates = new HashSet<HashSet<int>>(setComparer);
                         var queue = new HashSet<HashSet<int>>(setComparer);
-                        // получаем конечные состояния, сгруппированные по маркерам
+                        optimalStates.Add(new HashSet<int>(FinalStates));
-                        optimalStates.UnionWith(
-                            GroupFinalStates()
-                        );
                         var state = new HashSet<int>(
                             Enumerable
                             for (int c = 0; c < m_symbolCount; c++) {
                                 var stateX = new HashSet<int>();
-                                //foreach(var a in stateA.Where(rmap.ContainsKey))
+                                foreach(var a in stateA.Where(rmap.ContainsKey))
-                                //    stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
+                                    stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
-                                stateX.UnionWith(m_transitions.Where(t => stateA.Contains(t.s2) && t.edge == c).Select(t => t.s1));
                                 var tmp = optimalStates.ToArray();
                                 foreach (var stateY in tmp) {
-                                    if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
+                                    var stateR1 = new HashSet<int>(stateY);
-                                        var stateR1 = new HashSet<int>(stateY);
+                                    var stateR2 = new HashSet<int>(stateY);
-                                        var stateR2 = new HashSet<int>(stateY);
-                                        stateR1.IntersectWith(stateX);
+                                    stateR1.IntersectWith(stateX);
-                                        stateR2.ExceptWith(stateX);
+                                    stateR2.ExceptWith(stateX);
+                                    if (stateR1.Count > 0 && stateR2.Count > 0) {
                                         optimalStates.Remove(stateY);
                                         optimalStates.Add(stateR1);
                             }
                         }
+                        // дополнительно разбиваем конечные состояния
+                        foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
+                            optimalStates.Remove(final);
+                            foreach (var split in SplitFinalStates(final))
+                                optimalStates.Add(split);
+                        }
                         // карта получения оптимального состояния по соотвествующему ему простому состоянию
                         var nextState = 0;
                         foreach (var item in optimalStates) {

Implab/Automaton/RegularExpressions/RegularDFA.cs +2 -6

                         // skip all unclassified symbols
                         foreach (var pair in alphaMap.Where(x => x.Value != 0))
                             alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
-                        var orig = ToString();
-                        var opt = dfa.ToString();
                         return dfa;
                     }
-                    protected override IEnumerable<HashSet<int>> GroupFinalStates() {
+                    protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
                         var arrayComparer = new CustomEqualityComparer<TTag[]>(
                             (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
                             x => x.Sum(it => x.GetHashCode())
                         );
-                        return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
+                        return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
                     }
                     public override string ToString() {

Implab/Formats/JSON/JSONGrammar.cs +3 -1

                         Literal,
                         NameSeparator,
                         ValueSeparator,
+                        Whitespace,
                         StringBound,
                         EscapedChar,
                             .Or(beginArray.Tag(TokenType.BeginArray))
                             .Or(endArray.Tag(TokenType.EndArray))
                             .Or(nameSep.Tag(TokenType.NameSeparator))
-                            .Or(valueSep.Tag(TokenType.ValueSeparator));
+                            .Or(valueSep.Tag(TokenType.ValueSeparator))
+                            .Or(SymbolSetToken('\n', '\r', '\t', ' ').Closure().Tag(TokenType.Whitespace));
                         var jsonStringExpression =

Implab/Formats/JSON/JSONScanner.cs +3 -1

                     /// в строках обрабатываются экранированные символы, числа становтся типа double.</remarks>
                     public bool ReadToken(out object tokenValue, out JsonTokenType tokenType) {
                         JSONGrammar.TokenType[] tag;
-                        if (m_jsonContext.Execute(m_scanner, out tag)) {
+                        while (m_jsonContext.Execute(m_scanner, out tag)) {
                             switch (tag[0]) {
                                 case JSONGrammar.TokenType.StringBound:
                                     tokenValue = ReadString();
                                     tokenValue = Double.Parse(m_scanner.GetTokenValue(), CultureInfo.InvariantCulture);
                                     tokenType = JsonTokenType.Number;
                                     break;
+                                case JSONGrammar.TokenType.Whitespace:
+                                    continue;
                                 default:
                                     tokenType = (JsonTokenType)tag[0];
                                     tokenValue = m_scanner.GetTokenValue();

Implab/Formats/ReaderScanner.cs +1 -1

             namespace Implab.Formats {
                 public class ReaderScanner: TextScanner {
-                    const int CHUNK_SIZE = 1024;
+                    const int CHUNK_SIZE = 1024*4;
                     const int BUFFER_MAX = CHUNK_SIZE*1024;
                     readonly TextReader m_reader;

MonoPlay/MonoPlay.csproj +6 0

               </PropertyGroup>
               <ItemGroup>
                 <Reference Include="System" />
+                <Reference Include="System.Text.Json">
+                  <HintPath>..\packages\System.Text.Json.2.0.0.11\lib\net40\System.Text.Json.dll</HintPath>
+                </Reference>
               </ItemGroup>
               <ItemGroup>
                 <Compile Include="Program.cs" />
                   <Name>Implab</Name>
                 </ProjectReference>
               </ItemGroup>
+              <ItemGroup>
+                <None Include="packages.config" />
+              </ItemGroup>
             </Project>

MonoPlay/Program.cs +26 -18

@@ -1,6 +1,9
1	using System;	1	using System;
2	using Implab;	2	using Implab;
3	using System.Threading.Tasks;	3	using System.Threading.Tasks;
		4	using Implab.Formats.JSON;
		5	using System.IO;
		6	using System.Text.Json;
4		7
5	namespace MonoPlay {	8	namespace MonoPlay {
6	class MainClass {	9	class MainClass {
@@ -9,28 +12,33 namespace MonoPlay {
9	public static void Main(string[] args) {	12	public static void Main(string[] args) {
10	if (args == null)	13	if (args == null)
11	throw new ArgumentNullException("args");	14	throw new ArgumentNullException("args");
12		15	int t1, t2;
13	var t1 = Environment.TickCount;
14
15	DoWork().GetAwaiter().GetResult();
16		16
17	var t2 = Environment.TickCount;	17	for (int i = 0; i < 2; i++) {
18	Console.WriteLine("done: {0} ms, {1:.00} Mb, {2} GC", t2 - t1, GC.GetTotalMemory(false) / (1024*1024), GC.CollectionCount(0) );	18	t1 = Environment.TickCount;
		19	int elements =0;
		20	using (var reader = new JSONParser(File.OpenText("/home/sergey/temp/citylots.json"))) {
		21	while (reader.Read())
		22	elements++;
		23	}
19		24
20	}	25	t2 = Environment.TickCount;
		26	Console.WriteLine("attempt {0} done: {1} ms, {2:.00} Mb, {3} GC, Elements: {4}",i+1, t2 - t1, GC.GetTotalMemory(false) / (1024*1024), GC.CollectionCount(0), elements );
		27	}
21		28
22	static IPromise<int> DoItem(int x) {	29	Console.WriteLine("Syste.Text.Json");
23	//return Promise<int>.FromResult(x + 1);	30	var paraser = new JsonParser();
24	var p = new Promise<int>();	31	for (int i = 0; i < 2; i++) {
25	p.Resolve(x+1);	32	t1 = Environment.TickCount;
26	return p;	33	using (var reader = File.OpenText("/home/sergey/temp/citylots.json")) {
27	}	34	paraser.Parse(reader);
		35	}
28		36
29	static async Task<int> DoWork() {	37	t2 = Environment.TickCount;
30	var c = 0;	38	Console.WriteLine("attempt {0} done: {1} ms, {2:.00} Mb, {3} GC, ",i+1, t2 - t1, GC.GetTotalMemory(false) / (1024*1024), GC.CollectionCount(0));
31	for (int i = 0; i < 10000000; i++)	39	}
32	c = await DoItem(c);	40
33	return c;	41
34	}	42	}
35		43
36	}	44	}

packages/repositories.config 0 0

	1	NO CONTENT: modified file			NO CONTENT: modified file
The requested commit or file is too big and content was truncated. Show full diff

General Comments 0

Write
Preview

You need to be logged in to leave comments. Login now

No TODOs yet

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages