From 91158337a10c006971b66818cabb2e1bed3d494a Mon Sep 17 00:00:00 2001 From: Nathanael Sensfelder Date: Mon, 2 Nov 2020 22:31:35 +0100 Subject: Adds sort & sublist computation/instruction. --- data/tests/sublist_sort.fate | 39 +++++ .../v1/compiler/fate/v1/ComputationCompiler.java | 146 +++++++++++++--- .../v1/compiler/fate/v1/InstructionCompiler.java | 188 ++++++++++++++++++--- .../wyrd/v1/compiler/util/BinarySearch.java | 69 ++++++-- .../src/tonkadur/wyrd/v1/compiler/util/Clear.java | 65 +------ .../src/tonkadur/wyrd/v1/compiler/util/Sort.java | 129 +++++++++++++- .../tonkadur/wyrd/v1/compiler/util/SubList.java | 159 +++++++++++++++++ 7 files changed, 678 insertions(+), 117 deletions(-) create mode 100644 data/tests/sublist_sort.fate create mode 100644 src/core/src/tonkadur/wyrd/v1/compiler/util/SubList.java diff --git a/data/tests/sublist_sort.fate b/data/tests/sublist_sort.fate new file mode 100644 index 0000000..6ee7fc2 --- /dev/null +++ b/data/tests/sublist_sort.fate @@ -0,0 +1,39 @@ +(fate_version 1) + +(global (list int) li0) +(global (list int) li1) +(global (list int) li2) +(global (list int) li3) + +(global (list int) ili1) +(global (list int) ili2) +(global (list int) ili3) + +(global (lambda int (int int)) sort_fun) + +(set sort_fun + (lambda ((int x) (int y)) + (cond + ((< x y) -1) + ((> x y) 1) + ((true) 0) + ) + ) +) + +(set li0 (range 0 10 1)) +(set ili1 (var li0)) +(set ili3 (var li0)) + +(set li3 (sublist 3 6 li0)) +(sublist! 3 6 ili3) + +(set li1 (shuffle li0)) +(shuffle! ili1) + +(set ili2 (var ili1)) +(sort! sort_fun ili2) +(set li2 (sort sort_fun li1)) + + +(end) diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java index fa4ae49..2fab9bf 100644 --- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java +++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/ComputationCompiler.java @@ -25,30 +25,32 @@ import tonkadur.wyrd.v1.lang.instruction.SetPC; import tonkadur.wyrd.v1.compiler.util.AddElement; import tonkadur.wyrd.v1.compiler.util.AddElementsOf; import tonkadur.wyrd.v1.compiler.util.BinarySearch; -import tonkadur.wyrd.v1.compiler.util.IfElse; -import tonkadur.wyrd.v1.compiler.util.If; -import tonkadur.wyrd.v1.compiler.util.Fold; +import tonkadur.wyrd.v1.compiler.util.CountOccurrences; +import tonkadur.wyrd.v1.compiler.util.CreateCons; import tonkadur.wyrd.v1.compiler.util.FilterLambda; +import tonkadur.wyrd.v1.compiler.util.Fold; +import tonkadur.wyrd.v1.compiler.util.If; +import tonkadur.wyrd.v1.compiler.util.IfElse; import tonkadur.wyrd.v1.compiler.util.IndexedFilterLambda; -import tonkadur.wyrd.v1.compiler.util.Shuffle; -import tonkadur.wyrd.v1.compiler.util.RemoveAt; -import tonkadur.wyrd.v1.compiler.util.RemoveElementsOf; -import tonkadur.wyrd.v1.compiler.util.InsertAt; -import tonkadur.wyrd.v1.compiler.util.RemoveAllOf; import tonkadur.wyrd.v1.compiler.util.IndexedMapLambda; -import tonkadur.wyrd.v1.compiler.util.PartitionLambda; +import tonkadur.wyrd.v1.compiler.util.IndexedMergeLambda; import tonkadur.wyrd.v1.compiler.util.IndexedPartitionLambda; +import tonkadur.wyrd.v1.compiler.util.InsertAt; +import tonkadur.wyrd.v1.compiler.util.IterativeSearch; +import tonkadur.wyrd.v1.compiler.util.LambdaEvaluation; import tonkadur.wyrd.v1.compiler.util.MapLambda; -import tonkadur.wyrd.v1.compiler.util.PopElement; import tonkadur.wyrd.v1.compiler.util.MergeLambda; -import tonkadur.wyrd.v1.compiler.util.IndexedMergeLambda; +import tonkadur.wyrd.v1.compiler.util.PartitionLambda; +import tonkadur.wyrd.v1.compiler.util.PopElement; +import tonkadur.wyrd.v1.compiler.util.RemoveAllOf; +import tonkadur.wyrd.v1.compiler.util.RemoveAt; +import tonkadur.wyrd.v1.compiler.util.RemoveElementsOf; import tonkadur.wyrd.v1.compiler.util.RemoveOneOf; import tonkadur.wyrd.v1.compiler.util.ReverseList; -import tonkadur.wyrd.v1.compiler.util.CreateCons; -import tonkadur.wyrd.v1.compiler.util.IterativeSearch; -import tonkadur.wyrd.v1.compiler.util.CountOccurrences; +import tonkadur.wyrd.v1.compiler.util.Shuffle; +import tonkadur.wyrd.v1.compiler.util.Sort; +import tonkadur.wyrd.v1.compiler.util.SubList; import tonkadur.wyrd.v1.compiler.util.While; -import tonkadur.wyrd.v1.compiler.util.LambdaEvaluation; import tonkadur.wyrd.v1.lang.computation.*; @@ -2879,8 +2881,54 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor ) throws Throwable { - /* TODO */ - System.err.println("[P] Using unimplemented SubListComputation."); + final ComputationCompiler address_compiler, start_compiler, end_compiler; + final Register result; + + result = reserve(TypeCompiler.compile(compiler, n.get_type())); + result_as_address = result.get_address(); + result_as_computation = result.get_value(); + + address_compiler = new ComputationCompiler(compiler); + start_compiler = new ComputationCompiler(compiler); + end_compiler = new ComputationCompiler(compiler); + + n.get_collection().get_visited_by(address_compiler); + + if (address_compiler.has_init()) + { + init_instructions.add(address_compiler.get_init()); + } + + n.get_start_index().get_visited_by(start_compiler); + + if (start_compiler.has_init()) + { + init_instructions.add(start_compiler.get_init()); + } + + n.get_end_index().get_visited_by(end_compiler); + + if (end_compiler.has_init()) + { + init_instructions.add(end_compiler.get_init()); + } + + init_instructions.add + ( + SubList.generate + ( + compiler.registers(), + compiler.assembler(), + start_compiler.get_computation(), + end_compiler.get_computation(), + address_compiler.get_address(), + result_as_address + ) + ); + + start_compiler.release_registers(init_instructions); + end_compiler.release_registers(init_instructions); + address_compiler.release_registers(init_instructions); } @Override @@ -3092,8 +3140,66 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor ) throws Throwable { - /* TODO */ - System.err.println("[P] Using unimplemented SortComputation."); + final List params; + final ComputationCompiler lambda_cc, in_collection_cc; + final Register result; + + result = reserve(TypeCompiler.compile(compiler, n.get_type())); + + result_as_address = result.get_address(); + result_as_computation = result.get_value(); + + params = new ArrayList(); + + for + ( + final tonkadur.fate.v1.lang.meta.Computation p: + n.get_extra_parameters() + ) + { + final ComputationCompiler param_cc; + + param_cc = new ComputationCompiler(compiler); + + p.get_visited_by(param_cc); + + /* Let's not re-compute the parameters on every iteration. */ + param_cc.generate_address(); + + assimilate(param_cc); + + params.add(param_cc.get_computation()); + } + + lambda_cc = new ComputationCompiler(compiler); + + n.get_lambda_function().get_visited_by(lambda_cc); + + assimilate(lambda_cc); + + in_collection_cc = new ComputationCompiler(compiler); + + n.get_collection().get_visited_by(in_collection_cc); + + if (in_collection_cc.has_init()) + { + init_instructions.add(in_collection_cc.get_init()); + } + + init_instructions.add + ( + Sort.generate + ( + compiler.registers(), + compiler.assembler(), + lambda_cc.get_computation(), + in_collection_cc.get_address(), + result_as_address, + params + ) + ); + + in_collection_cc.release_registers(init_instructions); } @Override @@ -3381,6 +3487,8 @@ implements tonkadur.fate.v1.lang.meta.ComputationVisitor result_as_address ) ); + + element_compiler.release_registers(init_instructions); } @Override diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java index d27f865..679fcea 100644 --- a/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java +++ b/src/core/src/tonkadur/wyrd/v1/compiler/fate/v1/InstructionCompiler.java @@ -45,29 +45,31 @@ import tonkadur.wyrd.v1.lang.instruction.SetValue; import tonkadur.wyrd.v1.compiler.util.AddElement; import tonkadur.wyrd.v1.compiler.util.AddElementsOf; import tonkadur.wyrd.v1.compiler.util.BinarySearch; -import tonkadur.wyrd.v1.compiler.util.InsertAt; +import tonkadur.wyrd.v1.compiler.util.Clear; +import tonkadur.wyrd.v1.compiler.util.FilterLambda; import tonkadur.wyrd.v1.compiler.util.If; import tonkadur.wyrd.v1.compiler.util.IfElse; -import tonkadur.wyrd.v1.compiler.util.InstructionManager; -import tonkadur.wyrd.v1.compiler.util.NOP; -import tonkadur.wyrd.v1.compiler.util.While; import tonkadur.wyrd.v1.compiler.util.IndexedFilterLambda; -import tonkadur.wyrd.v1.compiler.util.FilterLambda; -import tonkadur.wyrd.v1.compiler.util.Shuffle; -import tonkadur.wyrd.v1.compiler.util.Clear; -import tonkadur.wyrd.v1.compiler.util.MapLambda; -import tonkadur.wyrd.v1.compiler.util.PopElement; -import tonkadur.wyrd.v1.compiler.util.MergeLambda; +import tonkadur.wyrd.v1.compiler.util.IndexedMapLambda; import tonkadur.wyrd.v1.compiler.util.IndexedMergeLambda; -import tonkadur.wyrd.v1.compiler.util.PartitionLambda; import tonkadur.wyrd.v1.compiler.util.IndexedPartitionLambda; -import tonkadur.wyrd.v1.compiler.util.IndexedMapLambda; +import tonkadur.wyrd.v1.compiler.util.InsertAt; +import tonkadur.wyrd.v1.compiler.util.InstructionManager; import tonkadur.wyrd.v1.compiler.util.IterativeSearch; +import tonkadur.wyrd.v1.compiler.util.MapLambda; +import tonkadur.wyrd.v1.compiler.util.MergeLambda; +import tonkadur.wyrd.v1.compiler.util.NOP; +import tonkadur.wyrd.v1.compiler.util.PartitionLambda; +import tonkadur.wyrd.v1.compiler.util.PopElement; import tonkadur.wyrd.v1.compiler.util.RemoveAllOf; +import tonkadur.wyrd.v1.compiler.util.RemoveAt; import tonkadur.wyrd.v1.compiler.util.RemoveElementsOf; import tonkadur.wyrd.v1.compiler.util.RemoveOneOf; import tonkadur.wyrd.v1.compiler.util.ReverseList; -import tonkadur.wyrd.v1.compiler.util.RemoveAt; +import tonkadur.wyrd.v1.compiler.util.Shuffle; +import tonkadur.wyrd.v1.compiler.util.Sort; +import tonkadur.wyrd.v1.compiler.util.SubList; +import tonkadur.wyrd.v1.compiler.util.While; public class InstructionCompiler implements tonkadur.fate.v1.lang.meta.InstructionVisitor @@ -386,7 +388,6 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor ( compiler.registers(), compiler.assembler(), - new Size(collection_address), collection_address ) ); @@ -635,8 +636,91 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor ) throws Throwable { - /* TODO */ - System.err.println("[P] Using unimplemented Sort."); + final ComputationCompiler lambda_cc; + final List params; + final List param_cc_list; + final ComputationCompiler collection_cc; + final Register sorted_result; + + params = new ArrayList(); + param_cc_list = new ArrayList(); + + lambda_cc = new ComputationCompiler(compiler); + + n.get_lambda_function().get_visited_by(lambda_cc); + + if (lambda_cc.has_init()) + { + result.add(lambda_cc.get_init()); + } + + collection_cc = new ComputationCompiler(compiler); + + n.get_collection().get_visited_by(collection_cc); + + if (collection_cc.has_init()) + { + result.add(collection_cc.get_init()); + } + + for + ( + final tonkadur.fate.v1.lang.meta.Computation p: + n.get_extra_parameters() + ) + { + final ComputationCompiler param_cc; + + param_cc = new ComputationCompiler(compiler); + + p.get_visited_by(param_cc); + + /* Let's not re-compute the parameters on every iteration. */ + param_cc.generate_address(); + + if (param_cc.has_init()) + { + result.add(param_cc.get_init()); + } + + param_cc_list.add(param_cc); + + params.add(param_cc.get_computation()); + } + + sorted_result = + compiler.registers().reserve + ( + collection_cc.get_computation().get_type(), + result + ); + + result.add + ( + Sort.generate + ( + compiler.registers(), + compiler.assembler(), + lambda_cc.get_computation(), + collection_cc.get_address(), + sorted_result.get_address(), + params + ) + ); + + result.add + ( + new SetValue(collection_cc.get_address(), sorted_result.get_value()) + ); + + compiler.registers().release(sorted_result, result); + + collection_cc.release_registers(result); + + for (final ComputationCompiler cc: param_cc_list) + { + cc.release_registers(result); + } } @Override @@ -1051,8 +1135,68 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor ) throws Throwable { - /* TODO */ - System.err.println("[P] Using unimplemented SubList."); + final ComputationCompiler address_compiler, start_compiler, end_compiler; + final Register result_holder; + + address_compiler = new ComputationCompiler(compiler); + start_compiler = new ComputationCompiler(compiler); + end_compiler = new ComputationCompiler(compiler); + + n.get_collection().get_visited_by(address_compiler); + + if (address_compiler.has_init()) + { + result.add(address_compiler.get_init()); + } + + n.get_start_index().get_visited_by(start_compiler); + + if (start_compiler.has_init()) + { + result.add(start_compiler.get_init()); + } + + n.get_end_index().get_visited_by(end_compiler); + + if (end_compiler.has_init()) + { + result.add(end_compiler.get_init()); + } + + result_holder = + compiler.registers().reserve + ( + address_compiler.get_computation().get_type(), + result + ); + + result.add + ( + SubList.generate + ( + compiler.registers(), + compiler.assembler(), + start_compiler.get_computation(), + end_compiler.get_computation(), + address_compiler.get_address(), + result_holder.get_address() + ) + ); + + result.add + ( + new SetValue + ( + address_compiler.get_address(), + result_holder.get_value() + ) + ); + + compiler.registers().release(result_holder, result); + + address_compiler.release_registers(result); + start_compiler.release_registers(result); + end_compiler.release_registers(result); } @Override @@ -2432,10 +2576,6 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor ( compiler.registers(), compiler.assembler(), - new Size - ( - compiler.registers().get_rand_value_holder().get_address() - ), compiler.registers().get_rand_value_holder().get_address() ) ); @@ -2596,10 +2736,6 @@ implements tonkadur.fate.v1.lang.meta.InstructionVisitor ( compiler.registers(), compiler.assembler(), - new Size - ( - compiler.registers().get_rand_value_holder().get_address() - ), compiler.registers().get_rand_value_holder().get_address() ) ); diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/BinarySearch.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/BinarySearch.java index a8efd31..00b80e5 100644 --- a/src/core/src/tonkadur/wyrd/v1/compiler/util/BinarySearch.java +++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/BinarySearch.java @@ -277,8 +277,62 @@ public class BinarySearch final List sort_fun_extra_params ) { - final List result, while_body; + final List result; final Register bot, top, midval, cmp; + + result = new ArrayList(); + + bot = registers.reserve(Type.INT, result); + top = registers.reserve(Type.INT, result); + midval = registers.reserve(target.get_type(), result); + cmp = registers.reserve(Type.INT, result); + + result.add + ( + generate + ( + registers, + assembler, + sort_fun, + target, + collection_size, + collection, + result_was_found, + result_index, + sort_fun_extra_params, + bot, + top, + midval, + cmp + ) + ); + + registers.release(bot, result); + registers.release(top, result); + registers.release(midval, result); + registers.release(cmp, result); + + return assembler.merge(result); + } + + public static Instruction generate + ( + final RegisterManager registers, + final InstructionManager assembler, + final Computation sort_fun, + final Computation target, + final Computation collection_size, + final Address collection, + final Address result_was_found, + final Address result_index, + final List sort_fun_extra_params, + final Register bot, + final Register top, + final Register midval, + final Register cmp + ) + { + final List result, while_body; final Type element_type; final Computation value_of_result_index; @@ -287,11 +341,6 @@ public class BinarySearch element_type = target.get_type(); - bot = registers.reserve(Type.INT, result); - top = registers.reserve(Type.INT, result); - midval = registers.reserve(element_type, result); - cmp = registers.reserve(Type.INT, result); - value_of_result_index = new ValueOf(result_index); result.add(new SetValue(result_index, Constant.ZERO)); @@ -364,6 +413,9 @@ public class BinarySearch ) ); + sort_fun_extra_params.add(0, target); + sort_fun_extra_params.add(0, midval.get_value()); + while_body.add ( LambdaEvaluation.generate @@ -459,11 +511,6 @@ public class BinarySearch ) ); - registers.release(bot, result); - registers.release(top, result); - registers.release(midval, result); - registers.release(cmp, result); - return assembler.merge(result); } } diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/Clear.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/Clear.java index c5137c2..9c59cc6 100644 --- a/src/core/src/tonkadur/wyrd/v1/compiler/util/Clear.java +++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/Clear.java @@ -30,80 +30,29 @@ public class Clear private Clear () {} /* - * (Computation int collection_size) * (declare_variable global collection) * - * (declare_variable int .iterator) + * (declare_variable .clean_value) * - * (set .iterator collection_size) - * - * (while (> (var .iterator) 0) - * (set .iterator (- (val .iterator) 1)) - * (remove collection[.iterator]) - * ) - * FIXME: this can now be written as - * (remove collection) - * (initialize collection) + * (set collection .clean_value) */ public static Instruction generate ( final RegisterManager registers, final InstructionManager assembler, - final Computation collection_size, final Address collection ) { - final List result, while_body; - final Type element_type; - final Register iterator; + final List result; + final Register clean_value; result = new ArrayList(); - while_body = new ArrayList(); - - element_type = - ((MapType) collection.get_target_type()).get_member_type(); - - iterator = registers.reserve(Type.INT, result); - - /* (set .iterator collection_size) */ - result.add(new SetValue(iterator.get_address(), collection_size)); - - /* (set .iterator (- (val .iterator) 1)) */ - while_body.add - ( - new SetValue - ( - iterator.get_address(), - Operation.minus(iterator.get_value(), Constant.ONE) - ) - ); - /* (remove collection[.iterator]) */ - while_body.add - ( - new Remove - ( - new RelativeAddress - ( - collection, - new Cast(iterator.get_value(), Type.STRING), - element_type - ) - ) - ); + clean_value = registers.reserve(collection.get_target_type(), result); - result.add - ( - While.generate - ( - registers, - assembler, - Operation.greater_than(iterator.get_value(), Constant.ZERO), - assembler.merge(while_body) - ) - ); + result.add(new SetValue(collection, clean_value.get_value())); - registers.release(iterator, result); + registers.release(clean_value, result); return assembler.merge(result); } diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/Sort.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/Sort.java index 200f7ef..6a67389 100644 --- a/src/core/src/tonkadur/wyrd/v1/compiler/util/Sort.java +++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/Sort.java @@ -36,11 +36,134 @@ public class Sort final InstructionManager assembler, final Computation lambda_fun, final Address collection, - final Type collection_type, + final Address sorted_result_holder, final List extra_params ) { - /* TODO: Quicksort implementation in Wyrd. */ - return null; + final Type element_type; + final List result; + final List while_body; + final Register result_was_found, result_index, element_to_insert; + final Register bot, top, midval, cmp; + final Register collection_size, iterator; + + element_type = + ((MapType) collection.get_target_type()).get_member_type(); + + result = new ArrayList(); + while_body = new ArrayList(); + + collection_size = registers.reserve(Type.INT, result); + iterator = registers.reserve(Type.INT, result); + + result_was_found = registers.reserve(Type.BOOL, result); + result_index = registers.reserve(Type.INT, result); + element_to_insert = registers.reserve(element_type, result); + + bot = registers.reserve(Type.INT, result); + top = registers.reserve(Type.INT, result); + midval = registers.reserve(element_type, result); + cmp = registers.reserve(Type.INT, result); + + /**** INIT DONE *********************************************************/ + + result.add(new SetValue(iterator.get_address(), Constant.ZERO)); + result.add + ( + new SetValue(collection_size.get_address(), new Size(collection)) + ); + + while_body.add + ( + new SetValue + ( + element_to_insert.get_address(), + new ValueOf + ( + new RelativeAddress + ( + collection, + new Cast(iterator.get_value(), Type.STRING), + element_type + ) + ) + ) + ); + + while_body.add + ( + BinarySearch.generate + ( + registers, + assembler, + lambda_fun, + element_to_insert.get_value(), + iterator.get_value(), + sorted_result_holder, + result_was_found.get_address(), + result_index.get_address(), + extra_params, + bot, + top, + midval, + cmp + ) + ); + + while_body.add + ( + InsertAt.generate + ( + registers, + assembler, + result_index.get_address(), + element_to_insert.get_value(), + iterator.get_value(), + sorted_result_holder + ) + ); + + while_body.add + ( + new SetValue + ( + iterator.get_address(), + Operation.plus(iterator.get_value(), Constant.ONE) + ) + ); + + + result.add + ( + While.generate + ( + registers, + assembler, + Operation.less_than + ( + iterator.get_value(), + collection_size.get_value() + ), + assembler.merge(while_body) + ) + ); + + //result.add(new SetValue(collection, sorted_result.get_value())); + + /**** CLEANUP ***********************************************************/ + + registers.release(collection_size, result); + registers.release(iterator, result); + + registers.release(result_was_found, result); + registers.release(result_index, result); + registers.release(element_to_insert, result); + + registers.release(bot, result); + registers.release(top, result); + registers.release(midval, result); + registers.release(cmp, result); + + return assembler.merge(result); } } diff --git a/src/core/src/tonkadur/wyrd/v1/compiler/util/SubList.java b/src/core/src/tonkadur/wyrd/v1/compiler/util/SubList.java new file mode 100644 index 0000000..f5f7015 --- /dev/null +++ b/src/core/src/tonkadur/wyrd/v1/compiler/util/SubList.java @@ -0,0 +1,159 @@ +package tonkadur.wyrd.v1.compiler.util; + +import java.util.List; +import java.util.ArrayList; +import java.util.Collections; + +import tonkadur.wyrd.v1.lang.Register; + +import tonkadur.wyrd.v1.lang.type.Type; +import tonkadur.wyrd.v1.lang.type.MapType; + +import tonkadur.wyrd.v1.lang.meta.Instruction; +import tonkadur.wyrd.v1.lang.meta.Computation; + +import tonkadur.wyrd.v1.lang.computation.Cast; +import tonkadur.wyrd.v1.lang.computation.Constant; +import tonkadur.wyrd.v1.lang.computation.Operation; +import tonkadur.wyrd.v1.lang.computation.Address; +import tonkadur.wyrd.v1.lang.computation.RelativeAddress; +import tonkadur.wyrd.v1.lang.computation.ValueOf; +import tonkadur.wyrd.v1.lang.computation.Size; + +import tonkadur.wyrd.v1.lang.instruction.SetValue; +import tonkadur.wyrd.v1.lang.instruction.Initialize; + +import tonkadur.wyrd.v1.compiler.util.registers.RegisterManager; + +public class SubList +{ + /* Utility Class */ + private SubList () {} + + /* Uses Durstenfeld's shuffling algorithm */ + public static Instruction generate + ( + final RegisterManager registers, + final InstructionManager assembler, + final Computation start, + final Computation end, + final Address collection, + final Address result_holder + ) + { + final List result, while_body; + final Register iterator, collection_size, target_index; + final Address target_address; + final Type element_type; + + result = new ArrayList(); + while_body = new ArrayList(); + + target_index = registers.reserve(Type.INT, result); + iterator = registers.reserve(Type.INT, result); + collection_size = registers.reserve(Type.INT, result); + + element_type = ((MapType) collection.get_target_type()).get_member_type(); + + target_address = + new RelativeAddress + ( + result_holder, + new Cast(target_index.get_value(), Type.STRING), + element_type + ); + + result.add(new SetValue(target_index.get_address(), Constant.ZERO)); + + result.add(new SetValue(iterator.get_address(), start)); + result.add + ( + If.generate + ( + registers, + assembler, + Operation.less_than(iterator.get_value(), Constant.ZERO), + new SetValue(iterator.get_address(), Constant.ZERO) + ) + ); + + result.add + ( + new SetValue + ( + collection_size.get_address(), + Operation.minus(new Size(collection), Constant.ONE) + ) + ); + + result.add + ( + If.generate + ( + registers, + assembler, + Operation.greater_than(collection_size.get_value(), end), + new SetValue(collection_size.get_address(), end) + ) + ); + + + while_body.add(new Initialize(target_address, element_type)); + + while_body.add + ( + new SetValue + ( + target_address, + new ValueOf + ( + new RelativeAddress + ( + collection, + new Cast(iterator.get_value(), Type.STRING), + element_type + ) + ) + ) + ); + + while_body.add + ( + new SetValue + ( + iterator.get_address(), + Operation.plus(iterator.get_value(), Constant.ONE) + ) + ); + + while_body.add + ( + new SetValue + ( + target_index.get_address(), + Operation.plus(target_index.get_value(), Constant.ONE) + ) + ); + + result.add + ( + While.generate + ( + registers, + assembler, + Operation.less_equal_than + ( + iterator.get_value(), + collection_size.get_value() + ), + assembler.merge(while_body) + ) + ); + + registers.release(target_index, result); + registers.release(iterator, result); + registers.release(collection_size, result); + + return assembler.merge(result); + } +} -- cgit v1.2.3-70-g09d2