Commits

Timwi committed 6d4fd58

* Bug fix: trace feature would sometimes crash with NullReferenceException because nodes are nulled to conserve memory. Fix this by only nulling them if we're not in a function that is being traced
* Trace feature now decodes and displays valid lists (as well as strings)
* Trace feature now nice and colorful
* Bug fix in getExpression() where letNodes can be null
* Bug fix where an empty source file would cause compile failure even if all other source files constituted a valid program
* Remove an unused function
* Bug fix where a NAND node connected to itself was not parsed correctly. Now works, enabling the Starkov Construct
* Bail out with compile error if a splitter is connected to itself (instead of stack-overflowing)

Comments (4)

    1. Timwi author

      The Roman Loop would only create infinite-loop programs anyway, so it serves no purpose. The Starkov Construct, on the other hand, is really useful, so... :)

      1. Roman Starkov

        The Roman Loop could be used to demo how the evaluation proceeds. For example, place it into a function with two outputs, connecting it to the second output. Then invoke the function, connecting the first output to the program's output, and the second output to a Starkov Construct, demonstrating that no infinite loop occurs.

        1. Timwi author

          Interesting idea. My first thought was it wouldn’t be possible because the Roman Loop stands by itself and would be disconnected from the rest of the function, and thus not count as part of the function, but then it occurred to me that you can use a cross-nop to connect it to the rest of the function...

Files changed (3)

FuncitonFunction.cs

             public Node NextToEvaluate(List<string> traceFunctions)
             {
                 var res = nextToEvaluate();
-                if (traceFunctions != null && res == null && !(this is LiteralNode) && traceFunctions.Contains(_thisFunction.Name))
-                {
-                    if (_alreadyTraced == null)
-                        _alreadyTraced = new HashSet<Node>();
-                    if (_alreadyTraced.Add(this))
-                        Console.WriteLine("{0}: {1} = {2} (\"{3}\")", _thisFunction.Name, getExpression(null, false), _result, Helpers.CLiteralEscape(FuncitonLanguage.IntegerToString(_result)));
-                }
+                if (traceFunctions != null && traceFunctions.Contains(_thisFunction.Name))
+                    trace(res);
+                else
+                    releaseMemory();
                 return res;
             }
-            private static HashSet<Node> _alreadyTraced;
+
+            private void trace(Node res)
+            {
+                // Only output a trace if this node is fully evaluated
+                if (res != null)
+                    return;
+
+                // Don’t bother showing extra trace lines for literals
+                if (this is LiteralNode)
+                    return;
+
+                // Only output a trace if we haven’t already done so for this node
+                if (!_alreadyTraced.Add(this))
+                    return;
+
+                // See if the result happens to be a valid string
+                string str;
+                try { str = string.Format(@"""{0}""", Helpers.CLiteralEscape(FuncitonLanguage.IntegerToString(_result))); }
+                catch { str = null; }
+
+                // See if the result happens to be a valid list
+                string list = null;
+                try
+                {
+                    if (_result < 0)
+                        goto notAValidList;
+                    var intList = new List<BigInteger>();
+                    var result = _result;
+                    var mask = (BigInteger.One << 22) - 1;
+                    while (result > 0)
+                    {
+                        var curItem = BigInteger.Zero;
+                        while (true)
+                        {
+                            bool endHere = (result & 1) == 1;
+                            curItem = (curItem << 21) | ((result & mask) >> 1);
+                            result >>= 22;
+                            if (endHere)
+                                break;
+                            if (result == 0)
+                                goto notAValidList;
+                        }
+                        if ((result & 1) == 1)
+                            curItem = ~curItem;
+                        result >>= 1;
+                        intList.Add(curItem);
+                    }
+                    list = string.Format(@"[{0}]", string.Join(", ", intList));
+                    notAValidList: ;
+                }
+                catch { }
+
+                ConsoleWriteLineColored(
+                    ConsoleColor.White, _thisFunction.Name, ": ",
+                    ConsoleColor.Gray, getExpression(null, false),
+                    ConsoleColor.White, " = ",
+                    ConsoleColor.Green, _result.ToString(),
+                    str == null ? null : new object[] { Environment.NewLine, ConsoleColor.DarkCyan, "        ", str },
+                    list == null ? null : new object[] { Environment.NewLine, ConsoleColor.DarkMagenta, "        ", list });
+            }
+
+            private void ConsoleWriteLineColored(params object[] objs)
+            {
+                ConsoleWriteColored(objs);
+                Console.WriteLine();
+                Console.ResetColor();
+            }
+
+            private void ConsoleWriteColored(params object[] objs)
+            {
+                foreach (var item in objs)
+                    if (item is ConsoleColor)
+                        Console.ForegroundColor = (ConsoleColor) item;
+                    else if (item is object[])
+                        ConsoleWriteColored((object[]) item);
+                    else if (item != null)
+                        Console.Write(item);
+            }
+
+            // This is a static field rather than a boolean instance field because an instance field would make
+            // every Node instance larger and thus use significantly more memory even when not tracing.
+            private static HashSet<Node> _alreadyTraced = new HashSet<Node>();
 
             protected abstract Node nextToEvaluate();
