Re: How case statement is tested?

[Peng Yu]

On Wed, Mar 11, 2020 at 12:55 PM Eric Blake <eblake@redhat.com> wrote:
>
> On 3/11/20 11:47 AM, Peng Yu wrote:
> > Hi,
> >
> > I am wondering if there is any optimization in testing the conditions
> > in a case statement?
>
> What optimization(s) do you have in mind?

When the patterns in a case statement are const strings, it can be
implemented faster using a hash function like the following instead of
a typical if-else-if-else chain.

Would this feature be considered to be added into bash so that it can
handle the case statement more efficiently for this special case
(probably the most common case)? Thanks.

#include "stdio.h"

#define LS 5863588
#define CD 5863276
#define MKDIR 210720772860
#define PWD 193502992

const unsigned long hash(const char *str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + c;
    return hash;
}

int main(int argc, char *argv[]) {
    char *p_command = argv[1];
    switch(hash(p_command)) {
    case LS:
        printf("Running ls...\n");
        break;
    case CD:
        printf("Running cd...\n");
        break;
    case MKDIR:
        printf("Running mkdir...\n");
        break;
    case PWD:
        printf("Running pwd...\n");
        break;
    default:
        printf("[ERROR] '%s' is not a valid command.\n", p_command);
    }
}

> Bash has to perform
> glob-matching for each potential pattern.  Anything you can do to speed
> up globbing (such as recognizing when a glob can only match a literal
> string) might help, but since side effects are possible in specifying a
> glob pattern, there's very little you can do to parallelize things by
> testing multiple glob patterns at once.  For example:
>
> x= y=
> case 1 in
>    $((x=0)) ) ;;
>    $((y=1)) ) ;;
>    $((x=1)) ) ;;
> esac
> echo "$x.$y"
>
> must output 0.1, which means you cannot precompute the pattern for the
> third clause bounded by $((x=1)) (which is really the glob '1' plus the
> side-effect of setting x=1) until after you have already ascertained
> whether the first two clauses did not match.
>
> >
> > Or it is just like a series of if-statement and each condition must be
> > tested until one condition is true? Thanks.
>
> This, with the additional complication that you can skip conditions
> (with ';&') or evaluate more than one condition as true (with ';;&').
> See if you can figure out what this will output prior to running it:
>
> for var in a b c d; do
>    case $var in
>      a) echo 1 ;;&
>      b) echo 2 ;&
>      c) echo 3 ;;
>      *) echo 4
>    esac
> done
>
> --
> Eric Blake, Principal Software Engineer
> Red Hat, Inc.           +1-919-301-3226
> Virtualization:  qemu.org | libvirt.org
>


-- 
Regards,
Peng