Merge pull request #9944 from vespa-engine/bratseth/output-immediate-graph

Bratseth/output immediate graph

4 files changed, 415 insertions, 4 deletions

diff --git a/vespajlib/abi-spec.json b/vespajlib/abi-spec.json
index a16127931e9..6f37b9edea4 100644
--- a/vespajlib/abi-spec.json
+++ b/vespajlib/abi-spec.json
@@ -2576,6 +2576,20 @@
     ],
     "fields": []
   },
+  "com.yahoo.text.ExpressionFormatter": {
+    "superClass": "java.lang.Object",
+    "interfaces": [],
+    "attributes": [
+      "public"
+    ],
+    "methods": [
+      "public java.lang.String format(java.lang.String)",
+      "public static java.lang.String on(java.lang.String)",
+      "public static com.yahoo.text.ExpressionFormatter withLineLength(int)",
+      "public static com.yahoo.text.ExpressionFormatter inTwoColumnMode(int, int)"
+    ],
+    "fields": []
+  },
   "com.yahoo.text.ForwardWriter": {
     "superClass": "com.yahoo.text.GenericWriter",
     "interfaces": [],
diff --git a/vespajlib/src/main/java/com/yahoo/collections/ListMap.java b/vespajlib/src/main/java/com/yahoo/collections/ListMap.java
index e851362a99d..479850beb1a 100644
--- a/vespajlib/src/main/java/com/yahoo/collections/ListMap.java
+++ b/vespajlib/src/main/java/com/yahoo/collections/ListMap.java
@@ -23,6 +23,12 @@ public class ListMap<K, V> {
         this(HashMap.class);
     }
 
+    /** Copy constructor. This will not be frozen even if the argument map is */
+    public ListMap(ListMap<K, V> original) {
+        map = new HashMap<>();
+        original.map.forEach((k, v) -> this.map.put(k, new ArrayList<>(v)));
+    }
+
     @SuppressWarnings("unchecked")
     public ListMap(@SuppressWarnings("rawtypes") Class<? extends Map> implementation) {
         try {
@@ -45,6 +51,27 @@ public class ListMap<K, V> {
         list.add(value);
     }
 
+    /** Put a key without adding a new value, such that there is an empty list of values if no values are already added */
+    public void put(K key) {
+        List<V> list = map.get(key);
+        if (list == null) {
+            list = new ArrayList<>();
+            map.put(key, list);
+        }
+    }
+
+    /** Put this map in the state where it has just the given value of the given key */
+    public void replace(K key, V value) {
+        List<V> list = map.get(key);
+        if (list == null) {
+            put(key);
+        }
+        else {
+            list.clear();
+            list.add(value);
+        }
+    }
+
     public void removeAll(K key) {
         map.remove(key);
     }
@@ -73,13 +100,13 @@ public class ListMap<K, V> {
 
     /**
      * Returns the List containing the elements with this key, or an empty list
-     * if there are no elements for this key. The list returned is unmodifiable.
+     * if there are no elements for this key.
+     * The returned list can be modified to add and remove values if the value exists.
      */
     public List<V> get(K key) {
         List<V> list = map.get(key);
-        if (list == null)
-            return ImmutableList.of();;
-        return ImmutableList.copyOf(list);
+        if (list == null) return ImmutableList.of();;
+        return list;
     }
 
     /** The same as get */
diff --git a/vespajlib/src/main/java/com/yahoo/text/ExpressionFormatter.java b/vespajlib/src/main/java/com/yahoo/text/ExpressionFormatter.java
new file mode 100644
index 00000000000..280b75f9cbb
--- /dev/null
+++ b/vespajlib/src/main/java/com/yahoo/text/ExpressionFormatter.java
@@ -0,0 +1,180 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.text;
+
+/**
+ * Formats any parenthesis expression.
+ * In addition to the obvious this can also operate in "two column mode",
+ * wherein each chunk that will be formatted on a separate line may optionally
+ * contain a prefix marked by a start and end tab sign which will be printed in a left column of the given fixed size.
+ * The prefix itself is not formatted but will be cut if too long.
+ *
+ * @author bratseth
+ */
+public class ExpressionFormatter {
+
+    private static final int indentUnit = 2;
+
+    /** The size of the first column, or 0 if none */
+    private final int firstColumnLength;
+
+    /**
+     * The desired size of the second column (or the entire line if no first column),
+     * or 0 to split into multiple lines as much as possible.
+     * Setting this collects larger chunks to one line across markup
+     * but will not split too long lines that have no markup.
+     */
+    private final int secondColumnLength;
+
+    private ExpressionFormatter(int firstColumnLength, int secondColumnLength) {
+        this.firstColumnLength = firstColumnLength;
+        this.secondColumnLength = secondColumnLength;
+    }
+
+    public String format(String parenthesisExpression) {
+        StringBuilder b = new StringBuilder();
+        format(parenthesisExpression, 0, b);
+        while (b.length() > 0 && Character.isWhitespace(b.charAt(b.length() - 1)))
+            b.setLength(b.length() - 1);
+        return b.toString();
+    }
+
+    private void format(String expression, int indent, StringBuilder b) {
+        if (expression.isEmpty()) return;
+        expression = appendFirstColumn(expression, b);
+
+        Markup next = Markup.next(expression);
+
+        appendIndent( ! next.isClose() || next.position() > 0 ? indent : indent - 2, b);
+
+        int endOfBalancedChunk = endOfBalancedChunk(expression, Math.max(0, secondColumnLength - indent));
+        if (next.isEmpty()) {
+            b.append(expression);
+        }
+        else if (endOfBalancedChunk > 0) {
+            b.append(expression, 0, endOfBalancedChunk + 1).append("\n");
+            format(expression.substring(endOfBalancedChunk + 1), indent, b);
+        }
+        else if (next.isComma()) {
+            b.append(expression, 0, next.position() + 1).append("\n");
+            format(expression.substring(next.position() + 1), indent, b);
+        }
+        else {
+            if ( next.isClose() && next.position() > 0) { // content before end parenthesis: content, newline, then end parenthesis
+                b.append(expression, 0, next.position()).append("\n");
+                appendFirstColumn(")", b);
+                appendIndent(indent - 2, b);
+                b.append(")\n");
+            }
+            else {
+                b.append(expression, 0, next.position() + 1).append("\n");
+            }
+            format(expression.substring(next.position() + 1), indent + (next.isOpen() ? indentUnit : -indentUnit), b);
+        }
+    }
+
+    /** Returns the position of the end of a balanced chunk of at most the given size, or 0 if there is no such chunk */
+    private int endOfBalancedChunk(String expression, int maxSize) {
+        int chunkSize = 0;
+        int i = 0;
+        int nesting = 0;
+        while (i < maxSize && i < expression.length()) {
+            if (expression.charAt(i) == '\t') return chunkSize;
+            if (expression.charAt(i) == '(') nesting++;
+            if (expression.charAt(i) == ')') nesting--;
+            if (nesting < 0) return chunkSize;
+            if (nesting == 0 && ( expression.charAt(i)==')' || expression.charAt(i)==','))
+                chunkSize = i;
+            i++;
+        }
+        return chunkSize;
+    }
+
+    private String appendFirstColumn(String expression, StringBuilder b) {
+        if (firstColumnLength == 0) return expression;
+
+        while (expression.charAt(0) == ' ')
+            expression = expression.substring(1);
+
+        if (expression.charAt(0) == '\t') {
+            int tab2 = expression.indexOf('\t', 1);
+            if (tab2 >= 0) {
+                String firstColumn = expression.substring(1, tab2);
+                b.append(asSize(firstColumnLength, firstColumn)).append(" ");
+                return expression.substring(tab2 + 1);
+            }
+        }
+        appendIndent(firstColumnLength + 1, b);
+        return expression;
+    }
+
+    private void appendIndent(int indent, StringBuilder b) {
+        b.append(" ".repeat(Math.max(0, indent)));
+    }
+
+    private String asSize(int size, String s) {
+        if (s.length() > size)
+            return s.substring(0, size);
+        else
+            return s + " ".repeat(size - s.length());
+    }
+
+    /** Convenience method creating a formatter and using it to format the given expression */
+    public static String on(String parenthesisExpression) {
+        return new ExpressionFormatter(0, 80).format(parenthesisExpression);
+    }
+
+    public static ExpressionFormatter withLineLength(int maxLineLength) {
+        return new ExpressionFormatter(0, maxLineLength);
+    }
+
+    public static ExpressionFormatter inTwoColumnMode(int firstColumnSize, int secondColumnSize) {
+        return new ExpressionFormatter(firstColumnSize, secondColumnSize);
+    }
+
+    /** Contains the next position of each kind of markup, or Integer.MAX_VALUE if not present */
+    private static class Markup {
+
+        final int open, close, comma;
+
+        private Markup(int open, int close, int comma) {
+            this.open = open;
+            this.close = close;
+            this.comma = comma;
+        }
+
+        int position() {
+            return Math.min(Math.min(open, close), comma);
+        }
+
+        boolean isOpen() {
+            return open < close && open < comma;
+        }
+
+        boolean isClose() {
+            return close < open && close < comma;
+        }
+
+        boolean isComma() {
+            return comma < open && comma < close;
+        }
+
+        boolean isEmpty() {
+            return open == Integer.MAX_VALUE && close == Integer.MAX_VALUE && comma == Integer.MAX_VALUE;
+        }
+
+        static Markup next(String expression) {
+            int nextOpen = expression.indexOf('(');
+            int nextClose = expression.indexOf(')');
+            int nextComma = expression.indexOf(',');
+            if (nextOpen < 0)
+                nextOpen = Integer.MAX_VALUE;
+            if (nextClose < 0)
+                nextClose = Integer.MAX_VALUE;
+            if (nextComma < 0)
+                nextComma = Integer.MAX_VALUE;
+            return new Markup(nextOpen, nextClose, nextComma);
+        }
+
+    }
+
+}
diff --git a/vespajlib/src/test/java/com/yahoo/text/ExpressionFormatterTest.java b/vespajlib/src/test/java/com/yahoo/text/ExpressionFormatterTest.java
new file mode 100644
index 00000000000..7251ccef521
--- /dev/null
+++ b/vespajlib/src/test/java/com/yahoo/text/ExpressionFormatterTest.java
@@ -0,0 +1,190 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.text;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author bratseth
+ */
+public class ExpressionFormatterTest {
+
+    @Test
+    public void testBasic() {
+        String expected =
+                "foo(\n" +
+                "  bar(\n" +
+                "    baz(\n" +
+                "    )\n" +
+                "  )\n" +
+                ")";
+        assertPrettyPrint(expected, "foo(bar(baz()))", 0);
+    }
+
+    @Test
+    public void testBasicDense() {
+        assertPrettyPrint("foo(bar(baz()))", "foo(bar(baz()))", 50);
+    }
+
+    @Test
+    public void testArgument() {
+        String expected =
+                "foo(\n" +
+                "  bar(\n" +
+                "    baz(\n" +
+                "      hello world\n" +
+                "    )\n" +
+                "  )\n" +
+                ")";
+        assertPrettyPrint(expected, "foo(bar(baz(hello world)))", 0);
+    }
+
+    @Test
+    public void testMultipleArguments() {
+        String expected =
+                "foo(\n" +
+                "  bar(\n" +
+                "    baz(\n" +
+                "      hello world,\n" +
+                "      37\n" +
+                "    )\n" +
+                "  )\n" +
+                ")";
+        assertPrettyPrint(expected, "foo(bar(baz(hello world,37)))", 0);
+    }
+
+    @Test
+    public void testMultipleArgumentsSemiDense() {
+        String expected =
+                "foo(\n" +
+                "  bar(\n" +
+                "    baz(hi,37),\n" +
+                "    baz(\n" +
+                "      hello world,\n" +
+                "      37\n" +
+                "    )\n" +
+                "  )\n" +
+                ")";
+        assertPrettyPrint(expected, "foo(bar(baz(hi,37),baz(hello world,37)))", 15);
+    }
+
+    @Test
+    public void testUnmatchedStart() {
+        String expected =
+                "foo(\n" +
+                "  (\n" +
+                "    bar(\n" +
+                "      baz(\n" +
+                "      )\n" +
+                "    )\n" +
+                "  )";
+        assertPrettyPrint(expected, "foo((bar(baz()))", 0);
+    }
+
+    @Test
+    public void testUnmatchedEnd() {
+        String expected =
+                "foo(\n" +
+                "  bar(\n" +
+                "    baz(\n" +
+                "    )\n" +
+                "  )\n" +
+                ")\n" +
+                ")";
+        assertPrettyPrint(expected, "foo(bar(baz())))", 0);
+    }
+
+    @Test
+    public void testNoParenthesis() {
+        String expected =
+                "foo bar baz";
+        assertPrettyPrint(expected, "foo bar baz", 0);
+    }
+
+    @Test
+    public void testEmpty() {
+        String expected =
+                "";
+        assertPrettyPrint(expected, "", 0);
+    }
+
+    @Test
+    public void test2ColumnMode() {
+        String expected =
+                "1:  foo(\n" +
+                "      bar(\n" +
+                "        baz(\n" +
+                "2:        hello world\n" +
+                "        )\n" +
+                "t(o   )\n" +
+                "    )";
+        ExpressionFormatter pp = ExpressionFormatter.inTwoColumnMode(3, 0);
+        assertEquals(expected, pp.format("\t1:\tfoo(bar(baz(\t2:\thello world)\tt(o)@olong:\t))"));
+    }
+
+    @Test
+    public void test2ColumnModeMultipleArguments() {
+        String expected =
+                "1:  foo(\n" +
+                "      bar(\n" +
+                "        baz(\n" +
+                "2:        hello world,\n" +
+                "3:        37\n" +
+                "        )\n" +
+                "t(o   )\n" +
+                "    )";
+        ExpressionFormatter pp = ExpressionFormatter.inTwoColumnMode(3, 0);
+        assertEquals(expected, pp.format("\t1:\tfoo(bar(baz(\t2:\thello world,\t3:\t37)\tt(o)@olong:\t))"));
+    }
+
+    @Test
+    public void test2ColumnModeMultipleArgumentsSemiDense() {
+        String expected =
+                "1:  foo(\n" +
+                "      bar(\n" +
+                "        baz(hi,37),\n" +
+                "        boz(\n" +
+                "2:        hello world,\n" +
+                "3:        5\n" +
+                "        )\n" +
+                "t(o   )\n" +
+                "    )";
+        ExpressionFormatter pp = ExpressionFormatter.inTwoColumnMode(3, 15);
+        assertEquals(expected, pp.format("\t1:\tfoo(bar(baz(hi,37),boz(\t2:\thello world,\t3:\t5)\tt(o)@olong:\t))"));
+    }
+
+    @Test
+    public void test2ColumnModeMultipleArgumentsWithSpaces() {
+        String expected =
+                "    foo(\n" +
+                "1:    bar(\n" +
+                "        baz(\n" +
+                "2:        hello world,\n" +
+                "3:        37\n" +
+                "        )\n" +
+                "t(o   )\n" +
+                "    )";
+        ExpressionFormatter pp = ExpressionFormatter.inTwoColumnMode(3, 0);
+        assertEquals(expected, pp.format("foo(\t1:\tbar(baz(\t2:\thello world, \t3:\t37)\tt(o)@olong:\t))"));
+    }
+
+    @Test
+    public void testTwoColumnLambdaFunction() {
+        String expected =
+                "      join(\n" +
+                "        a,\n" +
+                "        join(\n" +
+                "          b, c, f(a, b)(a * b)\n" +
+                "        )\n" +
+                "        , f(a, b)(a * b)\n" +
+                "      )";
+        ExpressionFormatter pp = ExpressionFormatter.inTwoColumnMode(5, 25);
+        assertEquals(expected, pp.format("join(a, join(b, c, f(a, b)(a * b)), f(a, b)(a * b))"));
+    }
+
+    private void assertPrettyPrint(String expected, String expression, int lineLength) {
+        assertEquals(expected, ExpressionFormatter.withLineLength(lineLength).format(expression));
+    }
+
+}