// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

//go:generate go run makeisprint.go -output isprint.go

package strconv

import (
	
)

const (
	lowerhex = "0123456789abcdef"
	upperhex = "0123456789ABCDEF"
)

// contains reports whether the string contains the byte c.
func contains( string,  byte) bool {
	return index(, ) != -1
}

func quoteWith( string,  byte, ,  bool) string {
	return string(appendQuotedWith(make([]byte, 0, 3*len()/2), , , , ))
}

func quoteRuneWith( rune,  byte, ,  bool) string {
	return string(appendQuotedRuneWith(nil, , , , ))
}

func appendQuotedWith( []byte,  string,  byte, ,  bool) []byte {
	// Often called with big strings, so preallocate. If there's quoting,
	// this is conservative but still helps a lot.
	if cap()-len() < len() {
		 := make([]byte, len(), len()+1+len()+1)
		copy(, )
		 = 
	}
	 = append(, )
	for  := 0; len() > 0;  = [:] {
		 := rune([0])
		 = 1
		if  >= utf8.RuneSelf {
			,  = utf8.DecodeRuneInString()
		}
		if  == 1 &&  == utf8.RuneError {
			 = append(, `\x`...)
			 = append(, lowerhex[[0]>>4])
			 = append(, lowerhex[[0]&0xF])
			continue
		}
		 = appendEscapedRune(, , , , )
	}
	 = append(, )
	return 
}

func appendQuotedRuneWith( []byte,  rune,  byte, ,  bool) []byte {
	 = append(, )
	if !utf8.ValidRune() {
		 = utf8.RuneError
	}
	 = appendEscapedRune(, , , , )
	 = append(, )
	return 
}

func appendEscapedRune( []byte,  rune,  byte, ,  bool) []byte {
	if  == rune() ||  == '\\' { // always backslashed
		 = append(, '\\')
		 = append(, byte())
		return 
	}
	if  {
		if  < utf8.RuneSelf && IsPrint() {
			 = append(, byte())
			return 
		}
	} else if IsPrint() ||  && isInGraphicList() {
		return utf8.AppendRune(, )
	}
	switch  {
	case '\a':
		 = append(, `\a`...)
	case '\b':
		 = append(, `\b`...)
	case '\f':
		 = append(, `\f`...)
	case '\n':
		 = append(, `\n`...)
	case '\r':
		 = append(, `\r`...)
	case '\t':
		 = append(, `\t`...)
	case '\v':
		 = append(, `\v`...)
	default:
		switch {
		case  < ' ' ||  == 0x7f:
			 = append(, `\x`...)
			 = append(, lowerhex[byte()>>4])
			 = append(, lowerhex[byte()&0xF])
		case !utf8.ValidRune():
			 = 0xFFFD
			fallthrough
		case  < 0x10000:
			 = append(, `\u`...)
			for  := 12;  >= 0;  -= 4 {
				 = append(, lowerhex[>>uint()&0xF])
			}
		default:
			 = append(, `\U`...)
			for  := 28;  >= 0;  -= 4 {
				 = append(, lowerhex[>>uint()&0xF])
			}
		}
	}
	return 
}

// Quote returns a double-quoted Go string literal representing s. The
// returned string uses Go escape sequences (\t, \n, \xFF, \u0100) for
// control characters and non-printable characters as defined by
// IsPrint.
func ( string) string {
	return quoteWith(, '"', false, false)
}

// AppendQuote appends a double-quoted Go string literal representing s,
// as generated by Quote, to dst and returns the extended buffer.
func ( []byte,  string) []byte {
	return appendQuotedWith(, , '"', false, false)
}

// QuoteToASCII returns a double-quoted Go string literal representing s.
// The returned string uses Go escape sequences (\t, \n, \xFF, \u0100) for
// non-ASCII characters and non-printable characters as defined by IsPrint.
func ( string) string {
	return quoteWith(, '"', true, false)
}

// AppendQuoteToASCII appends a double-quoted Go string literal representing s,
// as generated by QuoteToASCII, to dst and returns the extended buffer.
func ( []byte,  string) []byte {
	return appendQuotedWith(, , '"', true, false)
}

// QuoteToGraphic returns a double-quoted Go string literal representing s.
// The returned string leaves Unicode graphic characters, as defined by
// IsGraphic, unchanged and uses Go escape sequences (\t, \n, \xFF, \u0100)
// for non-graphic characters.
func ( string) string {
	return quoteWith(, '"', false, true)
}

