nodes: 0, module; 1, function_definition; 2, function_name:find_write_predecessors; 3, parameters; 4, block; 5, identifier:self; 6, identifier:address; 7, expression_statement; 8, comment:# A write operation must be preceded by:; 9, comment:#   - The "enclosing writer", which is the writer at the address or; 10, comment:#     the nearest writer higher (closer to the root) in the tree.; 11, comment:#   - The "enclosing readers", which are the readers at the address; 12, comment:#     or higher in the tree.; 13, comment:#   - The "children writers", which include all writers which are; 14, comment:#     lower in the tree than the address.; 15, comment:#   - The "children readers", which include all readers which are; 16, comment:#     lower in the tree than the address.; 17, comment:#; 18, comment:# The enclosing writer must be added as it may have modified a node; 19, comment:# which must not happen after the current write.; 20, comment:#; 21, comment:# Writers which are higher in the tree than the enclosing writer may; 22, comment:# have modified a node at or under the given address.  However, we do; 23, comment:# not need to include them here as they will have been considered a; 24, comment:# predecessor to the enclosing writer.; 25, comment:#; 26, comment:# Enclosing readers must be included.  Technically, we only need to add; 27, comment:# enclosing readers which occurred after the enclosing writer, since; 28, comment:# the readers preceding the writer will have been considered a; 29, comment:# predecessor of the enclosing writer.  However, with the current; 30, comment:# data structure we can not determine the difference between readers; 31, comment:# so we specify them all; this is mostly harmless as it will not change; 32, comment:# the eventual sort order generated by the scheduler.; 33, comment:#; 34, comment:# Children readers must be added, since their reads must happen prior; 35, comment:# to the write.; 36, expression_statement; 37, expression_statement; 38, expression_statement; 39, expression_statement; 40, comment:# First, walk down from the root to the address, collecting all readers; 41, comment:# and updating the enclosing_writer if needed.; 42, try_statement; 43, comment:# Next, descend down the tree starting at the address node and; 44, comment:# find all descendant readers and writers.; 45, for_statement; 46, return_statement; 47, comment:"""Returns all predecessor transaction ids for a write of the provided
          address.
  
          Arguments:
              address (str): the radix address
  
          Returns: a set of transaction ids
          """; 48, assignment; 49, assignment; 50, assignment; 51, assignment; 52, block; 53, comment:# If the address isn't on the tree, then there aren't any; 54, comment:# predecessors below the node to worry about (because there; 55, comment:# isn't anything at all), so return the predecessors that have; 56, comment:# already been collected.; 57, except_clause; 58, finally_clause; 59, pattern_list; 60, identifier:node_stream; 61, block; 62, identifier:predecessors; 63, identifier:predecessors; 64, call; 65, identifier:enclosing_writer; 66, None; 67, identifier:node_stream; 68, call; 69, identifier:address_len; 70, call; 71, for_statement; 72, as_pattern; 73, block; 74, block; 75, identifier:_; 76, identifier:node; 77, if_statement; 78, identifier:set; 79, argument_list; 80, attribute; 81, argument_list; 82, identifier:len; 83, argument_list; 84, pattern_list; 85, identifier:node_stream; 86, block; 87, identifier:AddressNotInTree; 88, as_pattern_target; 89, if_statement; 90, return_statement; 91, if_statement; 92, comparison_operator:node is not None; 93, block; 94, attribute; 95, identifier:walk; 96, identifier:address; 97, identifier:address; 98, identifier:node_address; 99, identifier:node; 100, if_statement; 101, identifier:err; 102, comparison_operator:err.match is not None; 103, block; 104, identifier:predecessors; 105, comparison_operator:enclosing_writer is not None; 106, block; 107, identifier:node; 108, None; 109, if_statement; 110, expression_statement; 111, identifier:self; 112, identifier:_tree; 113, comparison_operator:node is not None; 114, block; 115, attribute; 116, None; 117, return_statement; 118, identifier:enclosing_writer; 119, None; 120, expression_statement; 121, comparison_operator:node.writer is not None; 122, block; 123, call; 124, identifier:node; 125, None; 126, expression_statement; 127, if_statement; 128, if_statement; 129, identifier:err; 130, identifier:match; 131, call; 132, call; 133, attribute; 134, None; 135, expression_statement; 136, attribute; 137, argument_list; 138, call; 139, comparison_operator:node.writer is not None; 140, block; 141, comparison_operator:len(node_address) >= address_len; 142, block; 143, attribute; 144, argument_list; 145, attribute; 146, argument_list; 147, identifier:node; 148, identifier:writer; 149, call; 150, identifier:predecessors; 151, identifier:update; 152, attribute; 153, attribute; 154, argument_list; 155, attribute; 156, None; 157, expression_statement; 158, call; 159, identifier:address_len; 160, break_statement; 161, identifier:self; 162, identifier:find_write_predecessors; 163, attribute; 164, identifier:predecessors; 165, identifier:add; 166, identifier:enclosing_writer; 167, attribute; 168, argument_list; 169, identifier:node; 170, identifier:readers; 171, identifier:predecessors; 172, identifier:update; 173, attribute; 174, identifier:node; 175, identifier:writer; 176, assignment; 177, identifier:len; 178, argument_list; 179, identifier:err; 180, identifier:match; 181, identifier:predecessors; 182, identifier:add; 183, attribute; 184, identifier:node; 185, identifier:readers; 186, identifier:enclosing_writer; 187, attribute; 188, identifier:node_address; 189, identifier:node; 190, identifier:writer; 191, identifier:node; 192, identifier:writer
code: def find_write_predecessors(self, address):
          """Returns all predecessor transaction ids for a write of the provided
          address.
  
          Arguments:
              address (str): the radix address
  
          Returns: a set of transaction ids
          """
          # A write operation must be preceded by:
          #   - The "enclosing writer", which is the writer at the address or
          #     the nearest writer higher (closer to the root) in the tree.
          #   - The "enclosing readers", which are the readers at the address
          #     or higher in the tree.
          #   - The "children writers", which include all writers which are
          #     lower in the tree than the address.
          #   - The "children readers", which include all readers which are
          #     lower in the tree than the address.
          #
          # The enclosing writer must be added as it may have modified a node
          # which must not happen after the current write.
          #
          # Writers which are higher in the tree than the enclosing writer may
          # have modified a node at or under the given address.  However, we do
          # not need to include them here as they will have been considered a
          # predecessor to the enclosing writer.
          #
          # Enclosing readers must be included.  Technically, we only need to add
          # enclosing readers which occurred after the enclosing writer, since
          # the readers preceding the writer will have been considered a
          # predecessor of the enclosing writer.  However, with the current
          # data structure we can not determine the difference between readers
          # so we specify them all; this is mostly harmless as it will not change
          # the eventual sort order generated by the scheduler.
          #
          # Children readers must be added, since their reads must happen prior
          # to the write.
  
          predecessors = set()
  
          enclosing_writer = None
  
          node_stream = self._tree.walk(address)
  
          address_len = len(address)
  
          # First, walk down from the root to the address, collecting all readers
          # and updating the enclosing_writer if needed.
  
          try:
              for node_address, node in node_stream:
                  if node is not None:
                      predecessors.update(node.readers)
  
                      if node.writer is not None:
                          enclosing_writer = node.writer
  
                      if len(node_address) >= address_len:
                          break
  
          # If the address isn't on the tree, then there aren't any
          # predecessors below the node to worry about (because there
          # isn't anything at all), so return the predecessors that have
          # already been collected.
          except AddressNotInTree as err:
              if err.match is not None:
                  return self.find_write_predecessors(err.match)
  
              return predecessors
  
          finally:
              if enclosing_writer is not None:
                  predecessors.add(enclosing_writer)
  
          # Next, descend down the tree starting at the address node and
          # find all descendant readers and writers.
  
          for _, node in node_stream:
              if node is not None:
                  if node.writer is not None:
                      predecessors.add(node.writer)
  
                  predecessors.update(node.readers)
  
          return predecessors