+            protected abstract void releaseMemory();
 
             protected BigInteger _result;
             protected BigInteger _previousSubresult;
                 {
                     case 0:
                         _state = 1;
-                        var ret = CallNode.ClonedFunctionOutputs[OutputPosition];
-                        CallNode = null;
-                        return ret;
+                        return CallNode.ClonedFunctionOutputs[OutputPosition];
                     case 1:
                         _result = _previousSubresult;
                         _state = 2;
                 }
             }
 
+            protected override void releaseMemory()
+            {
+                if (_state == 1)
+                    CallNode = null;
+            }
+
             protected override FuncitonFunction findFunction(string functionName, HashSet<Node> alreadyVisited)
             {
                 if (functionName == CallNode.Function.Name)
                 // Detect single-parameter, single-output functions (e.g. “ℓ”)
                 var inputIndexes = CallNode.Inputs.Select((node, i) => node == null ? -1 : i).Where(i => i != -1).ToArray();
                 var outputIndexes = CallNode.Function._outputNodes.Select((node, i) => node == null ? -1 : i).Where(i => i != -1).ToArray();
-                var config = string.Join("", outputIndexes) + string.Join("", inputIndexes);
                 if (inputIndexes.Length == 1 && outputIndexes.Length == 1)
                     return CallNode.Function.Name + "(" + CallNode.Inputs.Select((inp, ind) => inp == null ? null : inp.GetExpression(letNodes, false, false)).First(str => str != null) + ")";
 
                 // Detect two-opposite-parameter, single-perpendicular-output functions (normally binary operators, e.g. “<”)
+                var config = string.Join("", outputIndexes) + string.Join("", inputIndexes);
                 if (inputIndexes.Length == 2 && (config == "013" || config == "302"))
                     return open + CallNode.Inputs[inputIndexes[1]].GetExpression(letNodes, false, true) + " " + CallNode.Function.Name + " " + CallNode.Inputs[inputIndexes[0]].GetExpression(letNodes, false, true) + close;
                 else if (inputIndexes.Length == 2 && (config == "102" || config == "213"))
             private BigInteger _leftEval;
             protected override Node nextToEvaluate()
             {
-                Node ret = null;
                 switch (_state)
                 {
                     case 0:
                         _state = 1;
-                        ret = Left;
-                        Left = null;
-                        return ret;
+                        return Left;
                     case 1:
                         if (_previousSubresult.IsZero)
                         {
                             _result = BigInteger.MinusOne;
                             _state = 3;
+                            return null;
                         }
                         else
                         {
                             _leftEval = _previousSubresult;
                             _state = 2;
-                            ret = Right;
+                            return Right;
                         }
-                        Right = null;
-                        return ret;
                     case 2:
                         _result = ~(_leftEval & _previousSubresult);
                         _state = 3;
                 }
             }
 
+            protected override void releaseMemory()
+            {
+                if (_state == 1)
+                    Left = null;
+                else if (_state > 1)
+                    Right = null;
+            }
+
             protected override FuncitonFunction findFunction(string functionName, HashSet<Node> alreadyVisited)
             {
                 return Left.FindFunction(functionName, alreadyVisited) ?? Right.FindFunction(functionName, alreadyVisited);
                 // detect “or” (¬a @ ¬b = a | b)
                 var leftNand = Left as NandNode;
                 var rightNand = Right as NandNode;
-                if (leftNand != null && leftNand.Left == leftNand.Right && rightNand != null && rightNand.Left == rightNand.Right && !letNodes.Contains(Left) && !letNodes.Contains(Right))
+                if (leftNand != null && leftNand.Left == leftNand.Right && rightNand != null && rightNand.Left == rightNand.Right && (letNodes == null || !letNodes.Contains(Left)) && (letNodes == null || !letNodes.Contains(Right)))
                     return open + leftNand.Left.GetExpression(letNodes, false, true) + " | " + rightNand.Left.GetExpression(letNodes, false, true) + close;
 
                 // detect “and” (¬(a @ b) = a & b)
-                if (Left == Right && leftNand != null && !letNodes.Contains(Left))
+                if (Left == Right && leftNand != null && (letNodes == null || !letNodes.Contains(Left)))
                     return open + leftNand.Left.GetExpression(letNodes, false, true) + " & " + leftNand.Right.GetExpression(letNodes, false, true) + close;
 
                 // detect “not” (a @ a = ¬a)
             private BigInteger _leftEval;
             protected override Node nextToEvaluate()
             {
-                Node ret;
                 switch (_state)
                 {
                     case 0:
                         _state = 1;
-                        ret = Left;
-                        Left = null;
-                        return ret;
+                        return Left;
                     case 1:
                         _leftEval = _previousSubresult;
                         _state = 2;
-                        ret = Right;
-                        Right = null;
-                        return ret;
+                        return Right;
                     case 2:
                         _result = _leftEval < _previousSubresult ? BigInteger.MinusOne : BigInteger.Zero;
                         _state = 3;
                         return null;
                 }
             }
+            protected override void releaseMemory()
+            {
+                if (_state == 1)
+                    Left = null;
+                else if (_state == 2)
+                    Right = null;
+            }
             protected override string _operator { get { return " < "; } }
         }
 
             private BigInteger _leftEval;
             protected override Node nextToEvaluate()
             {
-                Node ret;
                 switch (_state)
                 {
                     case 0:
                         _state = 1;
-                        ret = Left;
-                        Left = null;
-                        return ret;
+                        return Left;
                     case 1:
                         _leftEval = _previousSubresult;
                         _state = 2;
-                        ret = Right;
-                        Right = null;
-                        return ret;
+                        return Right;
                     case 2:
                         _result = _previousSubresult.IsZero ? _leftEval : _previousSubresult > 0 ? _leftEval << (int) _previousSubresult : _leftEval >> (int) -_previousSubresult;
                         _state = 3;
                         return null;
                 }
             }
+            protected override void releaseMemory()
+            {
+                if (_state == 1)
+                    Left = null;
+                else if (_state == 2)
+                    Right = null;
+            }
             protected override string _operator { get { return " SHL "; } }
         }
 
                 {
                     case 0:
                         _state = 1;
-                        var ret = _functionInputs[InputPosition];
-                        _functionInputs = null;
-                        return ret;
+                        return _functionInputs[InputPosition];
                     case 1:
                         _result = _previousSubresult;
                         _state = 2;
                         return null;
                 }
             }
