16
\$\begingroup\$

Write the shortest program or function that will determine if an input is a valid Go type.

Spec

This challenge will use the following simplified subset of Go types. For more information, see the Golang specification.

  • "Primitive" types:
    • bool
    • int,uint,float(32|64),complex(64|128),byte,rune
    • string
  • *T where T is any type
  • []T, a slice of T
  • [n]T, an array of T, and n is some positive non-zero integer
  • map[K]V, where K and V are any type
  • chan T (note the required whitespace)
  • struct{...}, where ... is a list of 0 or more semicolon-separated types (such as struct{int;float64;*struct{int;bool}}).
  • func(args)return, a function.
    • args is an optional comma-separated list of types.
    • return is optionally either a type, or a non-empty list of types in parentheses (a,b,c).

All truthy inputs have characters in the set [][a-z0-9(){},;* \t\n]. It is not guaranteed that an input that matches this regex is truthy.

Whitespace is allowed everywhere within the type, as long as it does not break apart keywords (struct, chan, map, func) or primitive types.

Test Cases

Truthy

bool
int
complex128
*int
*********int
[]string
[][]int
[ 10 ] [ ][123] * [567] [ ] [890 ] *rune
map[int]string
map[ []int ] [] string
map[map[map[int]string]map[bool]chan map[int]int]struct{int;string;bool}
struct{ }
struct{int; float64; *struct{int;bool} }
struct{struct{bool;struct{int; *[]chan complex128}; *float64}; map[string]string}
func()
func(int,uint,int,bool)string
func(int,uint,int,bool)(string,string,string)
func(func(int) int) func(func([]map[string]int) int) func(int) int
chan chan chan chan chan chan int
map[func() func() func()]func() func() func()
chan []string
func(int)(int)

Falsy

integer   // unknown primitive
float     // unknown primitive
imaginary // unknown primitive
int*      // * with no type
[]        // missing contained type
[]asdfghjkl // unknown type
[[]]int     // [] is invalid for array length
[-1]string  // negative ints are invalid for array length
[123.456]float64     // floats are invalid for array length
struct{int,float64}  // missing semicolon between member types
func(int)(int,string // missing closing paren
struct{func(int)map[int]string // missing closing brace
structfunc(int)map[int]string} // missing opening brace, unknown type
chanint      // missing required whitespace
chan[]string // missing space whitespace
func()()     // non-empty parenthesized return type only
[0]int       // positive non-zero integers only
func(int)(int)(iint) // dangling leftovers `(iint)` is not a type
\$\endgroup\$
10
  • 1
    \$\begingroup\$ @mousetail added a whitespace clarification \$\endgroup\$
    – bigyihsuan
    Aug 7, 2023 at 13:59
  • 1
    \$\begingroup\$ Would chan[]string be invalid because it doesn't have the required whitespace? \$\endgroup\$ Aug 7, 2023 at 21:48
  • 1
    \$\begingroup\$ @DanielSchepler ah, that's technically valid go, but let's keep the required whitespace for this challenge \$\endgroup\$
    – bigyihsuan
    Aug 7, 2023 at 21:55
  • 1
    \$\begingroup\$ @Arnauld func()() is not valid; the return type must either be empty, 1 type, or parenthesized comma-separated list of types. \$\endgroup\$
    – bigyihsuan
    Aug 8, 2023 at 12:57
  • 2
    \$\begingroup\$ This is probably invalidating some answers. Maybe it should be clarified as "or a non-empty list of types in parentheses". \$\endgroup\$
    – Arnauld
    Aug 8, 2023 at 13:02

6 Answers 6

14
\$\begingroup\$

Regex (PCRE), 241 bytes

^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|&\s*(?1)|\*\s*(?1)|\[\s*\d*\s*\]\s*(?1)|map\s*\[\s*(?1)\s*\]\s*(?1)|chan (?1)|struct\s*\{\s*(|((?1);\s*)*\s*(?1)\s*;?\s*)\}|func\(\s*(((?1),\s*)*(?1),?\s*)?\)\s*(\s*(?1)|\((?6)\))?)$

Fixed to handle func()() case

Try it on regex 101

\$\endgroup\$
8
\$\begingroup\$

