You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2021/05/28 03:20:21 UTC

[GitHub] [lucene] glawson0 opened a new pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

glawson0 opened a new pull request #157:
URL: https://github.com/apache/lucene/pull/157


   <!--
   _(If you are a project committer then you may remove some/all of the following template.)_
   
   Before creating a pull request, please file an issue in the ASF Jira system for Lucene:
   
   * https://issues.apache.org/jira/projects/LUCENE
   
   You will need to create an account in Jira in order to create an issue.
   
   The title of the PR should reference the Jira issue number in the form:
   
   * LUCENE-####: <short description of problem or changes>
   
   LUCENE must be fully capitalized. A short description helps people scanning pull requests for items they can work on.
   
   Properly referencing the issue in the title ensures that Jira is correctly updated with code review comments and commits. -->
   
   
   # Description
   
   There are various situations were the flatten graph filter may throw an exception or drop tokens due to mishandling of holes in the analysis graph. The primary causes were
   1) Output nodes that were hole destinations and valid sources
   2) Freeing nodes before they had been fully resolved
   3) Putting edges at incorrect output nodes after a hole
   # Solution
   
   1)Iterate through all output.InputNodes since dest gaps can exist
   2)Freebefore the minimum input node not the first input node(which is usually, but not always, the minimum)
   3)Recovery nodes that have end offset less than their preceeding node gaplessly follow their preceeding node
   4)Ensure nodes  positionInc >1 are arriving at the end of the graph.
   
   # Tests
   
   same tests as https://github.com/apache/lucene/pull/146
   plus tests for shingled tokens and gaps at the start of a token graph.
   
   # Checklist
   
   Please review the following and check all that apply:
   
   - [x] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/lucene/HowToContribute) and my code conforms to the standards described there to the best of my ability.
   - [x] I have created a Jira issue and added the issue ID to my pull request title.
   - [x] I have given Lucene maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
   - [x] I have developed this patch against the `main` branch.
   - [x] I have run `./gradlew check`.
   - [x] I have added tests for my changes.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-888287420


   > We have been using this change internally for a few weeks now. We no longer encounter the ArrayIndexOutOfBounds exceptions that we were previously experiencing. Depending on the dataset/analyzer combination we have seen up to a 1% increase in the average number of tokens per field. This comes from the tokens that had previously been dropped now being correctly indexed.
   
   Thanks for the update @glawson0!  This is great news.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r655951001



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -284,27 +316,27 @@ public boolean incrementToken() throws IOException {
 
         InputNode src = inputNodes.get(inputFrom);
         if (src.node == -1) {
-          // This means the "from" node of this token was never seen as a "to" node,
-          // which should only happen if we just crossed a hole.  This is a challenging
-          // case for us because we normally rely on the full dependencies expressed
-          // by the arcs to assign outgoing node IDs.  It would be better if tokens
-          // were never dropped but instead just marked deleted with a new
-          // TermDeletedAttribute (boolean valued) ... but until that future, we have

Review comment:
       Working on this change has made me realize how valuable not removing tokens would be.




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-865954873


   For additional testing I've built a few indexes and played some queries against them. I didn't find any changes to latency or memory usage. Depending on the data set used there was impact on results. The English data sets didn't show any impact. Using it with our Japanese analyzer had a larger impact. In one index 10% of queries were impacted by the change with those queries matching more documents. Previously those documents had lost tokens from `FlattenGraphFilter`. The primary cause of these dropped tokens was graphs with gaps in them. The `JapaneseTokenizer` would create graphs that `FilteringTokenFilter`s would remove tokens from and then `FlattenGraphFilter` would incorrectly flatten them.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r678412320



##########
File path: lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
##########
@@ -0,0 +1,197 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.analysis;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.Operations;
+import org.apache.lucene.util.automaton.Transition;
+
+/** Converts an Automaton into a TokenStream. */
+public class AutomatonToTokenStream {

Review comment:
       Whoa, awesome!  This will be a really helpful infrastructure for future testing!  And of course now I really feel compelled to take a Lev1("lucene") and run it through here and watch what the resulting tokens are!

##########
File path: lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
##########
@@ -0,0 +1,197 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.analysis;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.Operations;
+import org.apache.lucene.util.automaton.Transition;
+
+/** Converts an Automaton into a TokenStream. */
+public class AutomatonToTokenStream {
+
+  private AutomatonToTokenStream() {}
+
+  /**
+   * converts an automaton into a TokenStream. This is done by first Topo sorting the nodes in the
+   * Automaton. Nodes that have the same distance from the start are grouped together to form the
+   * position nodes for the TokenStream. The resulting TokenStream releases edges from the automaton
+   * as tokens in order from the position nodes. This requires the automaton be a finite DAG.
+   *
+   * @param automaton automaton to convert. Must be a finite DAG.
+   * @return TokenStream representation of automaton.
+   */
+  public static TokenStream toTokenStream(Automaton automaton) {
+    if (Operations.isFinite(automaton) == false) {
+      throw new IllegalArgumentException("Automaton must be finite");
+    }
+
+    List<List<Integer>> positionNodes = new ArrayList<>();
+
+    Transition[][] transitions = automaton.getSortedTransitions();
+
+    int[] indegree = new int[transitions.length];
+
+    for (int i = 0; i < transitions.length; i++) {
+      for (int edge = 0; edge < transitions[i].length; edge++) {
+        indegree[transitions[i][edge].dest] += 1;
+      }
+    }
+    if (indegree[0] != 0) {
+      throw new IllegalArgumentException("Start node has incoming edges, creating cycle");
+    }
+
+    LinkedList<RemapNode> noIncomingEdges = new LinkedList<>();
+    Map<Integer, Integer> idToPos = new HashMap<>();
+    noIncomingEdges.addLast(new RemapNode(0, 0));
+    while (noIncomingEdges.isEmpty() == false) {

Review comment:
       Whoa, is this toposort?  What algorithm :)  Maybe add a comment that that is what this code is doing, with which algo?
   

##########
File path: lucene/core/src/test/org/apache/lucene/analysis/TestAutomatonToTokenStream.java
##########
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.analysis;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.DaciukMihovAutomatonBuilder;
+
+public class TestAutomatonToTokenStream extends BaseTokenStreamTestCase {
+
+  public void testSinglePath() throws IOException {
+    List<BytesRef> acceptStrings = new ArrayList<>();
+    acceptStrings.add(new BytesRef("abc"));
+
+    Automaton flatPathAutomaton = DaciukMihovAutomatonBuilder.build(acceptStrings);
+    TokenStream ts = AutomatonToTokenStream.toTokenStream(flatPathAutomaton);
+    assertTokenStreamContents(
+        ts,
+        new String[] {"a", "b", "c"},
+        new int[] {0, 1, 2},
+        new int[] {1, 2, 3},
+        new int[] {1, 1, 1},
+        new int[] {1, 1, 1},
+        3);
+  }
+
+  public void testParallelPaths() throws IOException {
+    List<BytesRef> acceptStrings = new ArrayList<>();
+    acceptStrings.add(new BytesRef("123"));
+    acceptStrings.add(new BytesRef("abc"));
+
+    Automaton flatPathAutomaton = DaciukMihovAutomatonBuilder.build(acceptStrings);
+    TokenStream ts = AutomatonToTokenStream.toTokenStream(flatPathAutomaton);
+    assertTokenStreamContents(

Review comment:
       So cool!!

##########
File path: lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
##########
@@ -0,0 +1,197 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.analysis;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.Operations;
+import org.apache.lucene.util.automaton.Transition;
+
+/** Converts an Automaton into a TokenStream. */
+public class AutomatonToTokenStream {
+
+  private AutomatonToTokenStream() {}
+
+  /**
+   * converts an automaton into a TokenStream. This is done by first Topo sorting the nodes in the
+   * Automaton. Nodes that have the same distance from the start are grouped together to form the
+   * position nodes for the TokenStream. The resulting TokenStream releases edges from the automaton
+   * as tokens in order from the position nodes. This requires the automaton be a finite DAG.
+   *
+   * @param automaton automaton to convert. Must be a finite DAG.
+   * @return TokenStream representation of automaton.
+   */
+  public static TokenStream toTokenStream(Automaton automaton) {
+    if (Operations.isFinite(automaton) == false) {
+      throw new IllegalArgumentException("Automaton must be finite");
+    }
+
+    List<List<Integer>> positionNodes = new ArrayList<>();
+
+    Transition[][] transitions = automaton.getSortedTransitions();
+
+    int[] indegree = new int[transitions.length];
+
+    for (int i = 0; i < transitions.length; i++) {
+      for (int edge = 0; edge < transitions[i].length; edge++) {
+        indegree[transitions[i][edge].dest] += 1;
+      }
+    }
+    if (indegree[0] != 0) {
+      throw new IllegalArgumentException("Start node has incoming edges, creating cycle");
+    }
+
+    LinkedList<RemapNode> noIncomingEdges = new LinkedList<>();
+    Map<Integer, Integer> idToPos = new HashMap<>();
+    noIncomingEdges.addLast(new RemapNode(0, 0));
+    while (noIncomingEdges.isEmpty() == false) {
+      RemapNode currState = noIncomingEdges.removeFirst();
+      for (int i = 0; i < transitions[currState.id].length; i++) {
+        indegree[transitions[currState.id][i].dest] -= 1;
+        if (indegree[transitions[currState.id][i].dest] == 0) {
+          noIncomingEdges.addLast(
+              new RemapNode(transitions[currState.id][i].dest, currState.pos + 1));
+        }
+      }
+      if (positionNodes.size() == currState.pos) {
+        List<Integer> posIncs = new ArrayList<>();
+        posIncs.add(currState.id);
+        positionNodes.add(posIncs);
+      } else {
+        positionNodes.get(currState.pos).add(currState.id);
+      }
+      idToPos.put(currState.id, currState.pos);
+    }
+
+    for (int i = 0; i < indegree.length; i++) {
+      if (indegree[i] != 0) {
+        throw new IllegalArgumentException("Cycle found in automaton");
+      }
+    }
+
+    List<List<EdgeToken>> edgesByLayer = new ArrayList<>();
+    for (List<Integer> layer : positionNodes) {
+      List<EdgeToken> edges = new ArrayList<>();
+      for (int state : layer) {
+        for (Transition t : transitions[state]) {
+          // each edge in the token stream can only be on value, though a transition takes a range.
+          for (int val = t.min; val <= t.max; val++) {
+            int destLayer = idToPos.get(t.dest);
+            edges.add(new EdgeToken(destLayer, val));
+            // If there's an intermediate accept state, add an edge to the terminal state.
+            if (automaton.isAccept(t.dest) && destLayer != positionNodes.size() - 1) {
+              edges.add(new EdgeToken(positionNodes.size() - 1, val));

Review comment:
       Ahh, the token graph has only one "accept" state, the highest end position, so we have to move these accept transitions "out" to that end pos.  Sneaky!

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +415,55 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset, int posinc) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int outIndex;
+    int previousInputFrom = inputFrom - posinc;
+    if (previousInputFrom >= 0) {
+      InputNode offsetSrc = inputNodes.get(previousInputFrom);
+      /* Select output src node. Need to make sure the new output node isn't placed too far ahead.
+       * If a disconnected node is placed at the end of the output graph that may place it after output nodes that map to input nodes that are after src in the input.
+       * Since it is disconnected there is no path to it, and there could be holes after meaning no paths to following nodes. This "floating" edge will cause problems in FreeBefore.
+       * In the following section make sure the edge connects to something.
+       * Related test testLongHole testAltPathLastStepHoleFollowedByHole, testAltPathFirstStepHole, testShingledGapWithHoles
+       */
+      if (offsetSrc.minToNode < inputFrom) {
+        // There is a possible path to this node.
+        // place this node one position off from the possible path keeping a 1 inc gap.
+        // Can't be larger than 1 inc or risk getting disconnected.
+        outIndex = inputNodes.get(offsetSrc.minToNode).outputNode + 1;
+      } else {
+        // no information about how the current node was previously connected.
+        // Connect it to the end.

Review comment:
       This connects the orphan'd token to the "end" as far as we've consumed/produced so far (`outputNodes.getMaxPos()`) right?  This seems OK (not sure how else we could recover) but I wonder in practice what incoming hole configuration tickles this?

##########
File path: lucene/core/src/java/org/apache/lucene/analysis/AutomatonToTokenStream.java
##########
@@ -0,0 +1,197 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.analysis;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
+import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.Operations;
+import org.apache.lucene.util.automaton.Transition;
+
+/** Converts an Automaton into a TokenStream. */
+public class AutomatonToTokenStream {
+
+  private AutomatonToTokenStream() {}
+
+  /**
+   * converts an automaton into a TokenStream. This is done by first Topo sorting the nodes in the
+   * Automaton. Nodes that have the same distance from the start are grouped together to form the
+   * position nodes for the TokenStream. The resulting TokenStream releases edges from the automaton
+   * as tokens in order from the position nodes. This requires the automaton be a finite DAG.
+   *
+   * @param automaton automaton to convert. Must be a finite DAG.
+   * @return TokenStream representation of automaton.
+   */
+  public static TokenStream toTokenStream(Automaton automaton) {
+    if (Operations.isFinite(automaton) == false) {
+      throw new IllegalArgumentException("Automaton must be finite");
+    }
+
+    List<List<Integer>> positionNodes = new ArrayList<>();
+
+    Transition[][] transitions = automaton.getSortedTransitions();
+
+    int[] indegree = new int[transitions.length];
+
+    for (int i = 0; i < transitions.length; i++) {
+      for (int edge = 0; edge < transitions[i].length; edge++) {
+        indegree[transitions[i][edge].dest] += 1;
+      }
+    }
+    if (indegree[0] != 0) {
+      throw new IllegalArgumentException("Start node has incoming edges, creating cycle");
+    }
+
+    LinkedList<RemapNode> noIncomingEdges = new LinkedList<>();
+    Map<Integer, Integer> idToPos = new HashMap<>();
+    noIncomingEdges.addLast(new RemapNode(0, 0));
+    while (noIncomingEdges.isEmpty() == false) {
+      RemapNode currState = noIncomingEdges.removeFirst();
+      for (int i = 0; i < transitions[currState.id].length; i++) {
+        indegree[transitions[currState.id][i].dest] -= 1;
+        if (indegree[transitions[currState.id][i].dest] == 0) {
+          noIncomingEdges.addLast(
+              new RemapNode(transitions[currState.id][i].dest, currState.pos + 1));
+        }
+      }
+      if (positionNodes.size() == currState.pos) {
+        List<Integer> posIncs = new ArrayList<>();
+        posIncs.add(currState.id);
+        positionNodes.add(posIncs);
+      } else {
+        positionNodes.get(currState.pos).add(currState.id);
+      }
+      idToPos.put(currState.id, currState.pos);

Review comment:
       It looks like we "eagerly" place all nodes onto the same position if the topo-sort allows it (i.e. those nodes are at the same "layer" after topo-sort)?  But doesn't that then over-generalize, causing the resulting token graph to accept more strings than the automaton originally did?

##########
File path: lucene/analysis/common/src/test/org/apache/lucene/analysis/core/TestFlattenGraphFilter.java
##########
@@ -544,8 +732,288 @@ protected TokenStreamComponents createComponents(String fieldName) {
     }
 
     String text = String.join(" ", stringTokens);
-    checkAnalysisConsistency(random, a, false, text);
+    // FlattenGraphFilter can create inconsistent offsets.
+    // If that is resolved we can check offsets
+    // Until then converting to automaton will pull text through and check if we hit asserts.
+    // checkAnalysisConsistency(random, withFlattenGraph, false, text);
+    TokenStreamToAutomaton tsta = new TokenStreamToAutomaton();
+    TokenStream flattenedTokenStream = withFlattenGraph.tokenStream("field", text);
+    assertFalse(Operations.hasDeadStates(tsta.toAutomaton(flattenedTokenStream)));
+    flattenedTokenStream.close();
+
+    /*
+       CheckGeneralization can get VERY slow as matching holes to tokens or other holes generates a lot of potentially valid paths.
+       Analyzer withoutFlattenGraph =
+           new Analyzer() {
+             @Override
+             protected TokenStreamComponents createComponents(String fieldName) {
+               Tokenizer in = new WhitespaceTokenizer();
+               TokenStream result = new SynonymGraphFilter(in, synMap, true);
+               result = new StopFilter(result, stopWords);
+               return new TokenStreamComponents(in, result);
+             }
+           };
+       checkGeneralization(
+           withFlattenGraph.tokenStream("field", text),
+           withoutFlattenGraph.tokenStream("field", text));
+
+    */
   }
 
+  /*
+   * Make some strings, make an automaton that accepts those strings, convert that automaton into a TokenStream,
+   * flatten it, back to an automaton, and see if the original strings are still accepted.
+   */
+  public void testPathsNotLost() throws IOException {
+    int wordCount = random().nextInt(5) + 5;
+    List<BytesRef> acceptStrings = new LinkedList<>();
+    for (int i = 0; i < wordCount; i++) {
+      int wordLen = random().nextInt(5) + 5;
+      BytesRef ref = new BytesRef(wordLen);
+      ref.length = wordLen;
+      ref.offset = 0;
+      for (int j = 0; j < wordLen; j++) {
+        ref.bytes[j] = (byte) (random().nextInt(5) + 65);
+      }
+      acceptStrings.add(ref);
+    }
+    acceptStrings.sort(Comparator.naturalOrder());
+
+    acceptStrings = acceptStrings.stream().limit(wordCount).collect(Collectors.toList());
+    Automaton nonFlattenedAutomaton = DaciukMihovAutomatonBuilder.build(acceptStrings);
+
+    TokenStream ts = AutomatonToTokenStream.toTokenStream(nonFlattenedAutomaton);
+    TokenStream flattenedTokenStream = new FlattenGraphFilter(ts);
+    TokenStreamToAutomaton tsta = new TokenStreamToAutomaton();
+    Automaton flattenedAutomaton = tsta.toAutomaton(flattenedTokenStream);
+
+    // TokenStreamToAutomaton adds position increment transitions into the automaton.
+    List<BytesRef> acceptStringsWithPosSep = createAcceptStringsWithPosSep(acceptStrings);
+
+    for (BytesRef acceptString : acceptStringsWithPosSep) {
+      assertTrue(
+          "string not accepted " + acceptString.utf8ToString(),
+          recursivelyValidate(acceptString, 0, 0, flattenedAutomaton));
+    }
+  }
+
+  /**
+   * adds POS_SEP bytes between bytes to match TokenStreamToAutomaton format.
+   *
+   * @param acceptStrings Byte refs of accepted strings. Each byte is a transition
+   * @return List of ByteRefs where each byte is separated by a POS_SEP byte.
+   */
+  private List<BytesRef> createAcceptStringsWithPosSep(List<BytesRef> acceptStrings) {
+    List<BytesRef> acceptStringsWithPosSep = new ArrayList<>();
+    for (BytesRef acceptString : acceptStrings) {
+      BytesRef withPosSep = new BytesRef(acceptString.length * 2 - 1);
+      withPosSep.length = acceptString.length * 2 - 1;
+      withPosSep.offset = 0;
+      for (int i = 0; i < acceptString.length; i++) {
+        withPosSep.bytes[i * 2] = acceptString.bytes[i];
+        if (i * 2 + 1 < withPosSep.length) {
+          withPosSep.bytes[i * 2 + 1] = TokenStreamToAutomaton.POS_SEP;
+        }
+      }
+      acceptStringsWithPosSep.add(withPosSep);
+    }
+    return acceptStringsWithPosSep;
+  }
+
+  /**
+   * Checks if acceptString is accepted by the automaton. Automaton may be an NFA.
+   *
+   * @param acceptString String to test
+   * @param acceptStringIndex current index into acceptString, initial value should be 0
+   * @param state state to transition from. initial value should be 0
+   * @param automaton Automaton to test
+   * @return true if acceptString is accepted by the automaton. otherwise false.
+   */
+  public boolean recursivelyValidate(
+      BytesRef acceptString, int acceptStringIndex, int state, Automaton automaton) {
+    if (acceptStringIndex == acceptString.length) {
+      return automaton.isAccept(state);
+    }
+
+    Transition transition = new Transition();
+    automaton.initTransition(state, transition);
+    int numTransitions = automaton.getNumTransitions(state);
+    boolean accept = false;
+    // Automaton can be NFA, so we need to check all matching transitions
+    for (int i = 0; i < numTransitions; i++) {
+      automaton.getTransition(state, i, transition);
+      if (transition.min <= acceptString.bytes[acceptStringIndex]
+          && transition.max >= acceptString.bytes[acceptStringIndex]) {
+        accept =
+            recursivelyValidate(acceptString, acceptStringIndex + 1, transition.dest, automaton);
+      }
+      if (accept == true) {
+        break;
+      }
+    }
+    return accept;
+  }
+
+  /**
+   * This method checks if strings that lead to the accept state of the not flattened TokenStream
+   * also lead to the accept state in the flattened TokenStream. This gets complicated when you
+   * factor in holes. The FlattenGraphFilter will remove alternate paths that are made entirely of
+   * holes. An alternate path of Holes is indistinguishable from a path that just has long
+   * lengths(ex: testStrangelyNumberedNodes). Also alternate paths that end in multiple holes could
+   * be interpreted as sequential holes after the branching has converged during flattening. This
+   * leads to a lot of weird logic about navigating around holes that may compromise the accuracy of
+   * this test.
+   *
+   * @param flattened flattened TokenStream
+   * @param notFlattened not flattened TokenStream
+   * @throws IOException on error creating Automata
+   */
+  /* private void checkGeneralization(TokenStream flattened, TokenStream notFlattened)

Review comment:
       Hmm why did you need to comment out all these methods?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r643674911



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -193,14 +194,25 @@ private boolean releaseBufferedToken() {
         }
         if (inputNode.tokens.size() == 0) {
           assert inputNode.nextOut == 0;
-          assert output.nextOut == 0;
           // Hole dest nodes should never be merged since 1) we always
           // assign them to a new output position, and 2) since they never
           // have arriving tokens they cannot be pushed:
-          assert output.inputNodes.size() == 1 : output.inputNodes.size();
+          // skip hole sources, but don't free until every input is checked
+          if (output.inputNodes.size() > 1) {
+            output.inputNodes.remove(output.nextOut);
+            if (output.nextOut < output.inputNodes.size()) {
+              continue;
+            }
+          }
+
           outputFrom++;
-          inputNodes.freeBefore(output.inputNodes.get(0));
+          int freeBefore = Collections.min(output.inputNodes);
+          assert outputNodes.get(outputFrom).inputNodes.stream().filter(n -> freeBefore < n).count()

Review comment:
       You're correct. The test as written here just checks if at least one node is ok instead of all nodes, then prints the wrong message.




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-865943363


   Changed 3 parts of flatten graph filter
   1) don't call freeBefore when we finish a hole src node. Hole src nodes can mean something hasn't been accounted for correctly so calling freeBefore may free nodes that still have info we need.
   2) Change how RecoverFromHole picks the outSrc node. Instead of always always adding to the end of the OutputNodes list it scales down its position increment to match the output graph and uses that to pick the OutputNode. This doesn't require the distinction between neighbor and consumed holes.
   3) Change the condition for fixing gaps after an alternate path hole. Now it checks if the shortest edge from the position the current edge is incrementing from comes to the current start node. if it doesn't then we've crossed a gap.
   
   
   Added a few more tests `testHeavilyConnectedGraphWithGap` and `testShingleFromGap` I believe cover the cases @mikemccand mentioned earlier. I also added the `Automaton` -> `TokenStream` -> Flattened`TokenStream` -> Automaton no paths lost test as well as a validation test on the existing random graph test. The validation gets weird with handling holes, but I think that's necessary as a hole in an accept sequence could be anything and hole sizes can change after flattening.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r645647506



##########
File path: lucene/analysis/common/src/test/org/apache/lucene/analysis/core/TestFlattenGraphFilter.java
##########
@@ -314,5 +323,304 @@ public void testTwoLongParallelPaths() throws Exception {
         11);
   }
 
+  // The end node the long path is supposed to flatten over doesn't exist
+  // assert disabled = pos length of abc = 4
+  // assert enabled = AssertionError: outputEndNode=3 vs inputTo=2

Review comment:
       Was this describing the bug before, that is now fixed?  Maybe clarify?

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -193,14 +194,20 @@ private boolean releaseBufferedToken() {
         }
         if (inputNode.tokens.size() == 0) {
           assert inputNode.nextOut == 0;
-          assert output.nextOut == 0;
           // Hole dest nodes should never be merged since 1) we always
           // assign them to a new output position, and 2) since they never
-          // have arriving tokens they cannot be pushed:
-          assert output.inputNodes.size() == 1 : output.inputNodes.size();
-          outputFrom++;
-          inputNodes.freeBefore(output.inputNodes.get(0));
-          outputNodes.freeBefore(outputFrom);
+          // have arriving tokens they cannot be pushed. Skip them but don't free

Review comment:
       I sooooo wish we could stick little PNGs into comments in our java sources!!  Why must we be restricted to our Unicode characters only ;). Imagine if we could write a few dot (graphviz) commands and our IDEs/Emacs's automagically rendered those into beautiful graph pictures!

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -284,27 +316,27 @@ public boolean incrementToken() throws IOException {
 
         InputNode src = inputNodes.get(inputFrom);
         if (src.node == -1) {
-          // This means the "from" node of this token was never seen as a "to" node,
-          // which should only happen if we just crossed a hole.  This is a challenging
-          // case for us because we normally rely on the full dependencies expressed
-          // by the arcs to assign outgoing node IDs.  It would be better if tokens
-          // were never dropped but instead just marked deleted with a new
-          // TermDeletedAttribute (boolean valued) ... but until that future, we have

Review comment:
       We should really make progress on this :)

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +394,48 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int maxOutIndex = outputNodes.getMaxPos();
+    OutputNode outSrc = outputNodes.get(maxOutIndex);
+    // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between
+    // two tokens, it looks like a->*hole*->b.
+    // A consumed hole is between the start a long token and the next token that is "under" the path

Review comment:
       Missing `of` after `start`?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand merged pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand merged pull request #157:
URL: https://github.com/apache/lucene/pull/157


   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r644165438



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +378,40 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int maxOutIndex = outputNodes.getMaxPos();
+    OutputNode outSrc = outputNodes.get(maxOutIndex);
+    // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between

Review comment:
       Thank you, that helps a lot!




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-888027281


   We have been using this change internally for a few weeks now. We no longer encounter the `ArrayIndexOutOfBounds` exceptions that we were previously experiencing. Depending on the dataset/analyzer combination we have seen up to a 1% increase in the average number of tokens per field. This comes from the tokens that had previously been dropped now being correctly indexed.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r641212886



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -193,14 +194,25 @@ private boolean releaseBufferedToken() {
         }
         if (inputNode.tokens.size() == 0) {
           assert inputNode.nextOut == 0;
-          assert output.nextOut == 0;
           // Hole dest nodes should never be merged since 1) we always
           // assign them to a new output position, and 2) since they never
           // have arriving tokens they cannot be pushed:
-          assert output.inputNodes.size() == 1 : output.inputNodes.size();
+          // skip hole sources, but don't free until every input is checked
+          if (output.inputNodes.size() > 1) {
+            output.inputNodes.remove(output.nextOut);
+            if (output.nextOut < output.inputNodes.size()) {
+              continue;
+            }
+          }
+
           outputFrom++;
-          inputNodes.freeBefore(output.inputNodes.get(0));
+          int freeBefore = Collections.min(output.inputNodes);
+          assert outputNodes.get(outputFrom).inputNodes.stream().filter(n -> freeBefore < n).count()

Review comment:
       I'm nervous about iterating this list. It's going to scale with how many edges arrive at the same node in the output which _shouldn't_ be large. But that's a big risk for an assert 




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-861386826


   >Maybe another way to improve the checking for correctness in the randomized test (or maybe in a new randomized test) would be to randomly generate a set of strings from a limited alphabet, create the minimal automaton matching only those strings (we have a nice API to do that, efficiently, already), call flatten, and the confirm that the resulting output graph still accepts all the original strings?
   
   Are you referring to the Automoton.Builder API here?
   
   > But I think one missing part for such a test would be an "Automaton to TokenStream" converter, i.e. a "serializer" from (acyclic) Automaton to TokenStream. I think such a thing would not be too difficult to build, basically just topo sort the input graph (and throw exception if it has cycles), then emit the transitions as tokens. The `posInc` attribute is guaranteed to never go negative because of the topo sort. This would (separately) be a nice utility API to convert between these two things that are really nearly the same ;)
   
   I'm having trouble with the transition from Automoton back to TokenStream. `posInc` is easy to calculate because after a toposort it's either 1 or 1+ number of holes since last non-hole. `poslen` is giving me some trouble because it needs to know how many positions were in alternate paths. I should be able to look at each path from a node that has multiple edges, follow those paths until they converge counting token separators along the way, then take the max of those as the length to be covered. However I'm not sure how to distribute that length across paths.
   For example
   ```
    --->O--->O--->O---
   |                  |
   |                  V
   (Start)           (End)
   |                  ^
   ----->O------>O-----
   ```
   There are 3 positions on the longest path so the total positions to be covered is 3, but on the short 2 node path I don't think it's possible to tell what should be `poslen`=1 and which should be `poslen`=2. For creating a valid token stream that can match the same as the automaton can accept it might not matter. However to reverse `tokenstreamToAutomaton` we would need to get those `poslen`s right.
   We would also need to set Offsets. Offsets are completely lost in the conversion from `TokenStream` to `Automaton`.  We should be able to generate offsets that are valid for a `TokenStream` but may not reflect what the text originally looked like. For creating a general `AutomotonToTokenStream` I think this would be a problem, as `tokenstreamToAutomaton` -> `AutomotonToTokenStream` would end in a different `TokenStream` then one started with.
   
   For the generalize test I might have to create an `Automaton` from a `TokenStream` with and one without `FlattenGraphFilter`, then create the acceptable paths from the one without `FGF` and check if the `Automaton` with `FGF` can accept all of them. It's less elegant but would still confirm that the flattened graph was a `generalization`.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r643770929



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +378,40 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int maxOutIndex = outputNodes.getMaxPos();
+    OutputNode outSrc = outputNodes.get(maxOutIndex);
+    // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between

Review comment:
       I've added some ascII graphs into the comment. do those help? They're a little weird since I have tokens in node positions which isn't quite right.




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r655951001



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -284,27 +316,27 @@ public boolean incrementToken() throws IOException {
 
         InputNode src = inputNodes.get(inputFrom);
         if (src.node == -1) {
-          // This means the "from" node of this token was never seen as a "to" node,
-          // which should only happen if we just crossed a hole.  This is a challenging
-          // case for us because we normally rely on the full dependencies expressed
-          // by the arcs to assign outgoing node IDs.  It would be better if tokens
-          // were never dropped but instead just marked deleted with a new
-          // TermDeletedAttribute (boolean valued) ... but until that future, we have

Review comment:
       Working on this change has made me realize how valuable not removing tokens would be.




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r642116290



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +378,40 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int maxOutIndex = outputNodes.getMaxPos();
+    OutputNode outSrc = outputNodes.get(maxOutIndex);
+    // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between

Review comment:
       Could you add some example explaining these 2 types of holes? 
   Seems to me that consumed holes are like 
   ```
   abc: [0,3]
   b: [1,2] => c: [2,3]
   ``` 
   right? But I didn't really get what neighbor hole looks like...




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-854277244


   I love all the added test cases!
   
   Maybe in the new random test we could use `tokenstreamToAutomaton` and then confirm no dead states in that, using existing APIs?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r644165757



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -362,6 +394,48 @@ public boolean incrementToken() throws IOException {
     }
   }
 
+  private OutputNode recoverFromHole(InputNode src, int startOffset) {
+    // This means the "from" node of this token was never seen as a "to" node,
+    // which should only happen if we just crossed a hole.  This is a challenging
+    // case for us because we normally rely on the full dependencies expressed
+    // by the arcs to assign outgoing node IDs.  It would be better if tokens
+    // were never dropped but instead just marked deleted with a new
+    // TermDeletedAttribute (boolean valued) ... but until that future, we have
+    // a hack here to forcefully jump the output node ID:
+    assert src.outputNode == -1;
+    src.node = inputFrom;
+
+    int maxOutIndex = outputNodes.getMaxPos();
+    OutputNode outSrc = outputNodes.get(maxOutIndex);
+    // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between
+    // two tokens, it looks like a->*hole*->b.
+    // A consumed hole is between the start a long token and the next token that is "under" the path
+    // of the long token.
+    // It looks like :    ___abc__
+    //                   |        |
+    //                   |        V
+    //                 *hole*->b->c
+    // A consumed hole should have the outputsrc node of the short token after the hole be the out
+    // dest
+    // of the long token as that's how we'd resolve it if the missing token were present.
+    // neighbor holes should start a new output node and continue as if the hole didn't
+    // exist.
+    // Related tests testAltPathLastStepHoleFollowedByHole, testAltPathFirstStepHole,

Review comment:
       Thank you for linking the tests here!




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r642115419



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -193,14 +194,25 @@ private boolean releaseBufferedToken() {
         }
         if (inputNode.tokens.size() == 0) {
           assert inputNode.nextOut == 0;
-          assert output.nextOut == 0;
           // Hole dest nodes should never be merged since 1) we always
           // assign them to a new output position, and 2) since they never
           // have arriving tokens they cannot be pushed:
-          assert output.inputNodes.size() == 1 : output.inputNodes.size();
+          // skip hole sources, but don't free until every input is checked
+          if (output.inputNodes.size() > 1) {
+            output.inputNodes.remove(output.nextOut);
+            if (output.nextOut < output.inputNodes.size()) {
+              continue;
+            }
+          }
+
           outputFrom++;
-          inputNodes.freeBefore(output.inputNodes.get(0));
+          int freeBefore = Collections.min(output.inputNodes);
+          assert outputNodes.get(outputFrom).inputNodes.stream().filter(n -> freeBefore < n).count()

Review comment:
       I'm a bit confused about this assertion. Are we trying to assert no future node will be freed mistakenly? If that's the case, shouldn't we assert:
   ```
   assert outputNodes.get(outputFrom).inputNodes.stream().filter(n -> freeBefore > n).count() == 0
       : "FreeBefore " + freeBefore + " will free in use nodes"
   ```




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-865702423


   Thanks for the explanation. I think I understand how to do the `Automaton` to `TokenStream` now.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-852856814


   I've fleshed out the comments for the 4 change areas explaining each area and what tests exercise them. Do they help? are there areas you feel aren't fully explained or that I could be clearer on?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-854760044


   Maybe another way to improve the checking for correctness in the randomized test (or maybe in a new randomized test) would be to randomly generate a set of strings from a limited alphabet, create the minimal automaton matching only those strings (we have a nice API to do that, efficiently, already), call flatten, and the confirm that the resulting output graph still accepts all the original strings?
   
   I.e., flatten should only ever "generalize" -- accepting strings that the original machine did not -- and never "remove" previously accepted strings?
   
   But I think one missing part for such a test would be an "Automaton to TokenStream" converter, i.e. a "serializer" from (acyclic) Automaton to TokenStream.  I think such a thing would not be too difficult to build, basically just topo sort the input graph (and throw exception if it has cycles), then emit the transitions as tokens.  The `posInc` attribute is guaranteed to never go negative because of the topo sort.  This would (separately) be a nice utility API to convert between these two things that are really nearly the same ;)


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-895680595


   Thanks for the merge! You are correct, there are no API changes and it should be safe to backport. 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r642115585



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -240,7 +252,13 @@ private boolean releaseBufferedToken() {
           output.nextOut++;
           if (output.nextOut == output.inputNodes.size()) {
             outputFrom++;
-            inputNodes.freeBefore(output.inputNodes.get(0));
+            int freeBefore = Collections.min(output.inputNodes);
+            assert outputNodes.get(outputFrom).inputNodes.stream()
+                        .filter(n -> freeBefore < n)
+                        .count()
+                    > 0
+                : "FreeBefore " + output.inputNodes.get(0) + " will free in use nodes";

Review comment:
       Same question?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] zhaih commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
zhaih commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r644172488



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -255,6 +260,32 @@ private boolean releaseBufferedToken() {
     return false;
   }
 
+  /**
+   * Free output nodes before the given outputs. Free inputs nodes before the minimum input node for
+   * this output.
+   *
+   * @param output target output node
+   */
+  private void freeBefore(OutputNode output) {
+    // We've released all of the tokens that end at the current output,
+    // so free all output nodes before this. Input nodes are more complex.
+    // The second shingled tokens with alternate paths can appear later in the output graph than
+    // than some of their alternate path tokens.
+    // Because of this case we can only free from the minimum because the minimum node will have
+    // come from before the second shingled token.
+    // This means we have to hold onto input nodes who's tokens get stacked on previous nodes until
+    // we've completely passed those inputs.
+    // Related tests testShingledGap, testShingledGapWithHoles
+    outputFrom++;
+    int freeBefore = Collections.min(output.inputNodes);
+    // This will catch a node being freed early if it's input to the next output.
+    // Could a freed early node be input to a later output?
+    assert outputNodes.get(outputFrom).inputNodes.stream().filter(n -> freeBefore < n).count() > 0
+        : "FreeBefore " + output.inputNodes.get(0) + " will free in use nodes";

Review comment:
       Isn't this still the old assertion that need to be changed?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] msokolov commented on a change in pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
msokolov commented on a change in pull request #157:
URL: https://github.com/apache/lucene/pull/157#discussion_r643925065



##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -273,6 +260,32 @@ private boolean releaseBufferedToken() {
     return false;
   }
 
+  /**
+   * Free output nodes before the given outputs. Free inputs nodes before the minimum input node for
+   * this output.
+   *
+   * @param output target output node
+   */
+  private void freeBefore(OutputNode output) {
+    // We've released all of the tokens that end at the current output,
+    // so free all output nodes before this. Input nodes are more complex.
+    // The second shingled tokens with alternate paths can appear later in the output graph than

Review comment:
       "than than"

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -273,6 +260,32 @@ private boolean releaseBufferedToken() {
     return false;
   }
 
+  /**
+   * Free output nodes before the given outputs. Free inputs nodes before the minimum input node for

Review comment:
       "Free input nodes" I think

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -310,8 +323,11 @@ public boolean incrementToken() throws IOException {
           int outMax = outputNodes.getMaxPos();
           // If positionIncrement > 1 this node should be at the end of the flattened graph
           if (positionIncrement > 1 && src.outputNode < outMax) {
-            // We crossed a gap that we need to account for. This node exists from a length >1 path
-            // jumping to get here.
+            // If there was a hole at the end of an alternate path then the input and output nodes

Review comment:
       minor, but: if you use block comments, then our autoformatter won't apply its annoying line-break rules :)

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -273,6 +260,32 @@ private boolean releaseBufferedToken() {
     return false;
   }
 
+  /**
+   * Free output nodes before the given outputs. Free inputs nodes before the minimum input node for
+   * this output.
+   *
+   * @param output target output node
+   */
+  private void freeBefore(OutputNode output) {
+    // We've released all of the tokens that end at the current output,
+    // so free all output nodes before this. Input nodes are more complex.
+    // The second shingled tokens with alternate paths can appear later in the output graph than
+    // than some of their alternate path tokens.
+    // Because of this case we can only free from the minimum because the minimum node will have
+    // come from before the second shingled token.
+    // This means we have to hold onto input nodes who's tokens get stacked on previous nodes until

Review comment:
       "whose"

##########
File path: lucene/analysis/common/src/java/org/apache/lucene/analysis/core/FlattenGraphFilter.java
##########
@@ -392,12 +408,20 @@ private OutputNode recoverFromHole(InputNode src, int startOffset) {
     int maxOutIndex = outputNodes.getMaxPos();
     OutputNode outSrc = outputNodes.get(maxOutIndex);
     // There are two types of holes, neighbor holes and consumed holes. A neighbor hole is between
-    // two tokens. A consumed hole is
-    // between the start a long token and the next token that is "under" the path of the long token.
-    // A consumed hole should have the outputsrc node of the short token be the out dest
+    // two tokens, it looks like a->*hole*->b.
+    // A consumed hole is between the start a long token and the next token that is "under" the path
+    // of the long token.
+    // It looks like :    ___abc__
+    //                   |        |

Review comment:
       Have you run the formatter? I think it might mess these pictures up unless you use block comments




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-872219546


   Failure is from random testing. It looks like I'm overthinking how to handle calculating the new output node in `recoverHole`. Since multiple graphs could look the same after deletions, but would have flattened differently without the deletes, calculating future nodes in the middle of flattening isn't going to work. Instead the code will have to place at the end of the output graph adjusting for known holes.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-854820485


   Thank you for the ascii-art explanation of neighbor versus consumed holes!
   
   Do we also handle the neighbor-hole case when there is more than one long path?
   
   E.g. if the document has `the wizard of oz`, and we overlay `the_wizard` (pos len 2) and also `the_wizard_of_oz` (pos len 4) shingles on top of that, then run through `StopFilter` which deletes `the` (hmm and also `of`, but ignore that consumed hole for now), then we have a neighbor hole with three paths (the original tokens plus the two shingles).  Do we handle that / have a test case for it?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-895357881


   +1, thanks @glawson0 -- I'll try to merge this soon.
   
   I think this is also safe to backport?  No API breaks, and it is "just" fixing bugs in this hairy `TokenFilter`?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] mikemccand commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
mikemccand commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-854277244


   I love all the added test cases!
   
   Maybe in the new random test we could use `tokenstreamToAutomaton` and then confirm no dead states in that, using existing APIs?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] glawson0 commented on pull request #157: LUCENE-9963 Fix issue with FlattenGraphFilter throwing exceptions from holes

Posted by GitBox <gi...@apache.org>.
glawson0 commented on pull request #157:
URL: https://github.com/apache/lucene/pull/157#issuecomment-871334072


   Simplified `AutomatonToTokenStream` and added license comment.
   
   I beasted the random tests a few hundred times and found 2 issues.
   1)When completely separated edges get connected it can introduce gaps and cause book keeping errors.
   2)The `checkGeneralization` test can miss paths where a hole in the unflattened graph would cross multiple nodes.
   
   The logic to navigate around issue 2 slows down `checkGeneralization` to the point I don't think it is useful so I commented that portion out. The test that calls it still checks if asserts are getting hit, and `testPathsNotLost` is checking if strings to make an automaton are accepted after the automaton is flattened.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org