+            protected override void releaseMemory()
+            {
+                if (_state == 1)
+                    _functionInputs = null;
+            }
             protected override FuncitonFunction findFunction(string functionName, HashSet<Node> alreadyVisited) { return null; }
             protected override void analysisPass1(HashSet<Node> singleUseNodes, HashSet<Node> multiUseNodes) { }
             protected override string getExpression(Node[] letNodes, bool requireParentheses) { return "↑→↓←".Substring(InputPosition, 1); }
             public LiteralNode(FuncitonFunction thisFunction, BigInteger literal) : base(thisFunction) { _result = literal; }
             public override Node Clone(int clonedId, Node[] functionInputs) { return this; }
             protected override Node nextToEvaluate() { return null; }
+            protected override void releaseMemory() { }
             protected override FuncitonFunction findFunction(string functionName, HashSet<Node> alreadyVisited) { return null; }
             protected override void analysisPass1(HashSet<Node> singleUseNodes, HashSet<Node> multiUseNodes) { }
             protected override string getExpression(Node[] letNodes, bool requireParentheses) { return _result.ToString().Replace('-', '−'); }
                 }
                 return null;
             }
+            protected override void releaseMemory() { }
             protected override FuncitonFunction findFunction(string functionName, HashSet<Node> alreadyVisited) { return null; }
             protected override void analysisPass1(HashSet<Node> singleUseNodes, HashSet<Node> multiUseNodes) { }
             protected override string getExpression(Node[] letNodes, bool requireParentheses) { return "♦"; }