// AppendQuoteToGraphic appends a double-quoted Go string literal representing s,
// as generated by QuoteToGraphic, to dst and returns the extended buffer.
func ( []byte,  string) []byte {
	return appendQuotedWith(, , '"', false, true)
}

// QuoteRune returns a single-quoted Go character literal representing the
// rune. The returned string uses Go escape sequences (\t, \n, \xFF, \u0100)
// for control characters and non-printable characters as defined by IsPrint.
// If r is not a valid Unicode code point, it is interpreted as the Unicode
// replacement character U+FFFD.
func ( rune) string {
	return quoteRuneWith(, '\'', false, false)
}

// AppendQuoteRune appends a single-quoted Go character literal representing the rune,
// as generated by QuoteRune, to dst and returns the extended buffer.
func ( []byte,  rune) []byte {
	return appendQuotedRuneWith(, , '\'', false, false)
}

// QuoteRuneToASCII returns a single-quoted Go character literal representing
// the rune. The returned string uses Go escape sequences (\t, \n, \xFF,
// \u0100) for non-ASCII characters and non-printable characters as defined
// by IsPrint.
// If r is not a valid Unicode code point, it is interpreted as the Unicode
// replacement character U+FFFD.
func ( rune) string {
	return quoteRuneWith(, '\'', true, false)
}

// AppendQuoteRuneToASCII appends a single-quoted Go character literal representing the rune,
// as generated by QuoteRuneToASCII, to dst and returns the extended buffer.
func ( []byte,  rune) []byte {
	return appendQuotedRuneWith(, , '\'', true, false)
}

// QuoteRuneToGraphic returns a single-quoted Go character literal representing
// the rune. If the rune is not a Unicode graphic character,
// as defined by IsGraphic, the returned string will use a Go escape sequence
// (\t, \n, \xFF, \u0100).
// If r is not a valid Unicode code point, it is interpreted as the Unicode
// replacement character U+FFFD.
func ( rune) string {
	return quoteRuneWith(, '\'', false, true)
}

// AppendQuoteRuneToGraphic appends a single-quoted Go character literal representing the rune,
// as generated by QuoteRuneToGraphic, to dst and returns the extended buffer.
func ( []byte,  rune) []byte {
	return appendQuotedRuneWith(, , '\'', false, true)
}

// CanBackquote reports whether the string s can be represented
// unchanged as a single-line backquoted string without control
// characters other than tab.
func ( string) bool {
	for len() > 0 {
		,  := utf8.DecodeRuneInString()
		 = [:]
		if  > 1 {
			if  == '\ufeff' {
				return false // BOMs are invisible and should not be quoted.
			}
			continue // All other multibyte runes are correctly encoded and assumed printable.
		}
		if  == utf8.RuneError {
			return false
		}
		if ( < ' ' &&  != '\t') ||  == '`' ||  == '\u007F' {
			return false
		}
	}
	return true
}

func unhex( byte) ( rune,  bool) {
	 := rune()
	switch {
	case '0' <=  &&  <= '9':
		return  - '0', true
	case 'a' <=  &&  <= 'f':
		return  - 'a' + 10, true
	case 'A' <=  &&  <= 'F':
		return  - 'A' + 10, true
	}
	return
}

