From 5ca3693a7b5d65fd5aa67c737e7a60b457db2281 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Fri, 5 Apr 2019 15:22:37 -0700 Subject: compiler: better shared test for sys:switch. * share/txr/stdlib/compiler.tl (compiler comp-switch): The shared test here is both inaccurate and O(n^2). It tests that all the remaining branches of the code are tails of the first branch. However, this is not strict enough: we need to also test that the tails are in their order of appearance. We can do that in O(n) time. --- share/txr/stdlib/compiler.tl | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/share/txr/stdlib/compiler.tl b/share/txr/stdlib/compiler.tl index cbd2b6ee..3d906866 100644 --- a/share/txr/stdlib/compiler.tl +++ b/share/txr/stdlib/compiler.tl @@ -524,7 +524,12 @@ (mac-param-bind form (op idx-form cases-vec) form (let* ((ncases (len cases-vec)) (cs (and (plusp ncases) (conses [cases-vec 0]))) - (shared (and cs (all [cases-vec 1..:] (op memq @1 cs)))) + (shared (and cs + (let ((c cs) + (d (cdr (list-vec cases-vec)))) + (whilet ((m (if d (memq (pop d) c)))) + (set c m)) + (null d)))) (cases (if shared (let ((cs-nil ^(,*cs nil))) [mapcar ldiff cs-nil (cdr cs-nil)]) -- cgit v1.2.3