{"action":"created","comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/38206653","id":38206653,"diff_hunk":"@@ -0,0 +1,1036 @@\n+// Copyright 2015 The Cockroach Authors.\n+//\n+// Licensed under the Apache License, Version 2.0 (the \"License\");\n+// you may not use this file except in compliance with the License.\n+// You may obtain a copy of the License at\n+//\n+//     http://www.apache.org/licenses/LICENSE-2.0\n+//\n+// Unless required by applicable law or agreed to in writing, software\n+// distributed under the License is distributed on an \"AS IS\" BASIS,\n+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or\n+// implied. See the License for the specific language governing\n+// permissions and limitations under the License. See the AUTHORS file\n+// for names of contributors.\n+//\n+// Author: Peter Mattis (peter@cockroachlabs.com)\n+\n+package sql\n+\n+import (\n+\t\"fmt\"\n+\t\"reflect\"\n+\t\"regexp\"\n+\t\"sort\"\n+\t\"strings\"\n+\n+\t\"github.com/cockroachdb/cockroach/proto\"\n+\t\"github.com/cockroachdb/cockroach/sql/parser\"\n+)\n+\n+// analyzeExpr analyzes and simplifies an expression, returning a list of\n+// expressions of a list of expressions. The top-level list contains\n+// disjunctions (a.k.a OR expressions). The second-level contains conjuntions\n+// (a.k.a. AND expressions). For example:\n+//\n+//   (a AND b) OR c -> [[a, b], c]\n+func analyzeExpr(e parser.Expr) []parser.Exprs {\n+\te = simplifyExpr(e)\n+\torExprs := splitOrExpr(e, nil)\n+\tresults := make([]parser.Exprs, len(orExprs))\n+\tfor i := range orExprs {\n+\t\tresults[i] = splitAndExpr(orExprs[i], nil)\n+\t}\n+\treturn results\n+}\n+\n+// splitOrExpr flattens a tree of OR expressions returning all of the child\n+// expressions as a list. Any non-OR expression is returned as a single element\n+// in the list.\n+//\n+//   a OR b OR c OR d -> [a, b, c, d]\n+func splitOrExpr(e parser.Expr, exprs parser.Exprs) parser.Exprs {\n+\tswitch t := e.(type) {\n+\tcase *parser.OrExpr:\n+\t\treturn splitOrExpr(t.Right, splitOrExpr(t.Left, exprs))\n+\t}\n+\treturn append(exprs, e)\n+}\n+\n+// splitAndExpr flattens a tree of AND expressions returning all of the child\n+// expressions as a list. Any non-AND expression is returned as a single\n+// element in the list.\n+//\n+//   a AND b AND c AND d -> [a, b, c, d]\n+func splitAndExpr(e parser.Expr, exprs parser.Exprs) parser.Exprs {\n+\tswitch t := e.(type) {\n+\tcase *parser.AndExpr:\n+\t\treturn splitAndExpr(t.Right, splitAndExpr(t.Left, exprs))\n+\t}\n+\treturn append(exprs, e)\n+}\n+\n+// simplifyExpr transforms an expression such that it contains only expressions\n+// involving qvalues that can be used for index selection. If an expression is\n+// encountered that cannot be used for index selection (e.g. \"func(val)\") that\n+// part of the expression tree is considered to evaluate to true, possibly\n+// rendering the entire expression as true. Additionally, various\n+// normalizations are performed on comparison expressions. For example:\n+//\n+//   (a < 1 AND a < 2)  -> (a < 1)\n+//   (a < 1 AND a > 2)  -> false\n+//   (a > 1 OR a < 2)   -> true\n+//   (a > 1 OR func(b)) -> true\n+//\n+// Note that simplification is not normalization. Normalization as performed by\n+// parser.NormalizeExpr returns an expression that is equivalent to the\n+// original. Simplification can return an expression with parts of the\n+// expression tree stripped out.\n+func simplifyExpr(e parser.Expr) parser.Expr {\n+\tswitch t := e.(type) {\n+\tcase *parser.NotExpr:\n+\t\treturn simplifyNotExpr(t)\n+\tcase *parser.AndExpr:\n+\t\treturn simplifyAndExpr(t)\n+\tcase *parser.OrExpr:\n+\t\treturn simplifyOrExpr(t)\n+\tcase *parser.ComparisonExpr:\n+\t\treturn simplifyComparisonExpr(t)\n+\tcase *qvalue:\n+\t\treturn e\n+\t}\n+\t// We don't know how to simplify expressions that fall through to here, so\n+\t// consider this part of the expression true.\n+\treturn parser.DBool(true)\n+}\n+\n+func simplifyNotExpr(n *parser.NotExpr) parser.Expr {\n+\tswitch t := n.Expr.(type) {\n+\tcase *parser.ComparisonExpr:\n+\t\top := t.Operator\n+\t\tswitch op {\n+\t\tcase parser.EQ:\n+\t\t\top = parser.NE\n+\t\tcase parser.NE:\n+\t\t\top = parser.EQ\n+\t\tcase parser.GT:\n+\t\t\top = parser.LT","path":"sql/analyze.go","position":117,"original_position":117,"commit_id":"910af4212d14f5571ba66519811b4377e2d49c91","original_commit_id":"910af4212d14f5571ba66519811b4377e2d49c91","user":{"login":"petermattis","id":6201335,"avatar_url":"https://avatars.githubusercontent.com/u/6201335?v=3","gravatar_id":"","url":"https://api.github.com/users/petermattis","html_url":"https://github.com/petermattis","followers_url":"https://api.github.com/users/petermattis/followers","following_url":"https://api.github.com/users/petermattis/following{/other_user}","gists_url":"https://api.github.com/users/petermattis/gists{/gist_id}","starred_url":"https://api.github.com/users/petermattis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/petermattis/subscriptions","organizations_url":"https://api.github.com/users/petermattis/orgs","repos_url":"https://api.github.com/users/petermattis/repos","events_url":"https://api.github.com/users/petermattis/events{/privacy}","received_events_url":"https://api.github.com/users/petermattis/received_events","type":"User","site_admin":false},"body":"It sure is. More importantly, why didn't `checkEquivExpr` catch this...\r\n\r\nOh, it looks like `checkEquivExpr` was broken. Now fixed and it caught the errors here and some invalid equivalency checks in `TestSimplifyAndExprCheck`. ","created_at":"2015-08-28T14:42:44Z","updated_at":"2015-08-28T14:42:44Z","html_url":"https://github.com/cockroachdb/cockroach/pull/2285#discussion_r38206653","pull_request_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285","_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments/38206653"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/2285#discussion_r38206653"},"pull_request":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285"}}},"pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285","id":43567000,"html_url":"https://github.com/cockroachdb/cockroach/pull/2285","diff_url":"https://github.com/cockroachdb/cockroach/pull/2285.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/2285.patch","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/2285","number":2285,"state":"open","locked":false,"title":"Replace qvalueRange and qvalueRangeMap with analyzeExpr.","user":{"login":"petermattis","id":6201335,"avatar_url":"https://avatars.githubusercontent.com/u/6201335?v=3","gravatar_id":"","url":"https://api.github.com/users/petermattis","html_url":"https://github.com/petermattis","followers_url":"https://api.github.com/users/petermattis/followers","following_url":"https://api.github.com/users/petermattis/following{/other_user}","gists_url":"https://api.github.com/users/petermattis/gists{/gist_id}","starred_url":"https://api.github.com/users/petermattis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/petermattis/subscriptions","organizations_url":"https://api.github.com/users/petermattis/orgs","repos_url":"https://api.github.com/users/petermattis/repos","events_url":"https://api.github.com/users/petermattis/events{/privacy}","received_events_url":"https://api.github.com/users/petermattis/received_events","type":"User","site_admin":false},"body":"Working towards #2140 and #2142.","created_at":"2015-08-27T21:07:23Z","updated_at":"2015-08-28T14:42:44Z","closed_at":null,"merged_at":null,"merge_commit_sha":"76a12fe6b2b7190b525161f16b74229fc573f5bf","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285/commits","review_comments_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285/comments","review_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments{/number}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/2285/comments","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/910af4212d14f5571ba66519811b4377e2d49c91","head":{"label":"cockroachdb:pmattis/sql-analyze","ref":"pmattis/sql-analyze","sha":"910af4212d14f5571ba66519811b4377e2d49c91","user":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"repo":{"id":16563587,"name":"cockroach","full_name":"cockroachdb/cockroach","owner":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/cockroachdb/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":false,"url":"https://api.github.com/repos/cockroachdb/cockroach","forks_url":"https://api.github.com/repos/cockroachdb/cockroach/forks","keys_url":"https://api.github.com/repos/cockroachdb/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cockroachdb/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cockroachdb/cockroach/teams","hooks_url":"https://api.github.com/repos/cockroachdb/cockroach/hooks","issue_events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/cockroachdb/cockroach/events","assignees_url":"https://api.github.com/repos/cockroachdb/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/cockroachdb/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/cockroachdb/cockroach/tags","blobs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cockroachdb/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/cockroachdb/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/cockroachdb/cockroach/languages","stargazers_url":"https://api.github.com/repos/cockroachdb/cockroach/stargazers","contributors_url":"https://api.github.com/repos/cockroachdb/cockroach/contributors","subscribers_url":"https://api.github.com/repos/cockroachdb/cockroach/subscribers","subscription_url":"https://api.github.com/repos/cockroachdb/cockroach/subscription","commits_url":"https://api.github.com/repos/cockroachdb/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/cockroachdb/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments{/number}","contents_url":"https://api.github.com/repos/cockroachdb/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/cockroachdb/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cockroachdb/cockroach/merges","archive_url":"https://api.github.com/repos/cockroachdb/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cockroachdb/cockroach/downloads","issues_url":"https://api.github.com/repos/cockroachdb/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/cockroachdb/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/cockroachdb/cockroach/releases{/id}","created_at":"2014-02-06T00:18:47Z","updated_at":"2015-08-27T19:00:43Z","pushed_at":"2015-08-28T14:32:17Z","git_url":"git://github.com/cockroachdb/cockroach.git","ssh_url":"git@github.com:cockroachdb/cockroach.git","clone_url":"https://github.com/cockroachdb/cockroach.git","svn_url":"https://github.com/cockroachdb/cockroach","homepage":null,"size":52520,"stargazers_count":5057,"watchers_count":5057,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":400,"mirror_url":null,"open_issues_count":150,"forks":400,"open_issues":150,"watchers":5057,"default_branch":"master"}},"base":{"label":"cockroachdb:master","ref":"master","sha":"aa47787f2f59bf42ab885d59652334c4df77126e","user":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"repo":{"id":16563587,"name":"cockroach","full_name":"cockroachdb/cockroach","owner":{"login":"cockroachdb","id":6748139,"avatar_url":"https://avatars.githubusercontent.com/u/6748139?v=3","gravatar_id":"","url":"https://api.github.com/users/cockroachdb","html_url":"https://github.com/cockroachdb","followers_url":"https://api.github.com/users/cockroachdb/followers","following_url":"https://api.github.com/users/cockroachdb/following{/other_user}","gists_url":"https://api.github.com/users/cockroachdb/gists{/gist_id}","starred_url":"https://api.github.com/users/cockroachdb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cockroachdb/subscriptions","organizations_url":"https://api.github.com/users/cockroachdb/orgs","repos_url":"https://api.github.com/users/cockroachdb/repos","events_url":"https://api.github.com/users/cockroachdb/events{/privacy}","received_events_url":"https://api.github.com/users/cockroachdb/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/cockroachdb/cockroach","description":"A Scalable, Geo-Replicated, Transactional Datastore","fork":false,"url":"https://api.github.com/repos/cockroachdb/cockroach","forks_url":"https://api.github.com/repos/cockroachdb/cockroach/forks","keys_url":"https://api.github.com/repos/cockroachdb/cockroach/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cockroachdb/cockroach/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cockroachdb/cockroach/teams","hooks_url":"https://api.github.com/repos/cockroachdb/cockroach/hooks","issue_events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/events{/number}","events_url":"https://api.github.com/repos/cockroachdb/cockroach/events","assignees_url":"https://api.github.com/repos/cockroachdb/cockroach/assignees{/user}","branches_url":"https://api.github.com/repos/cockroachdb/cockroach/branches{/branch}","tags_url":"https://api.github.com/repos/cockroachdb/cockroach/tags","blobs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cockroachdb/cockroach/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cockroachdb/cockroach/git/refs{/sha}","trees_url":"https://api.github.com/repos/cockroachdb/cockroach/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cockroachdb/cockroach/statuses/{sha}","languages_url":"https://api.github.com/repos/cockroachdb/cockroach/languages","stargazers_url":"https://api.github.com/repos/cockroachdb/cockroach/stargazers","contributors_url":"https://api.github.com/repos/cockroachdb/cockroach/contributors","subscribers_url":"https://api.github.com/repos/cockroachdb/cockroach/subscribers","subscription_url":"https://api.github.com/repos/cockroachdb/cockroach/subscription","commits_url":"https://api.github.com/repos/cockroachdb/cockroach/commits{/sha}","git_commits_url":"https://api.github.com/repos/cockroachdb/cockroach/git/commits{/sha}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/comments{/number}","issue_comment_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments{/number}","contents_url":"https://api.github.com/repos/cockroachdb/cockroach/contents/{+path}","compare_url":"https://api.github.com/repos/cockroachdb/cockroach/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cockroachdb/cockroach/merges","archive_url":"https://api.github.com/repos/cockroachdb/cockroach/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cockroachdb/cockroach/downloads","issues_url":"https://api.github.com/repos/cockroachdb/cockroach/issues{/number}","pulls_url":"https://api.github.com/repos/cockroachdb/cockroach/pulls{/number}","milestones_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones{/number}","notifications_url":"https://api.github.com/repos/cockroachdb/cockroach/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/labels{/name}","releases_url":"https://api.github.com/repos/cockroachdb/cockroach/releases{/id}","created_at":"2014-02-06T00:18:47Z","updated_at":"2015-08-27T19:00:43Z","pushed_at":"2015-08-28T14:32:17Z","git_url":"git://github.com/cockroachdb/cockroach.git","ssh_url":"git@github.com:cockroachdb/cockroach.git","clone_url":"https://github.com/cockroachdb/cockroach.git","svn_url":"https://github.com/cockroachdb/cockroach","homepage":null,"size":52520,"stargazers_count":5057,"watchers_count":5057,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":400,"mirror_url":null,"open_issues_count":150,"forks":400,"open_issues":150,"watchers":5057,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285"},"html":{"href":"https://github.com/cockroachdb/cockroach/pull/2285"},"issue":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/2285"},"comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/issues/2285/comments"},"review_comments":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285/comments"},"review_comment":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/cockroachdb/cockroach/pulls/2285/commits"},"statuses":{"href":"https://api.github.com/repos/cockroachdb/cockroach/statuses/910af4212d14f5571ba66519811b4377e2d49c91"}}}}