| 295 | return topoorder, linear_data, inverse |
| 296 | |
| 297 | def compute_packed(self, order): |
| 298 | def compute_chunk(node, offsets): |
| 299 | """ compute the packed node/edge data for a node. result is a |
| 300 | list of bytes as long as order. the jump distance calculations use |
| 301 | the offsets dictionary to know where in the final big output |
| 302 | bytestring the individual nodes will end up. """ |
| 303 | result = bytearray() |
| 304 | offset = offsets[node] |
| 305 | encode_varint_unsigned(number_add_bits(node.num_reachable_linear, node.final), result) |
| 306 | if len(node.linear_edges) == 0: |
| 307 | assert node.final |
| 308 | encode_varint_unsigned(0, result) # add a 0 saying "done" |
| 309 | prev_child_offset = offset + len(result) |
| 310 | for edgeindex, (label, targetnode) in enumerate(node.linear_edges): |
| 311 | label = label.encode('ascii') |
| 312 | child_offset = offsets[targetnode] |
| 313 | child_offset_difference = child_offset - prev_child_offset |
| 314 | |
| 315 | info = number_add_bits(child_offset_difference, len(label) == 1, edgeindex == len(node.linear_edges) - 1) |
| 316 | if edgeindex == 0: |
| 317 | assert info != 0 |
| 318 | encode_varint_unsigned(info, result) |
| 319 | prev_child_offset = child_offset |
| 320 | if len(label) > 1: |
| 321 | encode_varint_unsigned(len(label), result) |
| 322 | result.extend(label) |
| 323 | return result |
| 324 | |
| 325 | def compute_new_offsets(chunks, offsets): |
| 326 | """ Given a list of chunks, compute the new offsets (by adding the |
| 327 | chunk lengths together). Also check if we cannot shrink the output |
| 328 | further because none of the node offsets are smaller now. if that's |
| 329 | the case return None. """ |
| 330 | new_offsets = {} |
| 331 | curr_offset = 0 |
| 332 | should_continue = False |
| 333 | for node, result in zip(order, chunks): |
| 334 | if curr_offset < offsets[node]: |
| 335 | # the new offset is below the current assumption, this |
| 336 | # means we can shrink the output more |
| 337 | should_continue = True |
| 338 | new_offsets[node] = curr_offset |
| 339 | curr_offset += len(result) |
| 340 | if not should_continue: |
| 341 | return None |
| 342 | return new_offsets |
| 343 | |
| 344 | # assign initial offsets to every node |
| 345 | offsets = {} |
| 346 | for i, node in enumerate(order): |
| 347 | # we don't know position of the edge yet, just use something big as |
| 348 | # the starting position. we'll have to do further iterations anyway, |
| 349 | # but the size is at least a lower limit then |
| 350 | offsets[node] = i * 2 ** 30 |
| 351 | |
| 352 | |
| 353 | # due to the variable integer width encoding of edge targets we need to |
| 354 | # run this to fixpoint. in the process we shrink the output more and |