<commit_before>/*
	Copyright (c) 2014, Percona LLC and/or its affiliates. All rights reserved.

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Affero General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Affero General Public License for more details.

	You should have received a copy of the GNU Affero General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>
*/

package query

/*
	Fingerprint is highly-specialized and operates on a single principle:

		1. We only replace numbers, quoted strings, and value lists.

	Although we must handle a lot of details, exceptions, and special cases,
	that principle distills the problem to its essence which makes it
	possible to solve without a true SQL syntax parser (or regex). It means
	that we can simply copy and ignore the vast majority of the query because
	if it's not a number, quoted string, or value list then there's nothing
	to do. With a regex solution we can stop there and simply do transformations
	like s/\d+/?/g and s/'[^']*'/?/g but the details, exceptions, and specials
	cases make that only a partial, crude solution because, for example, with
	col = 'It\s' an escaped quote char.' now the regex needs to handle inner,
	escaped quotes so it becomes more complicated and slower. There are many
	more difficult problems like this. Consequently, neither regex nor this
	solution can be simple, but at least this solution is very fast compared
	to regex because it makes a single pass through the query whereas regex
	makes as many passes as there are regexes and, worst case, a single regex
	can make several passes due to backtracking. To handle problems like these,
	this solution is a simple state machine. In the previous example problem,
	once the first quote char (') is seen we enter the inQuote state. In this
	state, if an escape char (\) is seen, this is remembered and the next char
	is ignored. This allows us to correctly detect the real ending quote char:
	it's the first unescaped quote char. Consequently, we can simply ignore
	everything else in the quoted value. The same basic logic applies to numbers
	and value lists.

	With that principle and basic logic in mind, you'll notice three major code
	blocks:
		1. Skip parts of the query for certain states.
		2. Change state based on rune and current state.
		3. Copy a slice of the query into the fingerprint.
	The order is important because it enforces the basic logic: once we enter
	certain states we must process and finish them first because in these states
	we ignore everything but whatever ends the state. As mentioned above, the
	inQuote state is handled in the first block. When in this state, only the
	real ending quote char ends it. Consequently nothing will trick the parser;
	for example the quoted value in col="INSERT INTO t VALUES ('no problem')"
	will not be mistaken for another query and another quoted value. --
	The second block is primarily where cpFromOffset and cpToOffset are set
	which are used by the third block to copy that range of the query into the
	fingerprint. The second block stops, switches state, copies, and lets
	the code enter the first block which skips through number, quoted value, or
	value list that the second block found.
*/

import (
	"crypto/md5"
	"fmt"
	"io"
	"strings"
)

const (
	unknown             byte = iota
	inWord                   // \S+
	inNumber                 // [0-9a-fA-Fx.-]
	inSpace                  // space, tab, \r, \n
	inOp                     // [=<>!] (usually precedes a number)
	opOrNumber               // + in 2 + 2 or +3e-9
	inQuote                  // '...' or "..."
	subOrOLC                 // - or start of -- comment
	inDash                   // -- begins a one-line comment if followed by space
	inOLC                    // -- comment (at least one space after dash is required)
	divOrMLC                 // / operator or start of /* comment */
	mlcOrMySQLCode           // /* comment */ or /*! MySQL-specific code */
	inMLC                    // /* comment */
	inValues                 // VALUES (1), ..., (N)
	moreValuesOrUnknown      // , (2nd+) or ON DUPLICATE KEY or end of query
	orderBy                  // ORDER BY
	onDupeKeyUpdate          // ON DUPLICATE KEY UPDATE
	inNumberInWord           // e.g. db23
)

var stateName map[byte]string = map[byte]string{
	0:  "unknown",
	1:  "inWord",
	2:  "inNumber",
	3:  "inSpace",
	4:  "inOp",
	5:  "opOrNumber",
	6:  "inQuote",
	7:  "subOrOLC",
	8:  "inDash",
	9:  "inOLC",
	10: "divOrMLC",
	11: "mlcOrMySQLCode",
	12: "inMLC",
	13: "inValues",
	14: "moreValuesOrUnknown",
	15: "orderBy",
	16: "onDupeKeyUpdate",
	17: "inNumberInWord",
}

var Debug bool = false
var ReplaceNumbersInWords = false

