added deque implementation and the relevant tests. It can be a useful…

… data structure for the pretty-printer implementation
vpisarev · Mar 8, 2021 · ad900b4 · ad900b4
1 parent 67aa796
commit ad900b4
Show file tree

Hide file tree

Showing 9 changed files with 183 additions and 9 deletions.
diff --git a/compiler/Ast.fx b/compiler/Ast.fx
@@ -1,4 +1,3 @@
-
 /*
     This file is a part of ficus language project.
     See ficus/LICENSE for the licensing terms

diff --git a/lib/Builtins.fx b/lib/Builtins.fx
@@ -650,7 +650,7 @@ fun print_repr(a: char) { print("'"); print(a); print("'") }
 fun print(a: 't [])
 {
     print("[")
-    for i <- 0:, x <- a {
+    for x@i <- a {
         if i > 0 {print(", ")}
         print_repr(x)
     }

diff --git a/lib/Deque.fx b/lib/Deque.fx
@@ -0,0 +1,113 @@
+/*
+    This file is a part of ficus language project.
+    See ficus/LICENSE for the licensing terms
+*/
+
+// very simple list-based deque
+
+exception NullQueueError
+
+// the name is very short, but it's convenient to reference this type as Deque.t
+@object type 't t = {head: 't list; tail: 't list}
+
+fun empty(_: 't t): bool
+{
+    | {head=[], tail=[]} => true
+    | _ => false
+}
+
+fun length(d: 't t) = d.head.length() + d.tail.length()
+fun rev(d: 't t) = t {head=d.tail, tail=d.head}
+
+// could improve performance in many cases but the worst one
+operator == (d1: 't t, d2: 't t) = list(d1) == list(d2)
+
+fun first(d: 't t): 't
+{
+    | {head=x :: _} => x
+    | {tail=_ :: _} => d.tail.last()
+    | _ => throw NullQueueError
+}
+
+fun last(d: 't t): 't
+{
+    | {tail=x :: _} => x
+    | {head=_ :: _} => d.head.last()
+    | _ => throw NullQueueError
+}
+
+fun pop_front(d: 't t): ('t, 't t)
+{
+    | {head=x :: rest, tail} => (x, t {head=rest, tail=tail})
+    | {tail=_ :: _} => pop_front(t {head=d.tail.rev(), tail=[]})
+    | _ => throw NullQueueError
+}
+
+fun push_front(d: 't t, x: 't): 't t = t {head=x::d.head, tail=d.tail}
+
+fun pop_back(d: 't t): ('t, 't t)
+{
+    | {head, tail=x :: rest} => (x, t {head=head, tail=rest})
+    | {head=_ :: _} => pop_back(t {head=[], tail=d.head.rev()})
+    | _ => throw NullQueueError
+}
+
+fun push_back(d: 't t, x: 't): 't t = t {head=d.head, tail=x::d.tail}
+
+fun from_list(l: 't list): 't t = t {head=l, tail=[]}
+fun list(d: 't t): 't list = d.head + d.tail.rev()
+fun array(d: 't t): 't list
+{
+    val h = [for x <- d.head {x}]
+    val t = [for x <- d.tail.rev() {x}]
+    [\h, \t]
+}
+
+fun map(d: 't t, f: 't -> 'rt): 'rt t
+{
+    val new_head = [: for x <- d.head {f(x)} :]
+    val new_tail = [: for x <- d.tail {f(x)} :]
+    t {head=new_head, tail=new_tail}
+}
+
+fun app(d: 't t, f: 't -> void, ~in_order:bool=true): void
+{
+    for x <- d.head {f(x)}
+    for x <- (if in_order {d.tail.rev()} else {d.tail}) {f(x)}
+}
+
+fun foldl(d: 't t, f: ('t, 'acc) -> 'acc, res0: 'acc): 'acc
+{
+    val fold res=res0 for x <- d.head {f(x, res)}
+    fold res=res for x <- d.tail.rev() {f(x, res)}
+}
+
+fun foldr(d: 't t, f: ('t, 'acc) -> 'acc, res0: 'acc): 'acc
+{
+    val fold res=res0 for x <- d.tail {f(x, res)}
+    fold res=res for x <- d.head.rev() {f(x, res)}
+}
+
+fun string(d: 't t)
+{
+    val len = length(d)
+    val elems = array(len, "")
+    for x@i <- d.head {elems[i] = repr(x)}
+    for x@i <- d.tail {elems[len-i-1] = repr(x)}
+    join_embrace("[", "]", ", ", elems)
+}
+
+fun print(d: 't t)
+{
+    print("[")
+    for x@i <- d.head {
+        if i > 0 {print(", ")}
+        print_repr(x)
+    }
+    val nonempty = (!d.head.empty() :> int)
+    for x@i <- d.tail.rev() {
+        if i+nonempty > 0 {print(", ")}
+        print_repr(x)
+    }
+    print("]")
+}
diff --git a/lib/String.fx b/lib/String.fx
@@ -55,7 +55,7 @@ fun cmp(s1: string, s2: string) = s1 <=> s2
         if( memcmp(s->data + i, part->data, sz2*sizeof(part->data[0])) == 0)
             break;
     }
-    return pos;
+    return i;
 }
 
 @pure @nothrow fun contains(s: string, c: char): bool = @ccode

diff --git a/lib/Sys.fx b/lib/Sys.fx
@@ -8,6 +8,7 @@ import File
 
 @ccode {
     #include <limits.h>
+    #include <stdlib.h>
     #include <stdio.h>
     #include <sys/stat.h>
     #include <unistd.h>
@@ -134,3 +135,14 @@ fun command(cmd: string): int = @ccode {
     }
     return fx_status;
 }
+
+fun getenv(name: string): string = @ccode {
+    fx_cstr_t name_;
+    int fx_status = fx_str2cstr(name, &name_, 0, 0);
+    if (fx_status >= 0) {
+        char* result = getenv(name_.data);
+        fx_free_cstr(&name_);
+        return fx_cstr2str(result, -1, fx_result);
+    }
+    return fx_status;
+}
diff --git a/runtime/ficus/impl/array.impl.h b/runtime/ficus/impl/array.impl.h
@@ -566,7 +566,7 @@ int fx_subarr(const fx_arr_t* arr, const int_* ranges, fx_arr_t* subarr)
 int fx_compose_arr( int ndims, size_t elemsize, fx_free_t free_elem, fx_copy_t copy_elem,
                     const int8_t* tags, const void** data, fx_arr_t* arr )
 {
-    int_ nrows = 0, ncols = 0, nrows_i = 0, ncols_i = 0;
+    int_ nrows = 0, ncols = -1, nrows_i = -1, ncols_i = 0;
     //printf("ndims=%d, copy_elem=%p, free_elem=%p\n", ndims, copy_elem, free_elem);
 
     if (ndims <= 0 || ndims > 2)
@@ -579,13 +579,14 @@ int fx_compose_arr( int ndims, size_t elemsize, fx_free_t free_elem, fx_copy_t c
     {
         int tag = tags[k];
         if (tag == 127 || tag < 0) {
-            if (ncols_i == 0 || (ncols != 0 && ncols_i != ncols)) {
+            if (ncols >= 0 && ncols_i != ncols) {
                 printf("throwing FX_EXN_SizeMismatchError\n");
                 FX_FAST_THROW_RET(FX_EXN_SizeMismatchError);
             }
             nrows += nrows_i;
             ncols = ncols_i;
-            nrows_i = ncols_i = 0;
+            nrows_i = -1;
+            ncols_i = 0;
             if (tag < 0)
                 break;
             continue;
@@ -613,7 +614,7 @@ int fx_compose_arr( int ndims, size_t elemsize, fx_free_t free_elem, fx_copy_t c
             FX_FAST_THROW_RET(FX_EXN_NoMatchError);
         }
 
-        if (nrows_i != 0 && nrows_i != nrows_k)
+        if (nrows_i >= 0 && nrows_i != nrows_k)
             FX_FAST_THROW_RET(FX_EXN_SizeMismatchError);
         nrows_i = nrows_k;
         ncols_i += ncols_k;

diff --git a/runtime/ficus/impl/string.impl.h b/runtime/ficus/impl/string.impl.h
@@ -184,10 +184,14 @@ static int_ fx_cstr2str_len(const char* src, int_ srclen)
 
 int fx_cstr2str(const char* src, int_ srclen, fx_str_t* str)
 {
+    int_ dstlen;
+    size_t total;
+    if(!src)
+        return fx_make_str(0, 0, str);
     if(srclen < 0)
         srclen = (int_)strlen(src);
-    int_ dstlen = fx_cstr2str_len(src, srclen);
-    size_t total = sizeof(*str->rc) + dstlen*sizeof(str->data[0]);
+    dstlen = fx_cstr2str_len(src, srclen);
+    total = sizeof(*str->rc) + dstlen*sizeof(str->data[0]);
     str->rc = (int_*)fx_malloc(total);
     if( !str->rc )
         FX_FAST_THROW_RET(FX_EXN_OutOfMemError);

diff --git a/test/test_all.fx b/test/test_all.fx
@@ -10,6 +10,7 @@ import test_mandelbrot
 import test_closure
 import test_re2
 import test_ds
+import test_deque
 import test_filename
 
 fun print_hdr()

diff --git a/test/test_deque.fx b/test/test_deque.fx
@@ -0,0 +1,44 @@
+/*
+    This file is a part of ficus language project.
+    See ficus/LICENSE for the licensing terms
+*/
+
+// tests for the deque type
+from UTest import *
+import Deque
+
+TEST("deque.simple", fun() {
+    val d = Deque.t {head=[: 1, 2, 3, 4, 5 :], tail=[: 7, 6 :]}
+    EXPECT_EQ(d.list(), [: 1, 2, 3, 4, 5, 6, 7 :])
+    EXPECT_EQ(d.first(), 1)
+    EXPECT_EQ(d.last(), 7)
+    val (x, d) = d.pop_back()
+    val (y, d) = d.pop_back()
+    val (z, d) = d.pop_back()
+    EXPECT_EQ(d.list(), [: 1, 2, 3, 4 :])
+    EXPECT_EQ(x, 7)
+    EXPECT_EQ(y, 6)
+    EXPECT_EQ(z, 5)
+    EXPECT_EQ(d.first(), 1)
+    EXPECT_EQ(d.last(), 4)
+    val d = d.push_back(100)
+    val d = d.push_back(200)
+    val d = d.push_back(300)
+    EXPECT_EQ(d.list(), [: 1, 2, 3, 4, 100, 200, 300 :])
+    val (x, d) = d.pop_front()
+    val (y, d) = d.pop_front()
+    EXPECT_EQ(d.list(), [: 3, 4, 100, 200, 300 :])
+    EXPECT_EQ(x, 1)
+    EXPECT_EQ(y, 2)
+    EXPECT_EQ(d.first(), 3)
+    EXPECT_EQ(d.last(), 300)
+    val d = d.push_front(-1)
+    val d = d.push_front(-2)
+    val d = d.push_front(-3)
+    EXPECT_EQ(d.list(), [: -3, -2, -1, 3, 4, 100, 200, 300 :])
+    EXPECT_EQ(d.length(), 8)
+    EXPECT_EQ(f"{d.rev()}", "[300, 200, 100, 4, 3, -1, -2, -3]")
+    EXPECT_EQ(f"{d.map(fun (i) {i*-3})}", "[9, 6, 3, -9, -12, -300, -600, -900]")
+    EXPECT_EQ(d.foldl(fun (i, s) {s*i}, 1), -432000000)
+    EXPECT_EQ(d.foldr(fun (i, s) {s+"."+string(i)}, "0"), "0.300.200.100.4.3.-1.-2.-3")
+})