// UnquoteChar decodes the first character or byte in the escaped string
// or character literal represented by the string s.
// It returns four values:
//
//  1. value, the decoded Unicode code point or byte value;
//  2. multibyte, a boolean indicating whether the decoded character requires a multibyte UTF-8 representation;
//  3. tail, the remainder of the string after the character; and
//  4. an error that will be nil if the character is syntactically valid.
//
// The second argument, quote, specifies the type of literal being parsed
// and therefore which escaped quote character is permitted.
// If set to a single quote, it permits the sequence \' and disallows unescaped '.
// If set to a double quote, it permits \" and disallows unescaped ".
// If set to zero, it does not permit either escape and allows both quote characters to appear unescaped.
func ( string,  byte) ( rune,  bool,  string,  error) {
	// easy cases
	if len() == 0 {
		 = ErrSyntax
		return
	}
	switch  := [0]; {
	case  ==  && ( == '\'' ||  == '"'):
		 = ErrSyntax
		return
	case  >= utf8.RuneSelf:
		,  := utf8.DecodeRuneInString()
		return , true, [:], nil
	case  != '\\':
		return rune([0]), false, [1:], nil
	}

	// hard case: c is backslash
	if len() <= 1 {
		 = ErrSyntax
		return
	}
	 := [1]
	 = [2:]

	switch  {
	case 'a':
		 = '\a'
	case 'b':
		 = '\b'
	case 'f':
		 = '\f'
	case 'n':
		 = '\n'
	case 'r':
		 = '\r'
	case 't':
		 = '\t'
	case 'v':
		 = '\v'
	case 'x', 'u', 'U':
		 := 0
		switch  {
		case 'x':
			 = 2
		case 'u':
			 = 4
		case 'U':
			 = 8
		}
		var  rune
		if len() <  {
			 = ErrSyntax
			return
		}
		for  := 0;  < ; ++ {
			,  := unhex([])
			if ! {
				 = ErrSyntax
				return
			}
			 = <<4 | 
		}
		 = [:]
		if  == 'x' {
			// single-byte string, possibly not UTF-8
			 = 
			break
		}
		if !utf8.ValidRune() {
			 = ErrSyntax
			return
		}
		 = 
		 = true
	case '0', '1', '2', '3', '4', '5', '6', '7':
		 := rune() - '0'
		if len() < 2 {
			 = ErrSyntax
			return
		}
		for  := 0;  < 2; ++ { // one digit already; two more
			 := rune([]) - '0'
			if  < 0 ||  > 7 {
				 = ErrSyntax
				return
			}
			 = ( << 3) | 
		}
		 = [2:]
		if  > 255 {
			 = ErrSyntax
			return
		}
		 = 
	case '\\':
		 = '\\'
	case '\'', '"':
		if  !=  {
			 = ErrSyntax
			return
		}
		 = rune()
	default:
		 = ErrSyntax
		return
	}
	 = 
	return
}

// QuotedPrefix returns the quoted string (as understood by Unquote) at the prefix of s.
// If s does not start with a valid quoted string, QuotedPrefix returns an error.
func ( string) (string, error) {
	, ,  := unquote(, false)
	return , 
}

// Unquote interprets s as a single-quoted, double-quoted,
// or backquoted Go string literal, returning the string value
// that s quotes.  (If s is single-quoted, it would be a Go
// character literal; Unquote returns the corresponding
// one-character string.)
func ( string) (string, error) {
	, ,  := unquote(, true)
	if len() > 0 {
		return "", ErrSyntax
	}
	return , 
}

// unquote parses a quoted string at the start of the input,
// returning the parsed prefix, the remaining suffix, and any parse errors.
// If unescape is true, the parsed prefix is unescaped,
// otherwise the input prefix is provided verbatim.
func unquote( string,  bool) (,  string,  error) {
	// Determine the quote form and optimistically find the terminating quote.
	if len() < 2 {
		return "", , ErrSyntax
	}
	 := [0]
	 := index([1:], )
	if  < 0 {
		return "", , ErrSyntax
	}
	 += 2 // position after terminating quote; may be wrong if escape sequences are present

	switch  {
	case '`':
		switch {
		case !:
			 = [:] // include quotes
		case !contains([:], '\r'):
			 = [len("`") : -len("`")] // exclude quotes
		default:
			// Carriage return characters ('\r') inside raw string literals
			// are discarded from the raw string value.
			 := make([]byte, 0, -len("`")-len("\r")-len("`"))
			for  := len("`");  < -len("`"); ++ {
				if [] != '\r' {
					 = append(, [])
				}
			}
			 = string()
		}
		// NOTE: Prior implementations did not verify that raw strings consist
		// of valid UTF-8 characters and we continue to not verify it as such.
		// The Go specification does not explicitly require valid UTF-8,
		// but only mention that it is implicitly valid for Go source code
		// (which must be valid UTF-8).
		return , [:], nil
	case '"', '\'':
		// Handle quoted strings without any escape sequences.
		if !contains([:], '\\') && !contains([:], '\n') {
			var  bool
			switch  {
			case '"':
				 = utf8.ValidString([len(`"`) : -len(`"`)])
			case '\'':
				,  := utf8.DecodeRuneInString([len("'") : -len("'")])
				 = len("'")++len("'") ==  && ( != utf8.RuneError ||  != 1)
			}
			if  {
				 = [:]
				if  {
					 = [1 : -1] // exclude quotes
				}
				return , [:], nil
			}
		}

		// Handle quoted strings with escape sequences.
		var  []byte
		 := 
		 = [1:] // skip starting quote
		if  {
			 = make([]byte, 0, 3*/2) // try to avoid more allocations
		}
		for len() > 0 && [0] !=  {
			// Process the next character,
			// rejecting any unescaped newline characters which are invalid.
			, , ,  := UnquoteChar(, )
			if [0] == '\n' ||  != nil {
				return "", , ErrSyntax
			}
			 = 

			// Append the character if unescaping the input.
			if  {
				if  < utf8.RuneSelf || ! {
					 = append(, byte())
				} else {
					 = utf8.AppendRune(, )
				}
			}

			// Single quoted strings must be a single character.
			if  == '\'' {
				break
			}
		}

		// Verify that the string ends with a terminating quote.
		if !(len() > 0 && [0] == ) {
			return "", , ErrSyntax
		}
		 = [1:] // skip terminating quote

		if  {
			return string(), , nil
		}
		return [:len()-len()], , nil
	default:
		return "", , ErrSyntax
	}
}

