Is it a valid Go type?

Question 1

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

Question 2

@mousetail added a whitespace clarification

Question 3

Would chan[]string be invalid because it doesn't have the required whitespace?

Question 4

@DanielSchepler ah, that's technically valid go, but let's keep the required whitespace for this challenge

Question 5

@Arnauld func()() is not valid; the return type must either be empty, 1 type, or parenthesized comma-separated list of types.

Question 6

This is probably invalidating some answers. Maybe it should be clarified as "or a non-empty list of types in parentheses".

Question 7

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

Question 8

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 $? "{}"'

Question 9

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 <~~>.

Question 10

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

Question 11

This erroneously accepts [0]int.

Question 12

This accepts T, which I'm pretty sure isn't a valid type.

Question 13

Also, stuff like i nt are also accepted.

Question 14

@ValueInk Seems like I misinterpreted valid input as input in the last two rules of the challenge. :-/

Question 15

@l4m2 I think we'd need (?![*[ (\w]), which is the same length.

Question 16

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
}

Question 17

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!

Question 18

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!

Question 19

@Arnauld thanks. I had a substitution at the beginning at first but it was erroneously "optimized" out.

mousetail 14.4k1 gold badge41 silver badges90 bronze badges · Accepted Answer · 2023-08-07 13:50:46Z

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

Stack Exchange Network

Is it a valid Go type?

Spec

Test Cases

Truthy

Falsy

6 Answers 6

Regex (PCRE), 241 bytes

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

Raku, (削除) 205 (削除ここまで) 193 bytes

JavaScript (ES6), 250 bytes

How?

Example 1

Example 2

Go, (削除) 1279 (削除ここまで) 1277 bytes

Ungolfed

Ruby `-nl`, (削除) 239 (削除ここまで) 234 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Hot Network Questions

Is it a valid Go type?

Spec

Test Cases

Truthy

Falsy

6 Answers 6

Regex (PCRE), 241 bytes

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

Raku, (削除) 205 (削除ここまで) 193 bytes

JavaScript (ES6), 250 bytes

How?

Example 1

Example 2

Go, (削除) 1279 (削除ここまで) 1277 bytes

Ungolfed

Ruby -nl, (削除) 239 (削除ここまで) 234 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Related

Hot Network Questions

Ruby `-nl`, (削除) 239 (削除ここまで) 234 bytes