Support keyword-only function parameters (#143)

Following a hitherto undocumented feature of Skylark-in-Java,
which in turn follows Python3,
a function declaration may now include optional parameters
after the *args parameter:

```
def f(a, b, c=1, *args, d=2, **kwargs)
```
The parameter d is a "keyword-only" parameter as it can
never by assigned from a positional parameter; all positional
arguments surplus to a, b, and c are put in a tuple and
assigned to args.

To declare a non-variadic function with keyword-only arguments,
the *args parameter is replaced by just *:

```
    def f(a, b, c=1, *, d=2, **kwargs)
```
The * parameter is not a real parameter; it just serves as a
separator between the parameter that may be specified positionally
and the keyword-only ones.

Spec proposal at bazelbuild/starlark#23

Fixes #61

13 files changed, 166 insertions, 43 deletions

diff --git a/doc/spec.md b/doc/spec.md
index 81a8a3e..3894bbe 100644
--- a/doc/spec.md
+++ b/doc/spec.md
@@ -2328,6 +2328,7 @@ LambdaExpr = 'lambda' [Parameters] ':' Test .
 Parameters = Parameter {',' Parameter} .
 Parameter  = identifier
            | identifier '=' Test
+           | '*'
            | '*' identifier
            | '**' identifier
            .
@@ -2515,7 +2516,7 @@ the parameter list (which is enclosed in parentheses), a colon, and
 then an indented block of statements which form the body of the function.
 
 The parameter list is a comma-separated list whose elements are of
-four kinds.  First come zero or more required parameters, which are
+several kinds.  First come zero or more required parameters, which are
 simple identifiers; all calls must provide an argument value for these parameters.
 
 The required parameters are followed by zero or more optional
@@ -2526,11 +2527,24 @@ provide an argument value for it.
 The required parameters are optionally followed by a single parameter
 name preceded by a `*`.  This is the called the _varargs_ parameter,
 and it accumulates surplus positional arguments specified by a call.
+It is conventionally named `*args`.
+
+The varargs parameter may be followed by zero or more optional
+parameters, again of the form `name=expression`, but these optional parameters
+differ from earlier ones in that they are "keyword-only":
+a call must provide their values as keyword arguments,
+not positional ones.
+
+A non-variadic function may also declare keyword-only parameters,
+by using a bare `*` in place of the `*args` parameter.
+This form does not declare a parameter but marks the boundary
+between the earlier parameters and the keyword-only parameters.
+This form must be followed by at least one optional parameter.
 
 Finally, there may be an optional parameter name preceded by `**`.
 This is called the _keyword arguments_ parameter, and accumulates in a
 dictionary any surplus `name=value` arguments that do not match a
-prior parameter.
+prior parameter. It is conventionally named `**kwargs`.
 
 Here are some example parameter lists:
 
@@ -2541,6 +2555,7 @@ def f(a, b, c=1): pass
 def f(a, b, c=1, *args): pass
 def f(a, b, c=1, *args, **kwargs): pass
 def f(**kwargs): pass
+def f(a, b, c=1, *, d=1): pass
 ```
 
 Execution of a `def` statement creates a new function object.  The
diff --git a/internal/compile/compile.go b/internal/compile/compile.go
index 6b43fbe..b313a5c 100644
--- a/internal/compile/compile.go
+++ b/internal/compile/compile.go
@@ -37,7 +37,7 @@ import (
 const debug = false // TODO(adonovan): use a bitmap of options; and regexp to match files
 
 // Increment this to force recompilation of saved bytecode files.
-const Version = 5
+const Version = 6
 
 type Opcode uint8
 
@@ -305,10 +305,11 @@ type Funcode struct {
 	Doc                   string          // docstring of this function
 	Code                  []byte          // the byte code
 	pclinetab             []uint16        // mapping from pc to linenum
-	Locals                []Ident         // for error messages and tracing
+	Locals                []Ident         // locals, parameters first
 	Freevars              []Ident         // for tracing
 	MaxStack              int
 	NumParams             int
+	NumKwonlyParams       int
 	HasVarargs, HasKwargs bool
 }
 
@@ -1705,7 +1706,14 @@ func (fcomp *fcomp) function(pos syntax.Position, name string, f *syntax.Functio
 		fmt.Fprintf(os.Stderr, "resuming %s @ %s\n", fcomp.fn.Name, fcomp.pos)
 	}
 
-	funcode.NumParams = len(f.Params)
+	// def f(a, *, b=1) has only 2 parameters.
+	numParams := len(f.Params)
+	if f.NumKwonlyParams > 0 && !f.HasVarargs {
+		numParams--
+	}
+
+	funcode.NumParams = numParams
+	funcode.NumKwonlyParams = f.NumKwonlyParams
 	funcode.HasVarargs = f.HasVarargs
 	funcode.HasKwargs = f.HasKwargs
 	fcomp.emit1(MAKEFUNC, fcomp.pcomp.functionIndex(funcode))
diff --git a/internal/compile/serial.go b/internal/compile/serial.go
index f6cf807..6056ea7 100644
--- a/internal/compile/serial.go
+++ b/internal/compile/serial.go
@@ -39,6 +39,7 @@ package compile
 //	freevar		[]Ident
 //	maxstack	varint
 //	numparams	varint
+//	numkwonlyparams	varint
 //	hasvarargs	varint (0 or 1)
 //	haskwargs	varint (0 or 1)
 //
@@ -185,6 +186,7 @@ func (e *encoder) function(fn *Funcode) {
 	e.idents(fn.Freevars)
 	e.int(fn.MaxStack)
 	e.int(fn.NumParams)
+	e.int(fn.NumKwonlyParams)
 	e.int(b2i(fn.HasVarargs))
 	e.int(b2i(fn.HasKwargs))
 }
@@ -350,20 +352,22 @@ func (d *decoder) function() *Funcode {
 	freevars := d.idents()
 	maxStack := d.int()
 	numParams := d.int()
+	numKwonlyParams := d.int()
 	hasVarargs := d.int() != 0
 	hasKwargs := d.int() != 0
 	return &Funcode{
 		// Prog is filled in later.
-		Pos:        id.Pos,
-		Name:       id.Name,
-		Doc:        doc,
-		Code:       code,
-		pclinetab:  pclinetab,
-		Locals:     locals,
-		Freevars:   freevars,
-		MaxStack:   maxStack,
-		NumParams:  numParams,
-		HasVarargs: hasVarargs,
-		HasKwargs:  hasKwargs,
+		Pos:             id.Pos,
+		Name:            id.Name,
+		Doc:             doc,
+		Code:            code,
+		pclinetab:       pclinetab,
+		Locals:          locals,
+		Freevars:        freevars,
+		MaxStack:        maxStack,
+		NumParams:       numParams,
+		NumKwonlyParams: numKwonlyParams,
+		HasVarargs:      hasVarargs,
+		HasKwargs:       hasKwargs,
 	}
 }
diff --git a/resolve/resolve.go b/resolve/resolve.go
index 0bc9ac0..51325bd 100644
--- a/resolve/resolve.go
+++ b/resolve/resolve.go
@@ -765,7 +765,9 @@ func (r *resolver) function(pos syntax.Position, name string, function *syntax.F
 	r.push(b)
 
 	var seenOptional bool
-	var star, starStar *syntax.Ident // *args, **kwargs
+	var star *syntax.UnaryExpr // * or *args param
+	var starStar *syntax.Ident // **kwargs ident
+	var numKwonlyParams int
 	for _, param := range function.Params {
 		switch param := param.(type) {
 		case *syntax.Ident:
@@ -786,7 +788,7 @@ func (r *resolver) function(pos syntax.Position, name string, function *syntax.F
 			if starStar != nil {
 				r.errorf(param.OpPos, "optional parameter may not follow **%s", starStar.Name)
 			} else if star != nil {
-				r.errorf(param.OpPos, "optional parameter may not follow *%s", star.Name)
+				numKwonlyParams++
 			}
 			if id := param.X.(*syntax.Ident); r.bind(id) {
 				r.errorf(param.OpPos, "duplicate parameter: %s", id.Name)
@@ -794,30 +796,48 @@ func (r *resolver) function(pos syntax.Position, name string, function *syntax.F
 			seenOptional = true
 
 		case *syntax.UnaryExpr:
-			// *args or **kwargs
-			id := param.X.(*syntax.Ident)
+			// * or *args or **kwargs
 			if param.Op == syntax.STAR {
 				if starStar != nil {
-					r.errorf(param.OpPos, "*%s parameter may not follow **%s", id.Name, starStar.Name)
+					r.errorf(param.OpPos, "* parameter may not follow **%s", starStar.Name)
 				} else if star != nil {
 					r.errorf(param.OpPos, "multiple * parameters not allowed")
 				} else {
-					star = id
+					star = param
 				}
 			} else {
 				if starStar != nil {
 					r.errorf(param.OpPos, "multiple ** parameters not allowed")
-				} else {
-					starStar = id
 				}
+				starStar = param.X.(*syntax.Ident)
 			}
+		}
+	}
+
+	// Bind the *args and **kwargs parameters at the end,
+	// so that regular parameters a/b/c are contiguous and
+	// there is no hole for the "*":
+	//   def f(a, b, *args, c=0, **kwargs)
+	//   def f(a, b, *,     c=0, **kwargs)
+	if star != nil {
+		if id, _ := star.X.(*syntax.Ident); id != nil {
+			// *args
 			if r.bind(id) {
 				r.errorf(id.NamePos, "duplicate parameter: %s", id.Name)
 			}
+			function.HasVarargs = true
+		} else if numKwonlyParams == 0 {
+			r.errorf(star.OpPos, "bare * must be followed by optional parameters")
 		}
 	}
-	function.HasVarargs = star != nil
-	function.HasKwargs = starStar != nil
+	if starStar != nil {
+		if r.bind(starStar) {
+			r.errorf(starStar.NamePos, "duplicate parameter: %s", starStar.Name)
+		}
+		function.HasKwargs = true
+	}
+
+	function.NumKwonlyParams = numKwonlyParams
 	r.stmts(function.Body)
 
 	// Resolve all uses of this function's local vars,
diff --git a/resolve/testdata/resolve.star b/resolve/testdata/resolve.star
index df96711..6d03ade 100644
--- a/resolve/testdata/resolve.star
+++ b/resolve/testdata/resolve.star
@@ -224,7 +224,7 @@ def f(x=1, y): pass ### `required parameter may not follow optional`
 def f(**kwargs, x): ### `parameter may not follow \*\*kwargs`
   pass
 
-def g(**kwargs, *args): ### `\*args parameter may not follow \*\*kwargs`
+def g(**kwargs, *args): ### `\* parameter may not follow \*\*kwargs`
   pass
 
 def h(**kwargs1, **kwargs2): ### `multiple \*\* parameters not allowed`
@@ -239,7 +239,27 @@ def f(*args, x): ### `required parameter may not follow \* parameter`
 def g(*args1, *args2): ### `multiple \* parameters not allowed`
   pass
 
-def h(*args, a=1, **kwargs): ### `optional parameter may not follow \*args`
+def h(*, ### `bare \* must be followed by optional parameters`
+      *): ### `multiple \* parameters not allowed`
+  pass
+
+def i(*args, *): ### `multiple \* parameters not allowed`
+  pass
+
+def j(*,      ### `bare \* must be followed by optional parameters`
+      *args): ### `multiple \* parameters not allowed`
+  pass
+
+def k(*, **kwargs): ### `bare \* must be followed by optional parameters`
+  pass
+
+def l(*): ### `bare \* must be followed by optional parameters`
+  pass
+
+def m(*args, a=1, **kwargs): # ok
+  pass
+
+def n(*, a=1, **kwargs): # ok
   pass
 
 ---
diff --git a/starlark/eval.go b/starlark/eval.go
index a144052..c03d71a 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -1147,7 +1147,7 @@ func setArgs(locals []Value, fn *Function, args Tuple, kwargs []Tuple) error {
 
 	// Too many positional args?
 	n := len(args)
-	maxpos := nparams
+	maxpos := nparams - fn.NumKwonlyParams()
 	if len(args) > maxpos {
 		if !fn.HasVarargs() {
 			return fmt.Errorf("function %s takes %s %d positional argument%s (%d given)",
@@ -1201,7 +1201,7 @@ func setArgs(locals []Value, fn *Function, args Tuple, kwargs []Tuple) error {
 	}
 
 	// default values
-	if n < nparams {
+	if n < nparams || fn.NumKwonlyParams() > 0 {
 		m := nparams - len(fn.defaults) // first default
 
 		// report errors for missing non-optional arguments
diff --git a/starlark/eval_test.go b/starlark/eval_test.go
index abb0dd9..044f0ac 100644
--- a/starlark/eval_test.go
+++ b/starlark/eval_test.go
@@ -268,6 +268,10 @@ def e(**kwargs):
 	return kwargs
 def f(a, b=42, *args, **kwargs):
 	return a, b, args, kwargs
+def g(a, b=42, *args, c=123, **kwargs):
+	return a, b, args, c, kwargs
+def h(a, b=42, *, c=123, **kwargs):
+	return a, b, c, kwargs
 `
 
 	thread := new(starlark.Thread)
@@ -320,6 +324,30 @@ def f(a, b=42, *args, **kwargs):
 		{`f(0, b=1, c=2)`, `(0, 1, (), {"c": 2})`},
 		{`f(0, 1, x=2, *[3, 4], y=5, **dict(z=6))`, // github.com/google/skylark/issues/135
 			`(0, 1, (3, 4), {"x": 2, "y": 5, "z": 6})`},
+
+		{`g()`, `function g takes at least 1 positional argument (0 given)`},
+		{`g(0)`, `(0, 42, (), 123, {})`},
+		{`g(0, 1)`, `(0, 1, (), 123, {})`},
+		{`g(0, 1, 2)`, `(0, 1, (2,), 123, {})`},
+		{`g(0, 1, 2, 3)`, `(0, 1, (2, 3), 123, {})`},
+		{`g(a=0)`, `(0, 42, (), 123, {})`},
+		{`g(0, b=1)`, `(0, 1, (), 123, {})`},
+		{`g(0, a=1)`, `function g got multiple values for keyword argument "a"`},
+		{`g(0, b=1, c=2, d=3)`, `(0, 1, (), 2, {"d": 3})`},
+		{`g(0, 1, x=2, *[3, 4], y=5, **dict(z=6))`,
+			`(0, 1, (3, 4), 123, {"x": 2, "y": 5, "z": 6})`},
+
+		{`h()`, `function h takes at least 1 positional argument (0 given)`},
+		{`h(0)`, `(0, 42, 123, {})`},
+		{`h(0)`, `(0, 42, 123, {})`},
+		{`h(0, 1)`, `(0, 1, 123, {})`},
+		{`h(0, 1, 2)`, `function h takes at most 2 positional arguments (3 given)`},
+		{`h(a=0)`, `(0, 42, 123, {})`},
+		{`h(0, b=1)`, `(0, 1, 123, {})`},
+		{`h(0, a=1)`, `function h got multiple values for keyword argument "a"`},
+		{`h(0, b=1, c=2)`, `(0, 1, 2, {})`},
+		{`h(0, b=1, d=2)`, `(0, 1, 123, {"d": 2})`},
+		{`h(0, b=1, c=2, d=3)`, `(0, 1, 2, {"d": 3})`},
 	} {
 		var got string
 		if v, err := starlark.Eval(thread, "<expr>", test.src, globals); err != nil {
diff --git a/starlark/value.go b/starlark/value.go
index b5a4aed..f697442 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -595,9 +595,12 @@ func (fn *Function) Globals() StringDict {
 
 func (fn *Function) Position() syntax.Position { return fn.funcode.Pos }
 func (fn *Function) NumParams() int            { return fn.funcode.NumParams }
+func (fn *Function) NumKwonlyParams() int      { return fn.funcode.NumKwonlyParams }
 
 // Param returns the name and position of the ith parameter,
 // where 0 <= i < NumParams().
+// The *args and **kwargs parameters are at the end
+// even if there were optional parameters after *args.
 func (fn *Function) Param(i int) (string, syntax.Position) {
 	id := fn.funcode.Locals[i]
 	return id.Name, id.Pos
diff --git a/syntax/grammar.txt b/syntax/grammar.txt
index c3ad159..0a1988b 100644
--- a/syntax/grammar.txt
+++ b/syntax/grammar.txt
@@ -10,7 +10,7 @@ DefStmt = 'def' identifier '(' [Parameters [',']] ')' ':' Suite .
 
 Parameters = Parameter {',' Parameter}.
 
-Parameter = identifier | identifier '=' Test | '*' identifier | '**' identifier .
+Parameter = identifier | identifier '=' Test | '*' | '*' identifier | '**' identifier .
 
 IfStmt = 'if' Test ':' Suite {'elif' Test ':' Suite} ['else' ':' Suite] .
 
diff --git a/syntax/parse.go b/syntax/parse.go
index 0764ab2..65a1852 100644
--- a/syntax/parse.go
+++ b/syntax/parse.go
@@ -423,15 +423,17 @@ func (p *parser) consume(t Token) Position {
 //
 // param = IDENT
 //       | IDENT EQ test
+//       | STAR
 //       | STAR IDENT
 //       | STARSTAR IDENT
 //
 // parseParams parses a parameter list.  The resulting expressions are of the form:
 //
-//      *Ident
-//      *Binary{Op: EQ, X: *Ident, Y: Expr}
-//      *Unary{Op: STAR, X: *Ident}
-//      *Unary{Op: STARSTAR, X: *Ident}
+//      *Ident                                          x
+//      *Binary{Op: EQ, X: *Ident, Y: Expr}             x=y
+//      *Unary{Op: STAR}                                *
+//      *Unary{Op: STAR, X: *Ident}                     *args
+//      *Unary{Op: STARSTAR, X: *Ident}                 **kwargs
 func (p *parser) parseParams() []Expr {
 	var params []Expr
 	stars := false
@@ -447,16 +449,19 @@ func (p *parser) parseParams() []Expr {
 			break
 		}
 
-		// *args or **kwargs
+		// * or *args or **kwargs
 		if p.tok == STAR || p.tok == STARSTAR {
 			stars = true
 			op := p.tok
 			pos := p.nextToken()
-			id := p.parseIdent()
+			var x Expr
+			if op == STARSTAR || p.tok == IDENT {
+				x = p.parseIdent()
+			}
 			params = append(params, &UnaryExpr{
 				OpPos: pos,
 				Op:    op,
-				X:     id,
+				X:     x,
 			})
 			continue
 		}
diff --git a/syntax/parse_test.go b/syntax/parse_test.go
index 309e249..eaf4040 100644
--- a/syntax/parse_test.go
+++ b/syntax/parse_test.go
@@ -104,6 +104,10 @@ func TestExprParseTrees(t *testing.T) {
 			`(CallExpr Fn=f Args=(1 (BinaryExpr X=x Op== Y=y)))`},
 		{`f(*args, **kwargs)`,
 			`(CallExpr Fn=f Args=((UnaryExpr Op=* X=args) (UnaryExpr Op=** X=kwargs)))`},
+		{`lambda *args, *, x=1, **kwargs: 0`,
+			`(LambdaExpr Function=(Function Params=((UnaryExpr Op=* X=args) (UnaryExpr Op=*) (BinaryExpr X=x Op== Y=1) (UnaryExpr Op=** X=kwargs)) Body=((ReturnStmt Result=0))))`},
+		{`lambda *, a, *b: 0`,
+			`(LambdaExpr Function=(Function Params=((UnaryExpr Op=*) a (UnaryExpr Op=* X=b)) Body=((ReturnStmt Result=0))))`},
 		{`a if b else c`,
 			`(CondExpr Cond=b True=a False=c)`},
 		{`a and not b`,
@@ -394,6 +398,11 @@ func writeTree(out *bytes.Buffer, x reflect.Value) {
 				if f.IsNil() {
 					continue
 				}
+			case reflect.Int:
+				if f.Int() != 0 {
+					fmt.Fprintf(out, " %s=%d", name, f.Int())
+				}
+				continue
 			case reflect.Bool:
 				if f.Bool() {
 					fmt.Fprintf(out, " %s", name)
diff --git a/syntax/syntax.go b/syntax/syntax.go
index c4f64c0..22fe397 100644
--- a/syntax/syntax.go
+++ b/syntax/syntax.go
@@ -122,14 +122,15 @@ func (x *AssignStmt) Span() (start, end Position) {
 type Function struct {
 	commentsRef
 	StartPos Position // position of DEF or LAMBDA token
-	Params   []Expr   // param = ident | ident=expr | *ident | **ident
+	Params   []Expr   // param = ident | ident=expr | * | *ident | **ident
 	Body     []Stmt
 
 	// set by resolver:
-	HasVarargs bool     // whether params includes *args (convenience)
-	HasKwargs  bool     // whether params includes **kwargs (convenience)
-	Locals     []*Ident // this function's local variables, parameters first
-	FreeVars   []*Ident // enclosing local variables to capture in closure
+	HasVarargs      bool     // whether params includes *args (convenience)
+	HasKwargs       bool     // whether params includes **kwargs (convenience)
+	NumKwonlyParams int      // number of keyword-only optional parameters
+	Locals          []*Ident // this function's local variables, parameters first
+	FreeVars        []*Ident // enclosing local variables to capture in closure
 }
 
 func (x *Function) Span() (start, end Position) {
diff --git a/syntax/testdata/errors.star b/syntax/testdata/errors.star
index d2d09b2..c8235bc 100644
--- a/syntax/testdata/errors.star
+++ b/syntax/testdata/errors.star
@@ -28,6 +28,16 @@ def f(**kwargs, ): ### `got '\)', want parameter`
 ---
 
 # Parameters are validated later.
+def f(**kwargs, *args, *, b=1, a, **kwargs, *args, *, b=1, a):
+  pass
+
+---
+
+def f(a, *-b, c): # ### `got '-', want ','`
+  pass
+
+---
+
 def f(**kwargs, *args, b=1, a, **kwargs, *args, b=1, a):
   pass