// bsearch16 returns the smallest i such that a[i] >= x.
// If there is no such i, bsearch16 returns len(a).
func bsearch16( []uint16,  uint16) int {
	,  := 0, len()
	for  <  {
		 :=  + (-)>>1
		if [] <  {
			 =  + 1
		} else {
			 = 
		}
	}
	return 
}

// bsearch32 returns the smallest i such that a[i] >= x.
// If there is no such i, bsearch32 returns len(a).
func bsearch32( []uint32,  uint32) int {
	,  := 0, len()
	for  <  {
		 :=  + (-)>>1
		if [] <  {
			 =  + 1
		} else {
			 = 
		}
	}
	return 
}

// TODO: IsPrint is a local implementation of unicode.IsPrint, verified by the tests
// to give the same answer. It allows this package not to depend on unicode,
// and therefore not pull in all the Unicode tables. If the linker were better
// at tossing unused tables, we could get rid of this implementation.
// That would be nice.

// IsPrint reports whether the rune is defined as printable by Go, with
// the same definition as unicode.IsPrint: letters, numbers, punctuation,
// symbols and ASCII space.
func ( rune) bool {
	// Fast check for Latin-1
	if  <= 0xFF {
		if 0x20 <=  &&  <= 0x7E {
			// All the ASCII is printable from space through DEL-1.
			return true
		}
		if 0xA1 <=  &&  <= 0xFF {
			// Similarly for ¡ through ÿ...
			return  != 0xAD // ...except for the bizarre soft hyphen.
		}
		return false
	}

	// Same algorithm, either on uint16 or uint32 value.
	// First, find first i such that isPrint[i] >= x.
	// This is the index of either the start or end of a pair that might span x.
	// The start is even (isPrint[i&^1]) and the end is odd (isPrint[i|1]).
	// If we find x in a range, make sure x is not in isNotPrint list.

	if 0 <=  &&  < 1<<16 {
		, ,  := uint16(), isPrint16, isNotPrint16
		 := bsearch16(, )
		if  >= len() ||  < [&^1] || [|1] <  {
			return false
		}
		 := bsearch16(, )
		return  >= len() || [] != 
	}

	, ,  := uint32(), isPrint32, isNotPrint32
	 := bsearch32(, )
	if  >= len() ||  < [&^1] || [|1] <  {
		return false
	}
	if  >= 0x20000 {
		return true
	}
	 -= 0x10000
	 := bsearch16(, uint16())
	return  >= len() || [] != uint16()
}

// IsGraphic reports whether the rune is defined as a Graphic by Unicode. Such
// characters include letters, marks, numbers, punctuation, symbols, and
// spaces, from categories L, M, N, P, S, and Zs.
func ( rune) bool {
	if IsPrint() {
		return true
	}
	return isInGraphicList()
}

// isInGraphicList reports whether the rune is in the isGraphic list. This separation
// from IsGraphic allows quoteWith to avoid two calls to IsPrint.
// Should be called only if IsPrint fails.
func isInGraphicList( rune) bool {
	// We know r must fit in 16 bits - see makeisprint.go.
	if  > 0xFFFF {
		return false
	}
	 := uint16()
	 := bsearch16(isGraphic, )
	return  < len(isGraphic) &&  == isGraphic[]
}