Commits

Ross Light  committed f203368

Add ParseAcceptHeaders function

  • Participants
  • Parent commits 76a03e3

Comments (0)

Files changed (5)

+package webapp
+
+import (
+	"strconv"
+	"strings"
+)
+
+// An AcceptHeader represents a set of media ranges as sent in the Accept header
+// of an HTTP request.
+//
+// http://tools.ietf.org/html/rfc2616#section-14.1
+type AcceptHeader []MediaRange
+
+func (h AcceptHeader) String() string {
+	parts := make([]string, len(h))
+	for i := range h {
+		mr := &h[i]
+		parts[i] = mr.String()
+	}
+	return strings.Join(parts, ",")
+}
+
+// Quality returns the quality of a content type based on the media ranges in h.
+func (h AcceptHeader) Quality(contentType string, params map[string][]string) float64 {
+	results := make(mediaRangeMatches, 0, len(h))
+	for i := range h {
+		mr := &h[i]
+		if m := mr.match(contentType, params); m.Valid {
+			results = append(results, m)
+		}
+	}
+	if len(results) == 0 {
+		return 0.0
+	}
+
+	// find most specific
+	i := 0
+	for j := 1; j < results.Len(); j++ {
+		if results.Less(j, i) {
+			i = j
+		}
+	}
+	return results[i].MediaRange.Quality
+}
+
+// ParseAcceptHeader parses an Accept header of an HTTP request.  The media
+// ranges are unsorted.
+func ParseAcceptHeader(accept string) (AcceptHeader, error) {
+	ranges := make(AcceptHeader, 0)
+	p := httpParser{r: []rune(accept)}
+	p.space()
+	for !p.eof() {
+		if len(ranges) > 0 {
+			if !p.consume(",") {
+				return ranges, &parseError{Expected: "','", Found: p.peek(), EOF: p.eof()}
+			}
+			p.space()
+		}
+
+		r, err := parseMediaRange(&p)
+		if err != nil {
+			if r != "" {
+				ranges = append(ranges, MediaRange{Range: r, Quality: 1.0})
+			}
+			return ranges, err
+		}
+		quality, params, err := parseAcceptParams(&p)
+		ranges = append(ranges, MediaRange{Range: r, Quality: quality, Params: params})
+		if err != nil {
+			return ranges, err
+		}
+
+	}
+	return ranges, nil
+}
+
+func parseMediaRange(p *httpParser) (string, error) {
+	const sep = "/"
+	type_ := p.token()
+	if len(type_) == 0 {
+		return "", &parseError{Expected: "token", Found: p.peek(), EOF: p.eof()}
+	}
+	if !p.consume(sep) {
+		return string(type_), &parseError{Expected: "'" + sep + "'", In: "media-range", Found: p.peek(), EOF: p.eof()}
+	}
+	subtype := p.token()
+	if len(subtype) == 0 {
+		return string(type_[:len(type_)+len(sep)]), &parseError{Expected: "subtype", In: "media-range", Found: p.peek(), EOF: p.eof()}
+	}
+	return string(type_[:len(type_)+len(sep)+len(subtype)]), nil
+}
+
+func parseAcceptParams(p *httpParser) (float64, map[string][]string, error) {
+	const qualityParam = "q"
+
+	quality, params := 1.0, make(map[string][]string)
+	p.space()
+	for p.consume(";") {
+		p.space()
+		key := string(p.token())
+		p.space()
+		if !p.consume("=") {
+			return quality, params, &parseError{Expected: "'='", In: "accept-params", Found: p.peek(), EOF: p.eof()}
+		}
+		p.space()
+		var value string
+		if s, err := p.quotedString(); err != nil {
+			return quality, params, err
+		} else if s != nil {
+			value = string(s)
+		} else {
+			value = string(p.token())
+		}
+		p.space()
+
+		if key == qualityParam {
+			// check for qvalue
+			if q, err := strconv.ParseFloat(value, 64); err != nil {
+				return quality, params, &qvalueError{value, err}
+			} else if q <= 0 || q > 1 {
+				return quality, params, &qvalueError{value, errQValueRange}
+			} else {
+				quality = q
+			}
+		} else {
+			params[key] = append(params[key], value)
+		}
+	}
+	return quality, params, nil
+}
+
+// A MediaRange represents a set of MIME types as sent in the Accept header of
+// an HTTP request.
+type MediaRange struct {
+	Range   string
+	Quality float64
+	Params  map[string][]string
+}
+
+// Match reports whether the range applies to a content type.
+func (mr *MediaRange) Match(contentType string, params map[string][]string) bool {
+	return mr.match(contentType, params).Valid
+}
+
+type mediaRangeMatch struct {
+	MediaRange *MediaRange
+	Valid      bool
+	Type       int
+	Subtype    int
+	Params     int
+}
+
+type mediaRangeMatches []mediaRangeMatch
+
+func (m mediaRangeMatches) Len() int      { return len(m) }
+func (m mediaRangeMatches) Swap(i, j int) { m[i], m[j] = m[j], m[i] }
+func (m mediaRangeMatches) Less(i, j int) bool {
+	mi, mj := &m[i], &m[j]
+	switch {
+	case !mi.Valid && !mj.Valid:
+		return false
+	case !mi.Valid && mj.Valid:
+		return false
+	case mi.Valid && !mj.Valid:
+		return true
+	}
+	if mi.Params != mj.Params {
+		return mi.Params > mj.Params
+	}
+	if mi.Subtype != mj.Subtype {
+		return mi.Subtype > mj.Subtype
+	}
+	return mi.Type > mj.Type
+}
+
+func (mr *MediaRange) match(contentType string, params map[string][]string) mediaRangeMatch {
+	mrType, mrSubtype := splitContentType(mr.Range)
+	ctType, ctSubtype := splitContentType(contentType)
+	match := mediaRangeMatch{MediaRange: mr}
+
+	if !(mrSubtype == "*" || mrSubtype == ctSubtype) || !(mrType == "*" || mrType == ctType) {
+		return match
+	}
+	if mrType != "*" {
+		match.Type++
+	}
+	if mrSubtype != "*" {
+		match.Subtype++
+	}
+
+	if len(mr.Params) == 0 {
+		match.Valid = true
+		return match
+	} else if len(params) != len(mr.Params) {
+		return match
+	}
+	for k, v1 := range params {
+		v2, ok := mr.Params[k]
+		if !ok {
+			return match
+		}
+		if len(v1) != len(v2) {
+			return match
+		}
+		for i := range v1 {
+			if v1[i] != v2[i] {
+				return match
+			}
+		}
+	}
+	match.Params++
+	match.Valid = true
+	return match
+}
+
+func splitContentType(s string) (string, string) {
+	i := strings.IndexRune(s, '/')
+	if i == -1 {
+		return "", ""
+	}
+	return s[:i], s[i+1:]
+}
+
+func (mr *MediaRange) String() string {
+	parts := make([]string, 0, len(mr.Params)+1)
+	parts = append(parts, mr.Range)
+	if mr.Quality != 1.0 {
+		parts = append(parts, "q="+strconv.FormatFloat(mr.Quality, 'f', 3, 64))
+	}
+	for k, vs := range mr.Params {
+		for _, v := range vs {
+			parts = append(parts, k+"="+quoteHTTP(v))
+		}
+	}
+	return strings.Join(parts, ";")
+}