BNFC + Haskell + Bash + coreutils, 175 + 96 = 271 bytes

bool"
int"
uint"
float32"
float64"
complex64"
complex128"
byte"
rune"
string"
*"T
[""]"T
["Integer"]"T
map""["T"]"T
chan "T
struct""{"[T]"}"
Q
QT
Q"("[T2]")"Z2","Z";";_.T2::=T

Compile with

sed 's/Q/func""("[T2]")"/g;s/Z/;separator T/g'|awk '{print"A"NR".T::=\""$0";"}'>g;bnfc -m g;make

Produces an executable named TestG which accepts input from stdin and exits with code 0 if the parse was successfull, 1 otherwise.

Possibly can be golfed more with a better use of sed and awk.


Script to test it:

cat truthy falsy | sed "s|//.*||" | xargs -d "\n" -I {} sh -c 'echo "{}" | ./TestG >/dev/null ; echo $? "{}"'
\$\endgroup\$
5
\$\begingroup\$

Raku, 205 193 bytes

*~~/^$(/:s \s*[bool|u?int|float[32|64]|complex[64|128]|byte|rune|string|\*<~~>|\[
\d* \]<~~>|map \[<~~>\]<~~>|chan\s+<~~>|struct \{ <~~>*%\; \}|func \(<~~>*%\,\)[<~~>|
\( <~~>*%\, \) ]?]\s*/)$/

Try it online!

This is an anonymous function that matches its argument against the giant regex following the leftmost ~~. That regex is of the form

/^$(/.../)$/

It interpolates the inner regex $(/.../) into the outer one. The outer regex requires that the overall match be anchored at the beginning and end of the string.

The inner regex matches a Go type. It is recursive, calling itself using the expression <~~>.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 250 bytes

Thanks to @Bbrk24 and @Value Ink for reporting bugs

Returns a Boolean value.

f=(s,t)=>s!=(s=s[R='replace'](T='T',t)[R](/chan |\[([1-9]\d*)?\]|map\[T\]/g,'*')[R](/\w \w/)[R](/ /,'')[R](/bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|\*T|struct{(T(;T)*)?}|func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/,T))?f(s,T):s==T

Try it online!

How?

At each iteration:

  • If we find a "T" and this is the first iteration, we replace it with "undefined" to invalidate the input.

  • We replace all occurrences of /chan /, /\[([1-9]\d*)?\]/ and /map\[T\]/ with "*". They all boil down to a valid prefix of another type.

  • If we find /\w \w/, we replace it with "undefined" to invalidate the input.

  • If we find a space somewhere else, we remove it.

  • We then look for the first valid type and replace it with "T":

    • primitive types: /bool|u?int|float(32|64)|complex(64|128)|byte|rune|string/
    • a type preceded with *: /\*T/
    • a struct type: /struct{(T(;T)*)?}/
    • a func type: /func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/

The func type is the trickiest one because we must not ignore a return statement that is not yet fully simplified. That's why we make sure that func(...) is followed by either a valid return statement or the end of the line or one of ,;}].

This process is repeated recursively until there's nothing more to replace. If the input string is valid, we should end up with a single "T".

Example 1

func(int,uint,int,bool)(string,string,string)
func(T,uint,int,bool)(string,string,string)
func(T,T,int,bool)(string,string,string)
func(T,T,T,bool)(string,string,string)
func(T,T,T,T)(string,string,string)
func(T,T,T,T)(T,string,string)
func(T,T,T,T)(T,T,string)
func(T,T,T,T)(T,T,T)
T

Example 2