FuncitonInterpreterProgram.cs

 using System;
+using System.Linq;
 using System.Collections.Generic;
 using System.IO;
 using System.Numerics;

FuncitonLanguage.cs

                 // Turn into array of characters
                 var lines = (sourceText.Replace("\r", "") + "\n\n").Split('\n');
                 if (lines.Length == 0)
-                    throw new ParseErrorException(new ParseError("Source file does not contain a program.", null, null, sourceFile));
+                    continue;
 
                 var longestLine = lines.Max(l => l.Length);
                 if (longestLine == 0)
-                    throw new ParseErrorException(new ParseError("Source file does not contain a program.", null, null, sourceFile));
+                    continue;
 
                 var source = new sourceAsChars { Chars = lines.Select(l => l.PadRight(longestLine).ToCharArray()).ToArray(), SourceFile = sourceFile };
 
                     }
                 }
 
-                // Add all the basic nodes except loose ends (and also complain about any stray characters)
+                // Add T-junctions and cross-junctions (but not loose ends yet), and also complain about any stray characters
                 for (int y = 0; y < source.Height; y++)
                 {
                     for (int x = 0; x < source.Width; x++)
             public edge[] Edges { get; private set; }
             public connectorType[] Connectors { get; private set; }
 
-            private T[][] rotations<T>(T[] input)
-            {
-                return Enumerable.Range(0, 4).Select(i => input.Skip(i).Concat(input.Take(i)).ToArray()).ToArray();
-            }
-
             private bool deduceGiven(edge[] edges, bool[] known, Action<edge> isCorrect, Action<edge> isFlipped, Action throwIfInvalid, params connectorType[][] connectors)
             {
                 bool[] validKnowns = null;
                 edge[] validEdges = null;
                 connectorType[] validConn = null;
+                int validRotation = 0;
 
                 foreach (var conn in connectors)
                 {
                             validEdges = rotatedEdges;
                             validKnowns = rotatedKnowns;
                             validConn = conn;
+                            validRotation = rot;
                         }
                     }
                 }
 
                 for (int i = 0; i < 4; i++)
                     if (validConn[i] != connectorType.None)
-                        ((validEdges[i].EndNode == this) ^ (validConn[i] == connectorType.Input) ? isFlipped : isCorrect)(validEdges[i]);
+                        if (validEdges[i].StartNode == this && (int) validEdges[i].DirectionFromStartNode == (i + validRotation) % 4)
+                            (validConn[i] == connectorType.Output ? isCorrect : isFlipped)(validEdges[i]);
+                        else if (validEdges[i].EndNode == this && (int) validEdges[i].DirectionFromEndNode == (i + validRotation) % 4)
+                            (validConn[i] == connectorType.Input ? isCorrect : isFlipped)(validEdges[i]);
                 Edges = validEdges;
                 Connectors = validConn;
                 return true;
                             Helpers.Assert(node.Connectors[0] == connectorType.Input);
                             Helpers.Assert(node.Connectors[1] == connectorType.Output);
                             Helpers.Assert(node.Connectors[3] == connectorType.Output);
+                            if (node.Edges[0] == edge)
+                                throw new ParseErrorException(new ParseError("This splitter is connected to itself. Such a construct is not allowed as it would always cause an infinite loop.", node.X, node.Y, _source.SourceFile));
                             var walked = walk(function, node.Edges[0], edgesAlready, callNodesAlready, unparsedFunctionsByName, unparsedFunctionsByNode, parsedFunctions);
                             edgesAlready[edge] = walked;
                             return walked;