File accept_test.go

+package webapp
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestAcceptHeader(t *testing.T) {
+	type QualityCheck struct {
+		Type    string
+		Params  map[string][]string
+		Quality float64
+	}
+
+	tests := []struct {
+		Accept string
+		Checks []QualityCheck
+	}{
+		{
+			"text/*;q=0.3, text/html;q=0.7, text/html;level=1, text/html;level=2;q=0.4, */*;q=0.5",
+			[]QualityCheck{
+				{"text/html", map[string][]string{"level": {"1"}}, 1.0},
+				{"text/html", map[string][]string{"level": {"1"}}, 1.0},
+				{"text/html", map[string][]string{}, 0.7},
+				{"text/plain", map[string][]string{}, 0.3},
+				{"image/jpeg", map[string][]string{}, 0.5},
+				{"text/html", map[string][]string{"level": {"2"}}, 0.4},
+				{"text/html", map[string][]string{"level": {"3"}}, 0.7},
+			},
+		},
+	}
+	for _, test := range tests {
+		h, err := ParseAcceptHeader(test.Accept)
+		if err != nil {
+			t.Errorf("ParseAcceptHeader(%q) error: %v", test.Accept, err)
+			continue
+		}
+		for _, check := range test.Checks {
+			q := h.Quality(check.Type, check.Params)
+			if q != check.Quality {
+				t.Errorf("Accept: %s\n%v = %.3f, want %.3f", test.Accept, &MediaRange{Range: check.Type, Quality: 1.0, Params: check.Params}, q, check.Quality)
+			}
+		}
+	}
+}
+
+func TestParseAcceptHeader(t *testing.T) {
+	tests := []struct {
+		Accept      string
+		Expect      AcceptHeader
+		ExpectError bool
+	}{
+		{"", AcceptHeader{}, false},
+		{"foo/)bar", AcceptHeader{MediaRange{"foo/", 1.0, nil}}, true},
+		{
+			`text/html; q=1`,
+			AcceptHeader{
+				{"text/html", 1.0, map[string][]string{}},
+			},
+			false,
+		},
+		{
+			`text/html; q=0.001`,
+			AcceptHeader{
+				{"text/html", 0.001, map[string][]string{}},
+			},
+			false,
+		},
+		{
+			`text/html; q=0`,
+			AcceptHeader{
+				{"text/html", 1.0, map[string][]string{}},
+			},
+			true,
+		},
+		{
+			`text/html; q=1.5`,
+			AcceptHeader{
+				{"text/html", 1.0, map[string][]string{}},
+			},
+			true,
+		},
+		{
+			"audio/*; q=0.2, audio/basic",
+			AcceptHeader{
+				{"audio/*", 0.2, map[string][]string{}},
+				{"audio/basic", 1.0, map[string][]string{}},
+			},
+			false,
+		},
+		{
+			`text/html; charset="utf-8"`,
+			AcceptHeader{
+				{"text/html", 1.0, map[string][]string{"charset": {"utf-8"}}},
+			},
+			false,
+		},
+		{
+			`text/html; charset="utf-8"; charset="utf 8"; charset="utf\"8"`,
+			AcceptHeader{
+				{"text/html", 1.0, map[string][]string{"charset": {"utf-8", "utf 8", "utf\"8"}}},
+			},
+			false,
+		},
+		{
+			"text/plain; q=0.5, text/html, text/x-dvi; q=0.8, text/x-c",
+			AcceptHeader{
+				{"text/plain", 0.5, map[string][]string{}},
+				{"text/html", 1.0, map[string][]string{}},
+				{"text/x-dvi", 0.8, map[string][]string{}},
+				{"text/x-c", 1.0, map[string][]string{}},
+			},
+			false,
+		},
+		{
+			"text/*, text/html, text/html;level=1, */*",
+			AcceptHeader{
+				{"text/*", 1.0, map[string][]string{}},
+				{"text/html", 1.0, map[string][]string{}},
+				{"text/html", 1.0, map[string][]string{"level": {"1"}}},
+				{"*/*", 1.0, map[string][]string{}},
+			},
+			false,
+		},
+		{
+			"text/*;q=0.3, text/html;q=0.7, text/html;level=1, text/html;level=2;q=0.4, */*;q=0.5",
+			AcceptHeader{
+				{"text/*", 0.3, map[string][]string{}},
+				{"text/html", 0.7, map[string][]string{}},
+				{"text/html", 1.0, map[string][]string{"level": {"1"}}},
+				{"text/html", 0.4, map[string][]string{"level": {"2"}}},
+				{"*/*", 0.5, map[string][]string{}},
+			},
+			false,
+		},
+	}
+
+	for _, test := range tests {
+		mr, err := ParseAcceptHeader(test.Accept)
+		if err != nil && !test.ExpectError {
+			t.Errorf("ParseAcceptHeader(%q) error: %v", test.Accept, err)
+		} else if err == nil && test.ExpectError {
+			t.Errorf("ParseAcceptHeader(%q) error = nil", test.Accept)
+		}
+		if !reflect.DeepEqual(mr, test.Expect) {
+			t.Errorf("ParseAcceptHeader(%q) = %v; want %v", test.Accept, mr, test.Expect)
+		}
+	}
+}
+
+func TestMediaRange_match(t *testing.T) {
+	tests := []struct {
+		Range  string
+		Params map[string][]string
+
+		ContentType   string
+		ContentParams map[string][]string
+
+		Match mediaRangeMatch
+	}{
+		{
+			"text/html", map[string][]string{},
+			"text/html", map[string][]string{},
+			mediaRangeMatch{nil, true, 1, 1, 0},
+		},
+		{
+			"text/html", map[string][]string{},
+			"text/plain", map[string][]string{},
+			mediaRangeMatch{nil, false, 0, 0, 0},
+		},
+		{
+			"text/*", map[string][]string{},
+			"image/jpeg", map[string][]string{},
+			mediaRangeMatch{nil, false, 0, 0, 0},
+		},
+		{
+			"text/*", map[string][]string{},
+			"text/plain", map[string][]string{},
+			mediaRangeMatch{nil, true, 1, 0, 0},
+		},
+		{
+			"*/*", map[string][]string{},
+			"image/jpeg", map[string][]string{},
+			mediaRangeMatch{nil, true, 0, 0, 0},
+		},
+		{
+			"text/html", map[string][]string{"level": {"1"}},
+			"text/html", map[string][]string{"level": {"1"}},
+			mediaRangeMatch{nil, true, 1, 1, 1},
+		},
+		{
+			"text/html", map[string][]string{"level": {"1"}},
+			"text/html", map[string][]string{"level": {"2"}},
+			mediaRangeMatch{nil, false, 1, 1, 0},
+		},
+		{
+			"text/html", map[string][]string{"level": {"1"}},
+			"text/html", map[string][]string{},
+			mediaRangeMatch{nil, false, 1, 1, 0},
+		},
+		{
+			"text/html", map[string][]string{},
+			"text/html", map[string][]string{"level": {"1"}},
+			mediaRangeMatch{nil, true, 1, 1, 0},
+		},
+		{
+			"text/html", map[string][]string{"level": {"1"}},
+			"text/html", map[string][]string{"level": {"1"}, "foo": {"bar"}},
+			mediaRangeMatch{nil, false, 1, 1, 0},
+		},
+		{
+			"text/html", map[string][]string{"level": {"1"}, "foo": {"bar"}},
+			"text/html", map[string][]string{"level": {"1"}},
+			mediaRangeMatch{nil, false, 1, 1, 0},
+		},
+	}
+	for _, test := range tests {
+		mr := MediaRange{Range: test.Range, Params: test.Params}
+		test.Match.MediaRange = &mr
+		match := mr.match(test.ContentType, test.ContentParams)
+		if match != test.Match {
+			t.Errorf("{Range:%v Params:%v}.match(%v, %v) = %v; want %v", test.Range, test.Params, test.ContentType, test.ContentParams, match, test.Match)
+		}
+	}
+}
+
+func TestMediaRangeMatchLess(t *testing.T) {
+	tests := []struct {
+		A, B mediaRangeMatch
+		Less bool
+	}{
+		{mediaRangeMatch{}, mediaRangeMatch{}, false},
+		{mediaRangeMatch{Valid: true}, mediaRangeMatch{}, true},
+		{mediaRangeMatch{}, mediaRangeMatch{Valid: true}, false},
+		{mediaRangeMatch{nil, true, 0, 0, 0}, mediaRangeMatch{nil, true, 0, 0, 0}, false},
+		{mediaRangeMatch{nil, true, 1, 0, 0}, mediaRangeMatch{nil, true, 0, 0, 0}, true},
+		{mediaRangeMatch{nil, true, 0, 0, 0}, mediaRangeMatch{nil, true, 1, 0, 0}, false},
+		{mediaRangeMatch{nil, true, 1, 1, 0}, mediaRangeMatch{nil, true, 0, 0, 0}, true},
+		{mediaRangeMatch{nil, true, 0, 0, 0}, mediaRangeMatch{nil, true, 1, 1, 0}, false},
+		{mediaRangeMatch{nil, true, 0, 0, 1}, mediaRangeMatch{nil, true, 0, 0, 0}, true},
+		{mediaRangeMatch{nil, true, 0, 0, 0}, mediaRangeMatch{nil, true, 0, 0, 1}, false},
+		{mediaRangeMatch{nil, true, 1, 1, 1}, mediaRangeMatch{nil, true, 0, 0, 0}, true},
+		{mediaRangeMatch{nil, true, 0, 0, 0}, mediaRangeMatch{nil, true, 1, 1, 1}, false},
+	}
+
+	matches := make(mediaRangeMatches, 2)
+	for _, test := range tests {
+		matches[0] = test.A
+		matches[1] = test.B
+		result := matches.Less(0, 1)
+		if result != test.Less {
+			t.Errorf("%v < %v = %t; want %t", test.A, test.B, result, test.Less)
+		}
+	}
+}
+package webapp
+
+import (
+	"errors"
+	"strconv"
+)
+
+// A MultiError is returned by operations that have errors on particular elements.
+// This is functionally identical to appengine.MultiError.
+type MultiError []error
+
+func (e MultiError) Error() string {
+	msg, n := "", 0
+	for _, err := range e {
+		if err != nil {
+			if n == 0 {
+				msg = err.Error()
+			}
+			n++
+		}
+	}
+	switch n {
+	case 0:
+		return "0 errors"
+	case 1:
+		return msg
+	case 2:
+		return msg + " (and 1 other error)"
+	}
+
+	s := []byte(msg)
+	s = append(s, []byte(" (and ")...)
+	s = strconv.AppendInt(s, int64(n-1), 10)
+	s = append(s, []byte(" other errors)")...)
+	return string(s)
+}
+
+type parseError struct {
+	Expected string
+	In       string
+	Found    rune
+	EOF      bool
+}
+
+func (e *parseError) Error() string {
+	var s []byte
+	s = append(s, []byte("expected ")...)
+	s = append(s, []byte(e.Expected)...)
+	if e.In != "" {
+		s = append(s, []byte(" in ")...)
+		s = append(s, []byte(e.In)...)
+	}
+	s = append(s, []byte(", found ")...)
+	if !e.EOF {
+		s = strconv.AppendQuoteRune(s, e.Found)
+	} else {
+		s = append(s, []byte("EOF")...)
+	}
+	return string(s)
+}
+
+type qvalueError struct {
+	QValue string
+	Err    error
+}
+
+func (e *qvalueError) Error() string {
+	return "qvalue " + strconv.Quote(e.QValue) + ": " + e.Err.Error()
+}
+
+var errQValueRange = errors.New("must be >0.0 and <=1.0")
 
 import (
 	"encoding/json"
-	"fmt"
+	"io"
 	"net/http"
 	"strconv"
 	"strings"
 	return json.NewEncoder(w).Encode(v)
 }
 