map[map[map[int]string]map[bool]chan map[int]int]struct{int;string;bool}
map[map[map[T]string]map[bool]*map[int]int]struct{int;string;bool}
map[map[*T]map[bool]*map[int]int]struct{int;string;bool}
map[map[T]map[bool]*map[int]int]struct{int;string;bool}
map[*map[T]*map[int]int]struct{int;string;bool}
map[***map[T]int]struct{int;string;bool}
map[****T]struct{int;string;bool}
map[***T]struct{int;string;bool}
map[**T]struct{int;string;bool}
map[*T]struct{int;string;bool}
map[T]struct{int;string;bool}
*struct{T;string;bool}
*struct{T;T;bool}
*struct{T;T;T}
*T
T
\$\endgroup\$
8
  • \$\begingroup\$ This erroneously accepts [0]int. \$\endgroup\$
    – Bbrk24
    Aug 8, 2023 at 19:26
  • \$\begingroup\$ This accepts T, which I'm pretty sure isn't a valid type. \$\endgroup\$
    – Value Ink
    Aug 9, 2023 at 1:01
  • \$\begingroup\$ Also, stuff like i nt are also accepted. \$\endgroup\$
    – Value Ink
    Aug 9, 2023 at 1:07
  • \$\begingroup\$ @ValueInk Seems like I misinterpreted valid input as input in the last two rules of the challenge. :-/ \$\endgroup\$
    – Arnauld
    Aug 9, 2023 at 7:32
  • 1
    \$\begingroup\$ @l4m2 I think we'd need (?![*[ (\w]), which is the same length. \$\endgroup\$
    – Arnauld
    Aug 9, 2023 at 15:56
5
\$\begingroup\$

Go, 1279 1277 bytes

import(."regexp";."strings";U"unicode")
func P(s string)(string,bool){S,M,C,t,Z:=U.IsSpace,MustCompile,CutPrefix,0,0<1
T,X:=func(){for len(s)>0&&S(rune(s[0])){s=TrimSpace(s[1:])}},!Z
N:=func(){T();s=s[1:];T()}
T()
if len(s)<1{return s,X}
if k:=M(`^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string)($|[]});,\s])`).FindStringIndex(s);k!=nil&&k[0]<1{s=s[k[1]-1:];T();return s,Z}
if s[0]=='*'{return P(s[1:])}
if s[0]=='['{N();k:=M("^[1-9][0-9]+").FindStringIndex(s);if k!=nil{s=s[k[1]:];N();return P(s)};N();return P(s)}
if r,o:=C(s,"map");o{s=r;N();s,o=P(s);if!o{return s,X};if s[0]==']'{N()};return P(s)}
if r,o:=C(s,"chan");o{s=r;if!S(rune(s[0])){return s,X};T();return P(s)}
if r,o:=C(s,"struct");o{s=r;T();if s[0]!='{'{return s,X};N();for s[0]!='}'{s,o=P(s);if!o{return s,X};if s[0]=='}'{break};if s[0]!=';'{return s,X};N()};N();return s,Z}
if r,o:=C(s,"func");o{s=r;T();if s[0]!='('{return s,X};N();for s[0]!=')'{s,o=P(s);if!o{return s,X};if s[0]==')'{break};if s[0]!=','{return s,X};N()};N();if len(s)<1||M(`^[]});,\s]`).MatchString(s){return s,Z}
if s[0]=='('{N();for s[0]!=')'{s,o=P(s);if!o{return s,X};t++;if s[0]==')'{break};if s[0]!=','{return s,X};N()};if t<1{return s,X};N()}
if M(`^[iufcmbrsc*[]`).MatchString(s){return P(s)};return s,len(s)<1}
return s,X}

Attempt This Online!

An extremely straight-forward recursive solution. The parser makes use of the fact that Go types are mainly right-recursive, with an unambiguous prefix determining the parser state.

Most definitely can be golfed down by using a different algorithm, or making it iterative.

(Fun fact: the builtin go/parser package fails some test cases due to the recursive anonymous structs. It expects typenames or field names there. Though, in normal usage with gofmt, nested anonymous structs tends to not happen.)

  • -2 bytes: account for "dangling" leftovers, move true/false into variables (@The Thonnu)

Ungolfed

