$ which xcodebuild
/usr/bin/xcodebuild
$ brew upgrade python3
==> Upgrading 1 outdated package, with result:
python3 3.5.2
==> Upgrading python3
Warning: Building python3 from source:
The bottle needs the Xcode CLT to be installed.
==> Downloading https://www.python.org/ftp/python/3.5.2/Python-3.5.2.tar.xz
...

There's a distinction in this case between the Command Line Tools shipped inside Xcode and Apple's Command Line Tools package. That explanatory message about the bottle is perhaps badly worded.
brew config will show whether Homebrew considers CLT installed or not.
Thanks, that was confusing. brew config indeed showed CLT: N/A until I installed the package from https://developer.apple.com/download/more/; now it shows CLT: 7.3.1.0.1.1461711523. So I guess I won't have this problem in the future. +1 for improving the wording, ideally including a hint as to how to fix.
Updated both python and python3 to be a little clearer. Hopefully helps. Thanks for letting us know you found this confusing!
Thanks @DomT4, and thanks for all your great work on Homebrew!
Try to run the follow command in the terminal:
xcode-select --install
It works for me:
CLT: 8.1.0.0.1.1476494586
thx ~ @jiahaoliuliu
Had the same, issue - installing the package fixed it.
Most helpful comment
Try to run the follow command in the terminal:
xcode-select --installIt works for me:
CLT: 8.1.0.0.1.1476494586