-// A MultiError is returned by operations that have errors on particular elements.
-// This is functionally identical to appengine.MultiError.
-type MultiError []error
-
-func (e MultiError) Error() string {
-	msg, n := "", 0
-	for _, err := range e {
-		if err != nil {
-			if n == 0 {
-				msg = err.Error()
-			}
-			n++
+func quoteHTTP(s string) string {
+	if s == "" {
+		return `""`
+	}
+	isToken := true
+	for _, r := range s {
+		if !isTokenChar(r) {
+			isToken = false
+			break
 		}
 	}
-	switch n {
-	case 0:
-		return "0 errors"
-	case 1:
-		return msg
-	case 2:
-		return msg + " (and 1 other error)"
+	if isToken {
+		return s
 	}
-	return fmt.Sprintf("%s (and %d other errors)", msg, n-1)
+	sb := make([]byte, 0, len(s)+2)
+	sb = append(sb, '"')
+	for i := 0; i < len(s); i++ {
+		switch c := s[i]; c {
+		case '\\', '"':
+			sb = append(sb, '\\', c)
+		default:
+			sb = append(sb, c)
+		}
+	}
+	sb = append(sb, '"')
+	return string(sb)
 }
+
+// httpParser is a rune-based parser that has rules for common HTTP productions.
+type httpParser struct {
+	r []rune
+}
+
+func (p *httpParser) eof() bool {
+	return len(p.r) == 0
+}
+
+func (p *httpParser) peek() rune {
+	if p.eof() {
+		return 0
+	}
+	return p.r[0]
+}
+
+func (p *httpParser) consume(literal string) bool {
+	if len(p.r) < len(literal) {
+		return false
+	}
+	if len(literal) == 1 {
+		// common case
+		ok := p.r[0] == rune(literal[0])
+		if ok {
+			p.r = p.r[1:]
+		}
+		return ok
+	}
+
+	i := 0
+	for _, c := range literal {
+		if p.r[i] != c {
+			return false
+		}
+		i++
+	}
+	p.r = p.r[i:]
+	return true
+}
+
+func (p *httpParser) run(f func(rune) bool) []rune {
+	var i int
+	for i = 0; i < len(p.r); i++ {
+		if !f(p.r[i]) {
+			break
+		}
+	}
+	run := p.r[:i]
+	p.r = p.r[i:]
+	return run
+}
+
+const tokenChars = "!#$%&'*+-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ^_`abcdefghijklmnopqrstuvwxyz|~"
+
+func isTokenChar(r rune) bool {
+	return strings.IndexRune(tokenChars, r) != -1
+}
+
+func (p *httpParser) token() []rune {
+	var i int
+	for i = 0; i < len(p.r); i++ {
+		if !isTokenChar(p.r[i]) {
+			break
+		}
+	}
+	run := p.r[:i]
+	p.r = p.r[i:]
+	return run
+}
+
+func (p *httpParser) quotedString() ([]rune, error) {
+	if len(p.r) == 0 || p.r[0] != '"' {
+		return nil, nil
+	}
+	s := make([]rune, 0, len(p.r)-1)
+	var i int
+	for i = 1; i < len(p.r); i++ {
+		if ru := p.r[i]; ru == '"' {
+			p.r = p.r[i+1:]
+			return s, nil
+		} else if ru == '\\' {
+			i++
+			if i < len(p.r) {
+				s = append(s, p.r[i])
+			} else {
+				p.r = p.r[i:]
+				return s, io.ErrUnexpectedEOF
+			}
+		} else {
+			s = append(s, ru)
+		}
+	}
+	p.r = p.r[i:]
+	return s, io.ErrUnexpectedEOF
+}
+
+func (p *httpParser) space() []rune {
+	var i int
+	for i = 0; i < len(p.r); i++ {
+		if ru := p.r[i]; ru != ' ' && ru != '\t' {
+			break
+		}
+	}
+	run := p.r[:i]
+	p.r = p.r[i:]
+	return run
+}

File http_test.go

+package webapp
+
+import (
+	"testing"
+)
+
+func TestTokenChars(t *testing.T) {
+	for c := rune(0); c < 0x10ffff; c++ {
+		expected := c < 127 && c > 31 &&
+			c != '(' && c != ')' && c != '<' && c != '>' && c != '@' &&
+			c != ',' && c != ';' && c != ':' && c != '\\' && c != '"' &&
+			c != '/' && c != '[' && c != ']' && c != '?' && c != '=' &&
+			c != '{' && c != '}' && c != ' ' && c != '\t'
+		if found := isTokenChar(c); found != expected {
+			t.Errorf("%q found=%t, want %t", c, found, expected)
+		}
+	}
+}
+
+func TestQuoteHTTP(t *testing.T) {
+	tests := []struct {
+		Value  string
+		Quoted string
+	}{
+		{"", `""`},
+		{"a", "a"},
+		{"abc", "abc"},
+		{"Hello, World!", `"Hello, World!"`},
+		{`C:\`, `"C:\\"`},
+		{`"foo"`, `"\"foo\""`},
+	}
+
+	for _, test := range tests {
+		q := quoteHTTP(test.Value)
+		if q != test.Quoted {
+			t.Errorf("quoteHTTP(%q) = %q; want %q", test.Value, q, test.Quoted)
+		}
+	}
+}