I have created an AccessibilityService by following this document: https://developer.android.com/reference/android/accessibilityservice/AccessibilityService.html
I don't think it's necessary to copy the code here because I did everything step by step and it works fine on all emulators that I've tried(between 19-25 API's) but it's not working on my real device(API 25). On the real device onServiceConnected method is never called. It's the only real device I've got. What can I try? What can cause this problem?
Edit: Now I've tried on a different real device(Android 4.4) and it works on that too. Now I am really confused.
Reboot solved the problem! I can't believe this. I spent a day for this. I am not going to delete the question. Maybe it can save someone else's day.