Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
proc += gen.decl(node, self.node_type, gen.stack_peek(stack))
proc += gen.stack_pop(stack)
proc += gen.if_true(self.is_leaf(gen, node))
# TODO: determine when this if-check is necessary! It isn't for
# Bullet, but it _is_ in general.
# proc += gen.if_true(self.query_holds(gen, gen.get_field(node, self.leaf_ptr)))
proc += gen.set(cursor, gen.get_field(node, self.leaf_ptr))
proc += gen.break_loop()
# proc += gen.endif()
proc += gen.else_true()
if True:
l = fresh_name("left")
r = fresh_name("right")
proc += gen.decl(l, self.node_type, gen.get_field(node, self.left_ptr))
proc += gen.decl(r, self.node_type, gen.get_field(node, self.right_ptr))
for n in (l, r):
proc += gen.if_true(self.intersects_query(gen, n))
proc += gen.stack_push(stack, n)
proc += gen.endif()
else:
proc += gen.if_true(self.intersects_query(gen, node))
proc += gen.stack_push(stack, gen.get_field(node, self.left_ptr))
proc += gen.stack_push(stack, gen.get_field(node, self.right_ptr))
proc += gen.endif()
def gen_insert(self, gen, x, parent_structure):
wrapper = fresh_name("leaf")
proc = gen.decl(wrapper, self.node_type, gen.alloc(self.node_type.ty, []))
for f,v in self.spec.lts + self.spec.gts:
proc += gen.set(gen.get_field(wrapper, self.remap[f]), gen.get_field(x, f))
proc += gen.set(gen.get_field(wrapper, self.left_ptr), gen.null_value())
proc += gen.set(gen.get_field(wrapper, self.right_ptr), gen.null_value())
proc += gen.set(gen.get_field(wrapper, self.parent_ptr), gen.null_value())
proc += gen.set(gen.get_field(wrapper, self.leaf_ptr), x)
proc += gen.set(gen.get_field(x, self.record_parent_ptr), wrapper)
# No root? Put it there.
proc += gen.if_true(gen.is_null(parent_structure.field(gen, self.root)))
proc += gen.set(parent_structure.field(gen, self.root), wrapper)
proc += gen.else_true()
# Descend to the right spot.
p, sibling = self.find_insertion_point(gen, x, parent_structure.field(gen, self.root))
def find_first(self, gen, tree_root):
cursor = fresh_name("cursor")
out = fresh_name("first")
proc = gen.decl(cursor, self.node_type, tree_root)
proc += gen.decl(out, RecordType(), gen.null_value())
proc += gen.while_true(gen.true_value())
# greedy descent until you find a leaf
proc += gen.while_true(gen.not_true(self.is_leaf(gen, cursor)))
proc += gen.if_true(self.intersects_query(gen, gen.get_field(cursor, self.left_ptr)))
proc += gen.set(cursor, gen.get_field(cursor, self.left_ptr))
proc += gen.else_if(self.intersects_query(gen, gen.get_field(cursor, self.right_ptr)))
proc += gen.set(cursor, gen.get_field(cursor, self.right_ptr))
proc += gen.else_true()
proc += gen.break_loop()
proc += gen.endif()
def gen_insert_with_index(self, gen, x, parent_structure, indexval):
name = parent_structure.field(gen, self.name)
prev = fresh_name("previous")
curr = fresh_name("current")
is_left = fresh_name("is_left")
proc = gen.set(gen.get_field(x, self.left_ptr), gen.null_value())
proc += gen.set(gen.get_field(x, self.right_ptr), gen.null_value())
for aug in self.augData:
proc += gen.set(gen.get_field(x, aug.real_field), gen.get_field(x, aug.orig_field))
if self.balance == BALANCE_AVL:
proc += gen.set(gen.get_field(x, self.height_name), "0")
proc += gen.decl(prev, self.ty, gen.null_value())
proc += gen.decl(curr, self.ty, name)
proc += gen.decl(is_left, BoolTy(), gen.false_value())
# find insertion point
proc += gen.while_true(gen.not_true(gen.is_null(curr)))
def find_match(self, gen, hashcode, node, level):
proc = gen.while_true(gen.le(IntTy(), level, 8)) # Bad style
match = fresh_name("match")
bits = fresh_name("bits")
proc += gen.decl(match, NodeTy(self.node_ty.name))
proc += gen.decl(bits, IntTy(), 0)
proc += self.get_match_node(gen, match, node, bits, hashcode, gen.mul(self.length_name, level), self.length_name)
# if
proc += gen.if_true(gen.is_null(match))
proc += gen.break_loop();
proc += gen.endif()
# end if
proc += gen.set(node, match)
proc += gen.plus_one(level)
proc += gen.endwhile()
return proc
def gen_insert_with_index(self, gen, x, parent_structure, indexval):
name = parent_structure.field(gen, self.name)
prev = fresh_name("previous")
curr = fresh_name("current")
is_left = fresh_name("is_left")
proc = gen.set(gen.get_field(x, self.left_ptr), gen.null_value())
proc += gen.set(gen.get_field(x, self.right_ptr), gen.null_value())
for aug in self.augData:
proc += gen.set(gen.get_field(x, aug.real_field), gen.get_field(x, aug.orig_field))
if self.balance == BALANCE_AVL:
proc += gen.set(gen.get_field(x, self.height_name), "0")
proc += gen.decl(prev, self.ty, gen.null_value())
proc += gen.decl(curr, self.ty, name)
proc += gen.decl(is_left, BoolTy(), gen.false_value())
# find insertion point
proc += gen.while_true(gen.not_true(gen.is_null(curr)))
proc += gen.set(prev, curr)
def _rotate(self, gen, x, child, parent_structure):
otherchild = self.left_ptr if child == self.right_ptr else self.right_ptr
proc = gen.comment("rotate {}".format(gen.get_field(x, child)))
a = fresh_name("a")
b = fresh_name("b")
c = fresh_name("c")
proc += gen.decl(a, RecordType(), x) # non-null
# proc += "assert({}); //1\n".format(gen.not_true(gen.is_null(a)))
proc += gen.decl(b, RecordType(), gen.get_field(a, child)) # non-null
# proc += "assert({}); //2\n".format(gen.not_true(gen.is_null(b)))
proc += gen.decl(c, RecordType(), gen.get_field(b, otherchild)) # maybe null
proc += self.replace_node_in_parent(gen, gen.get_field(a, self.parent_ptr), a, b)
proc += self.replace_node_in_parent(gen, b, c, a, otherchild)
# proc += "assert({}); //3\n".format(gen.same(a, gen.get_field(b, otherchild)))
proc += self.replace_node_in_parent(gen, a, b, c, child)
# proc += "assert({}); //4\n".format(gen.same(gen.get_field(a, child), c))
proc += self.recompute_all_augdata(gen, a)
proc += self.recompute_all_augdata(gen, b)
proc += gen.if_true(gen.not_true(gen.is_null(gen.get_field(b, self.parent_ptr))))
proc += self.recompute_all_augdata(gen, gen.get_field(b, self.parent_ptr))
def lookup(self, gen, m, k):
"""returns proc, handle"""
handle = fresh_name("maphandle")
proc = gen.decl(handle, self.handle_type())
proc += gen.map_find_handle(m, k, handle)
return proc, handle
def handle_exists(self, gen, m, handle):
def gen_query_one(self, gen, qvars, parent_structure):
if self.op == CONCAT_OP:
result = fresh_name("result")
proc = gen.decl(result, RecordType())
proc1, r1 = self.ty1.gen_query_one(gen, qvars, parent_structure)
proc += proc1
proc += gen.set(result, r1)
proc += gen.if_true(gen.is_null(result))
proc2, r2 = self.ty2.gen_query_one(gen, qvars, parent_structure)
proc += proc2
proc += gen.set(result, r2)
proc += gen.endif()
return (proc, result)
else:
raise Exception("unknown op {}".format(self.op))
def gen_find_any(self, gen, parent_structure):
def __init__(self, spec, fields, predicate, stack_iteration=False):
self.stack_iteration = stack_iteration
self.spec = spec
self.field_types = fields
self.the_type = NativeTy(fields[spec.lts[0][0]])
self.predicate = predicate
self.root = fresh_name("root")
self.left_ptr = fresh_name("left")
self.right_ptr = fresh_name("right")
self.leaf_ptr = fresh_name("leaf")
self.stack_name = fresh_name("stack")
self.prev_name = fresh_name("prev")
self.cursor_name = fresh_name("cursor")
self.parent_ptr = fresh_name("parent")
self.record_parent_ptr = fresh_name("parent")
self.remap = { f : fresh_name(f) for f, _ in (self.spec.lts + self.spec.gts) }
myfields = [f for f, _ in spec.lts] + [f for f, _ in spec.gts]
self.node_type = TupleTy(collections.OrderedDict(
[(self.remap[f], NativeTy(fields[f])) for f in myfields]))
self.node_type.fields[self.left_ptr] = PointerTy(self.node_type)
self.node_type.fields[self.right_ptr] = PointerTy(self.node_type)
self.node_type.fields[self.parent_ptr] = PointerTy(self.node_type)