func Fingerprint(q string) string {
	q += " " // need range to run off end of original query
	prevWord := ""
	f := make([]byte, len(q))
	fi := 0
	pr := rune(0) // previous rune
	s := unknown  // current state
	sqlState := unknown
	quoteChar := rune(0)
	cpFromOffset := 0
	cpToOffset := 0
	addSpace := false
	escape := false
	parOpen := 0
	parOpenTotal := 0
	valueNo := 0
	firstPar := 0

	for qi, r := range q {
		if Debug {
			fmt.Printf("\n%d:%d %s/%s [%d:%d] %x %q\n", qi, fi, stateName[s], stateName[sqlState], cpFromOffset, cpToOffset, r, r)
		}

		/**
		 * 1. Skip parts of the query for certain states.
		 */

		if s == inQuote {
			// We're in a 'quoted value' or "quoted value".  The quoted value
			// ends at the first non-escaped matching quote character (' or ").
			if r != quoteChar {
				// The only char inside a quoted value we need to track is \,
				// the escape char.  This allows us to tell that the 2nd ' in
				// '\'' is escaped, not the ending quote char.
				if escape {
					if Debug {
						fmt.Println("Ignore quoted literal")
					}
					escape = false
				} else if r == '\\' {
					if Debug {
						fmt.Println("Escape")
					}
					escape = true
				} else {
					if Debug {
						fmt.Println("Ignore quoted value")
					}
				}
			} else if escape {
				// \' or \"
				if Debug {
					fmt.Println("Quote literal")
				}
				escape = false
			} else {
				// 'foo' -> ?
				// "foo" -> ?
				if Debug {
					fmt.Println("Quote end")
				}
				escape = false

				// qi = the closing quote char, so +1 to ensure we don't copy
				// anything before this, i.e. quoted value is done, move on.
				cpFromOffset = qi + 1

				if sqlState == inValues {
					// ('Hello world!', ...) -> VALUES (, ...)
					// The inValues state uses this state to skip quoted values,
					// so we don't replace them with ?; the inValues blocks will
					// replace the entire value list with ?+.
					s = inValues
				} else {
					f[fi] = '?'
					fi++
					s = unknown
				}
			}
			continue
		} else if s == inNumberInWord {
			if r >= '0' && r <= '9' {
				if Debug {
					fmt.Println("Ignore digit in word")
				}
				continue
			}
			// 123 -> ?, 0xff -> ?, 1e-9 -> ?, etc.
			if Debug {
				fmt.Println("Number in word end")
			}
			f[fi] = '?'
			fi++
			cpFromOffset = qi<commit_msg>PCT-1255: Comments<commit_after>/*
	Copyright (c) 2014, Percona LLC and/or its affiliates. All rights reserved.

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Affero General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Affero General Public License for more details.

	You should have received a copy of the GNU Affero General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>
*/

package query

/*
	Fingerprint is highly-specialized and operates on a single principle:

		1. We only replace numbers, quoted strings, and value lists.

	Although we must handle a lot of details, exceptions, and special cases,
	that principle distills the problem to its essence which makes it
	possible to solve without a true SQL syntax parser (or regex). It means
	that we can simply copy and ignore the vast majority of the query because
	if it's not a number, quoted string, or value list then there's nothing
	to do. With a regex solution we can stop there and simply do transformations
	like s/\d+/?/g and s/'[^']*'/?/g but the details, exceptions, and specials
	cases make that only a partial, crude solution because, for example, with
	col = 'It\s' an escaped quote char.' now the regex needs to handle inner,
	escaped quotes so it becomes more complicated and slower. There are many
	more difficult problems like this. Consequently, neither regex nor this
	solution can be simple, but at least this solution is very fast compared
	to regex because it makes a single pass through the query whereas regex
	makes as many passes as there are regexes and, worst case, a single regex
	can make several passes due to backtracking. To handle problems like these,
	this solution is a simple state machine. In the previous example problem,
	once the first quote char (') is seen we enter the inQuote state. In this
	state, if an escape char (\) is seen, this is remembered and the next char
	is ignored. This allows us to correctly detect the real ending quote char:
	it's the first unescaped quote char. Consequently, we can simply ignore
	everything else in the quoted value. The same basic logic applies to numbers
	and value lists.

	With that principle and basic logic in mind, you'll notice three major code
	blocks:
		1. Skip parts of the query for certain states.
		2. Change state based on rune and current state.
		3. Copy a slice of the query into the fingerprint.
	The order is important because it enforces the basic logic: once we enter
	certain states we must process and finish them first because in these states
	we ignore everything but whatever ends the state. As mentioned above, the
	inQuote state is handled in the first block. When in this state, only the
	real ending quote char ends it. Consequently nothing will trick the parser;
	for example the quoted value in col="INSERT INTO t VALUES ('no problem')"
	will not be mistaken for another query and another quoted value. --
	The second block is primarily where cpFromOffset and cpToOffset are set
	which are used by the third block to copy that range of the query into the
	fingerprint. The second block stops, switches state, copies, and lets
	the code enter the first block which skips through number, quoted value, or
	value list that the second block found.
*/

import (
	"crypto/md5"
	"fmt"
	"io"
	"strings"
)

const (
	unknown             byte = iota
	inWord                   // \S+
	inNumber                 // [0-9a-fA-Fx.-]
	inSpace                  // space, tab, \r, \n
	inOp                     // [=<>!] (usually precedes a number)
	opOrNumber               // + in 2 + 2 or +3e-9
	inQuote                  // '...' or "..."
	subOrOLC                 // - or start of -- comment
	inDash                   // -- begins a one-line comment if followed by space
	inOLC                    // -- comment (at least one space after dash is required)
	divOrMLC                 // / operator or start of /* comment */
	mlcOrMySQLCode           // /* comment */ or /*! MySQL-specific code */
	inMLC                    // /* comment */
	inValues                 // VALUES (1), ..., (N)
	moreValuesOrUnknown      // , (2nd+) or ON DUPLICATE KEY or end of query
	orderBy                  // ORDER BY
	onDupeKeyUpdate          // ON DUPLICATE KEY UPDATE
	inNumberInWord           // e.g. db23
)

var stateName map[byte]string = map[byte]string{
	0:  "unknown",
	1:  "inWord",
	2:  "inNumber",
	3:  "inSpace",
	4:  "inOp",
	5:  "opOrNumber",
	6:  "inQuote",
	7:  "subOrOLC",
	8:  "inDash",
	9:  "inOLC",
	10: "divOrMLC",
	11: "mlcOrMySQLCode",
	12: "inMLC",
	13: "inValues",
	14: "moreValuesOrUnknown",
	15: "orderBy",
	16: "onDupeKeyUpdate",
	17: "inNumberInWord",
}

var Debug bool = false

// Set ReplaceNumbersInWords to true to cover cases like e.g.:
// `SELECT c FROM org235.t` -> `SELECT c FROM org?.t`
// For more examples take a look at test query_test.go/TestFingerprintWithNumberInDbName
var ReplaceNumbersInWords = false

func Fingerprint(q string) string {
	q += " " // need range to run off end of original query
	prevWord := ""
	f := make([]byte, len(q))
	fi := 0
	pr := rune(0) // previous rune
	s := unknown  // current state
	sqlState := unknown
	quoteChar := rune(0)
	cpFromOffset := 0
	cpToOffset := 0
	addSpace := false
	escape := false
	parOpen := 0
	parOpenTotal := 0
	valueNo := 0
	firstPar := 0

	for qi, r := range q {
		if Debug {
			fmt.Printf("\n%d:%d %s/%s [%d:%d] %x %q\n", qi, fi, stateName[s], stateName[sqlState], cpFromOffset, cpToOffset, r, r)
		}

		/**
		 * 1. Skip parts of the query for certain states.
		 */

		if s == inQuote {
			// We're in a 'quoted value' or "quoted value".  The quoted value
			// ends at the first non-escaped matching quote character (' or ").
			if r != quoteChar {
				// The only char inside a quoted value we need to track is \,
				// the escape char.  This allows us to tell that the 2nd ' in
				// '\'' is escaped, not the ending quote char.
				if escape {
					if Debug {
						fmt.Println("Ignore quoted literal")
					}
					escape = false
				} else if r == '\\' {
					if Debug {
						fmt.Println("Escape")
					}
					escape = true
				} else {
					if Debug {
						fmt.Println("Ignore quoted value")
					}
				}
			} else if escape {
				// \' or \"
				if Debug {
					fmt.Println("Quote literal")
				}
				escape = false
			} else {
				// 'foo' -> ?
				// "foo" -> ?
				if Debug {
					fmt.Println("Quote end")
				}
				escape = false

				// qi = the closing quote char, so +1 to ensure we don't copy
				// anything before this, i.e. quoted value is done, move on.
				cpFromOffset = qi + 1

				if sqlState == inValues {
					// ('Hello world!', ...) -> VALUES (, ...)
					// The inValues state uses this state to skip quoted values,
					// so we don't replace them with ?; the inValues blocks will
					// replace the entire value list with ?+.
					s = inValues
				} else {
					f[fi] = '?'
					fi++
					s = unknown
				}
			}
			continue
		} else if s == inNumberInWord {
			// Replaces number in words with ?
			// e.g. `db37` to `db?`
			// Parser can fall into inNumberInWord only if
			// option ReplaceNumbersInWords is turned on
			if r >= '0' && r <= '9' {
				if Debug {
					fmt.Println("Ignore digit in word")
				}
				continue
			}
			// 123 -> ?, 0xff -> ?, 1e-9 -> ?, etc.
			if Debug {
				fmt.Println("Number in word end")
			}
			f[fi] = '?'
			fi++
			cpFromOffset = qi
{'fraction_non_alphanumeric': 0.0936774364758177, 'fraction_numerical': 0.009487162475950375, 'mean_word_length': 2.540991308433169, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4351829', 'n_tokens_mistral': 5081, 'n_tokens_neox': 4424, 'n_words': 2043}