func parse(s string) (string, bool) {
    trimSpace := func() {
        for len(s) > 0 && unicode.IsSpace(rune(s[0])) {
            s = strings.TrimSpace(s[1:])
        }
    }
    nextChar := func() {
        trimSpace()
        s = s[1:]
        trimSpace()
    }
    trimSpace()
    // false on empty
    if len(s) == 0 {
        return s, false
    }
    // primitive types
    if k := regexp.MustCompile(`^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string)($|[]});,\s])`).FindStringIndex(s); k != nil && k[0] < 1 {
        s = s[k[1]-1:]
        trimSpace()
        return s, true
    }
    // pointer
    if s[0] == '*' {
        return parse(s[1:])
    }
    // slice/array
    if s[0] == '[' {
        nextChar()
        // look for a positive int
        k := regexp.MustCompile("^[1-9][0-9]+").FindStringIndex(s)
        if k != nil {
            s = s[k[1]:]
            nextChar()
            return parse(s)
        }
        nextChar()
        // contained type
        return parse(s)
    }
    // maps
    if rest, ok := strings.CutPrefix(s, "map"); ok {
        s = rest
        nextChar()
        // key
        s, ok = parse(s)
        if !ok {
            return s, false
        }
        // account for primitive
        if s[0] == ']' {
            nextChar()
        }
        // value
        return parse(s)

    }
    // chan
    if rest, ok := strings.CutPrefix(s, "chan"); ok {
        s = rest
        // required space
        if !unicode.IsSpace(rune(s[0])) {
            return s, false
        }
        trimSpace()
        // contained type
        return parse(s)
    }
    // struct
    if rest, ok := strings.CutPrefix(s, "struct"); ok {
        s = rest
        trimSpace()
        if s[0] != '{' {
            return s, false
        }
        nextChar()
        // semicolon-separated list of types
        for s[0] != '}' {
            // type
            s, ok = parse(s)
            if !ok {
                return s, false
            }
            // when 1 type, next is a '}'
            if s[0] == '}' {
                break
            }
            // semicolon
            if s[0] != ';' {
                return s, false
            }
            nextChar()
        }
        nextChar()
        return s, true
    }
    // func
    if rest, ok := strings.CutPrefix(s, "func"); ok {
        s = rest
        trimSpace()
        // comma-separated args
        if s[0] != '(' {
            return s, false
        }
        nextChar()
        for s[0] != ')' {
            // type
            s, ok = parse(s)
            if !ok {
                return s, false
            }
            // when 1 type, next is a ')'
            if s[0] == ')' {
                break
            }
            // comma
            if s[0] != ',' {
                return s, false
            }
            nextChar()
        }
        nextChar()
        // return type
        // can be nothing, 1 type, or parened comma-separated types
        // nothing
        if len(s) == 0 || regexp.MustCompile(`^[]});,\s]`).MatchString(s) {
            return s, true
        }
        // multiple types
        if s[0] == '(' {
            nextChar()
            typeCount := 0
            for s[0] != ')' {
                // type
                s, ok = parse(s)
                if !ok {
                    return s, false
                }
                typeCount++
                // when 1 type, next is a ')'
                if s[0] == ')' {
                    // nextChar()
                    break
                }
                // comma
                if s[0] != ',' {
                    return s, false
                }
                nextChar()
            }
            // no non-empty paren return type
            if typeCount == 0 {
                return s, false
            }
            nextChar()
        }
        // 1 type
        if regexp.MustCompile(`^[iufcmbrsc*[]`).MatchString(s) {
            return parse(s)
        }
        return s, len(s) == 0
    }
    return s, false
}
\$\endgroup\$
1
  • \$\begingroup\$ You could save 24 bytes by assigning 0>1 and 0<1 to variables and then using them in your return statements. Attempt This Online! \$\endgroup\$
    – The Thonnu
    Aug 9, 2023 at 10:29
2
\$\begingroup\$

Ruby -nl, 239 234 bytes

Uses the replacement strategy from Arnauld's Javascript answer as a full program using the -nl flag to loop the code over each line of input. Since Ruby doesn't let you inject undefined by leaving out arguments, the relevant replacements to force disqualification use X instead.

I had a slightly different regex strategy for solving the func issue but it turns out using the regexes from that answer was shorter.

sub'T',?X
1until$_==(gsub /\[([1-9]\d*)?\]|map\[T\]|chan\s/,?*;sub /\w\s\w/,?X;sub /\s/,'';sub /bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|\*T|struct{(T(;T)*)?}|func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/,?T)
p$_==?T

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Arnauld thanks. I had a substitution at the beginning at first but it was erroneously "optimized" out. \$\endgroup\$
    – Value Ink
    Aug 9, 2023 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.