class_docstr: Base class for implementations of deterministic finite
  automata.
  
  This is abstract to allow for the possibility of states
  being calculated lazily as we traverse the DFA (which
  we make heavy use of in our L* implementation - see
  lstar.py for details).
  
  States can be of any hashable type.
class_docstr_tok: ["Base","class","for","implementations","of","deterministic","finite","automata",".","This","is","abstract","to","allow","for","the","possibility","of","states","being","calculated","lazily","as","we","traverse","the","DFA","(","which","we","make","heavy","use","of","in","our","L","*","implementation","-","see","lstar.py","for","details",")",".","States","can","be","of","any","hashable","type","."]
docstr: Returns the maximum length of a string that is
  accepted when starting from i.
docstr_tok: ["Returns","the","maximum","length","of","a","string","that","is","accepted","when","starting","from","i","."]
code: def max_length(self, i):
      """Returns the maximum length of a string that is
      accepted when starting from i."""
      if self.is_dead(i):
          return 0
  
      cache = self.__cache("max_length")
  
      try:
          return cache[i]
      except KeyError:
          pass
  
      # Naively we can calculate this as 1 longer than the
      # max length of the non-dead states this can immediately
      # transition to, but a) We don't want unbounded recursion
      # because that's how you get RecursionErrors and b) This
      # makes it hard to look for cycles. So we basically do
      # the recursion explicitly with a stack, but we maintain
      # a parallel set that tracks what's already on the stack
      # so that when we encounter a loop we can immediately
      # determine that the max length here is infinite.
  
      stack = [i]
      stack_set = {i}
  
      def pop():
          """Remove the top element from the stack, maintaining
          the stack set appropriately."""
          assert len(stack) == len(stack_set)
          j = stack.pop()
          stack_set.remove(j)
          assert len(stack) == len(stack_set)
  
      while stack:
          j = stack[-1]
          assert not self.is_dead(j)
          # If any of the children have infinite max_length we don't
          # need to check all of them to know that this state does
          # too.
          if any(cache.get(k) == inf for k in self.successor_states(j)):
              cache[j] = inf
              pop()
              continue
  
          # Recurse to the first child node that we have not yet
          # calculated max_length for.
          for k in self.successor_states(j):
              if k in stack_set:
                  # k is part of a loop and is known to be live
                  # (since we never push dead states on the stack),
                  # so it can reach strings of unbounded length.
                  assert not self.is_dead(k)
                  cache[k] = inf
                  break
              elif k not in cache and not self.is_dead(k):
                  stack.append(k)
                  stack_set.add(k)
                  break
          else:
              # All of j's successors have a known max_length or are dead,
              # so we can now compute a max_length for j itself.
              cache[j] = max(
                  (
                      1 + cache[k]
                      for k in self.successor_states(j)
                      if not self.is_dead(k)
                  ),
                  default=0,
              )
  
              # j is live so it must either be accepting or have a live child.
              assert self.is_accepting(j) or cache[j] > 0
              pop()
      return cache[i]
  
imports: import threading
  from collections import Counter, defaultdict, deque
  from math import inf
  from hypothesis.internal.reflection import proxies
label_desc: Use image node_id 11 for calling the DFA obj's underlying member method code with example usage: obj.max_length(i) and returns: cache, int, cache