I've been experiencing an intermittent and difficult to reproduce bug where I use Evil (rev 42737279f1b75ec3731c3f3b0f2c465862159b40) to search and replace in a region and when the bug occurs, replacements are made throughout the buffer and point is left in the wrong place. Reproduction comes in streaks: when I witness it once, I can do it again and again for a while, then it stops reproducing at all. I made progress tracking the cause down such that I can report some findings here. I didn't finish narrowing down the problem because it stopped reproducing.

Description of events at the Lisp level:
аа Х Let my-old-string be a string which I've redacted for privacy. It is 14 non regex chars.
аа Х Let my-new-string be a redacted string. It is 16 chars, no backslashes.
аа Х Evil calls: (perform-replace my-old-string (replace-eval-replacement . my-new-string) nil t nil nil nil 6605 6749)
аа Х perform-replace calls: (replace-match my-new-string t nil) match-data=(6686 6700 [redacted filename])
ааааа Х Before the call to replace-match, point is 6700
ааааа Х After the call to replace-match, point is inexplicably 25

Since replace-match is implemented in C, I attached gdb to the running Emacs. I find that when the variable newpoint is assigned by:
аа newpoint = search_regs.start[sub] + SCHARS (newtext);
it is 9+16. I can see where 16 comes from, but not 9. sub is 0; I found search_regs.start[0] has the correct value of 6686 for a time prior. I continued to narrow down when search_regs.start[0] changes until the problem stopped reproducing. Here is the stack trace where it goes wrong:

#6а 0x00000000004fb13f in signal_after_change (charpos=6686, lendel=14, lenins=16) at insdel.c:2058
#7а 0x00000000004fcd87 in replace_range (from=6686, to=<value optimized out>, new=<value optimized out>, prepare=<value optimized out>, inherit=false, markers=true) at insdel.c:1427
#8а 0x0000000000516cd9 in Freplace_match (newtext=158062897, fixedcase=<value optimized out>, literal=<value optimized out>, string=1, subexp=<value optimized out>) at search.c:2644
#9а 0x0000000000544d8f in eval_sub (form=<value optimized out>) at eval.c:2157
#10 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#11 0x0000000000545454 in funcall_lambda (fun=167311462, nargs=5, arg_vector=0x7fff400cb870) at eval.c:3003
#12 0x000000000054686c in apply_lambda (fun=167311446, args=19819474) at eval.c:2887
#13 0x0000000000544a84 in eval_sub (form=<value optimized out>) at eval.c:2218
#14 0x000000000054504f in Fsetq (args=<value optimized out>) at eval.c:429
#15 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#16 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#17 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#18 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#19 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#20 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#21 0x0000000000544c63 in eval_sub (form=<value optimized out>) at eval.c:2214
#22 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#23 0x0000000000547a08 in Fwhile (args=<value optimized out>) at eval.c:936
#24 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#25 0x0000000000546975 in Funwind_protect (args=145892294) at eval.c:1148
#26 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#27 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#28 0x0000000000547e97 in FletX (args=131856198) at eval.c:844
#29 0x0000000000544f55 in eval_sub (form=<value optimized out>) at eval.c:2091
#30 0x000000000054511f in Fprogn (args=<value optimized out>) at eval.c:360
#31 0x0000000000545454 in funcall_lambda (fun=137050230, nargs=9, arg_vector=0x7fff400cc2f0) at eval.c:3003
#32 0x0000000000545692 in Ffuncall (nargs=10, args=<value optimized out>) at eval.c:2839
#33 0x0000000000577b1e in exec_byte_code (bytestr=6605, vector=38, maxdepth=11914850, args_template=11914850, nargs=0, args=0x0) at bytecode.c:900
#34 0x00000000005453d7 in funcall_lambda (fun=14279397, nargs=5, arg_vector=0x7fff400cc4e8) at eval.c:3010
#35 0x0000000000545692 in Ffuncall (nargs=6, args=<value optimized out>) at eval.c:2839
#36 0x0000000000545cc4 in Fapply (nargs=2, args=0x7fff400cc590) at eval.c:2312
#37 0x0000000000545ee0 in apply1 (fn=97848594, arg=<value optimized out>) at eval.c:2546
#38 0x0000000000541564 in Fcall_interactively (function=97848594, record_flag=11914850, keys=11950037) at callint.c:377
#39 0x00000000005457f7 in Ffuncall (nargs=2, args=<value optimized out>) at eval.c:2785
#40 0x0000000000577b1e in exec_byte_code (bytestr=6605, vector=33, maxdepth=11914850, args_template=11914850, nargs=0, args=0x0) at bytecode.c:900
#41 0x00000000005453d7 in funcall_lambda (fun=19430901, nargs=3, arg_vector=0x7fff400cc8b0) at eval.c:3010
#42 0x000000000054686c in apply_lambda (fun=19430901, args=158068849) at eval.c:2887
#43 0x0000000000544a84 in eval_sub (form=<value optimized out>) at eval.c:2218
#44 0x0000000000546edd in Feval (form=169173046, lexical=<value optimized out>) at eval.c:2005
#45 0x00000000005457e0 in Ffuncall (nargs=2, args=<value optimized out>) at eval.c:2781
#46 0x0000000000577b1e in exec_byte_code (bytestr=6605, vector=33, maxdepth=11914850, args_template=11914850, nargs=0, args=0x0) at bytecode.c:900
#47 0x00000000005453d7 in funcall_lambda (fun=19550949, nargs=1, arg_vector=0x7fff400ccd48) at eval.c:3010
#48 0x0000000000545692 in Ffuncall (nargs=2, args=<value optimized out>) at eval.c:2839
#49 0x0000000000545e47 in Fapply (nargs=2, args=0x7fff400ccd40) at eval.c:2259
#50 0x0000000000545ee0 in apply1 (fn=13903650, arg=<value optimized out>) at eval.c:2546
#51 0x0000000000541564 in Fcall_interactively (function=13903650, record_flag=11914850, keys=11950037) at callint.c:377
#52 0x00000000005457f7 in Ffuncall (nargs=4, args=<value optimized out>) at eval.c:2785
#53 0x0000000000545a74 in call3 (fn=<value optimized out>, arg1=<value optimized out>, arg2=11914850, arg3=11914898) at eval.c:2603
#54 0x00000000004e5402 in command_loop_1 () at keyboard.c:1587
#55 0x00000000005441a6 in internal_condition_case (bfun=0x4e5040 <command_loop_1>, handlers=11966498, hfun=0x4dc150 <cmd_error>) at eval.c:1289
#56 0x00000000004dbc9a in command_loop_2 (ignore=<value optimized out>) at keyboard.c:1168
#57 0x000000000054429a in internal_catch (tag=<value optimized out>, func=0x4dbc80 <command_loop_2>, arg=11914850) at eval.c:1060
#58 0x00000000004dc3f0 in command_loop () at keyboard.c:1147
#59 recursive_edit_1 () at keyboard.c:779
#60 0x00000000004dc53a in Frecursive_edit () at keyboard.c:843
#61 0x00000000004d4146 in main (argc=<value optimized out>, argv=0x7fff400cd538) at emacs.c:1528

Before replace_match's call to signal_after_change, search_regs.start[0] is correct, after signal_after_change returns, it is incorrect.

Looking at the code, I see what I think are callbacks to Lisp related to overlays. It's notable that Evil uses overlays to display the search and replace as the user types the command in, showing the old string striked out the old with the new string alongside. Is it possible the invoked hooks could replace the match data and thus cause search_regs to have wrong values upon return? Are there other ideas about what's going on? The next time I witness the bug, I'll narrow down where in signal_after_change the value becomes wrong.

In GNU Emacs 24.3.2 (x86_64-unknown-linux-gnu, GTK+ Version 2.10.4)
аof 2013-03-11 on psd15
Windowing system distributor `The X.Org Foundation', version 11.0.70101000
System Description:ааа Red Hat Enterprise Linux Client release 5.4 (Tikanga)

Configured using:
а`configure '--prefix=/[redacted]/user/boreilly/sw/emacs-24.3/rhel5-install'
а'--with-gif=no''

Important settings:
а value of $LANG: en_US.UTF-8
а value of $XMODIFIERS: @im=none
а locale-coding-system: utf-8-unix
а default enable-multibyte-characters: t

Major mode: Fundamental

Minor modes in effect:
а diff-auto-refine-mode: t
а shell-dirtrack-mode: t
а global-whitespace-mode: t
а global-cedet-m3-minor-mode: t
а global-semantic-mru-bookmark-mode: t
а global-semanticdb-minor-mode: t
а global-semantic-idle-scheduler-mode: t
а semantic-mode: t
а global-ede-mode: t
а evil-mode: t
а evil-local-mode: t
а global-undo-tree-mode: t
а undo-tree-mode: t
а show-paren-mode: t
а delete-selection-mode: t
а global-auto-revert-mode: t
а tooltip-mode: t
а mouse-wheel-mode: t
а menu-bar-mode: t
а file-name-shadow-mode: t
а global-font-lock-mode: t
а font-lock-mode: t
а blink-cursor-mode: t
а auto-composition-mode: t
а auto-encryption-mode: t
а auto-compression-mode: t
а column-number-mode: t
а line-number-mode: t
а transient-mark-mode: t

Recent input:
' ' ' ' ' ' ' / h e r e SPC 1 3 <return> N N n ' '
' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ; j
k k k k k k k k k k k k k k k k k k k k k k k k k k
k k V y f j j j j j j <return> / n e w t e x t <return>
f j <return> k k V y f j <return> V y f j <return>
j j j k f j j j <return> f <return> ; ' ' ' j V y C-c
V y C-c V y / s u b <return> ' ' ' ' ' ' ' ' ' ' '
' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '
' ' ' ' ' ' k k k k k k k k k k k k n 0 f <return>
j k f j j j j j j j H <return> f <return> f j <return>
j k W W W W h h h h h h h h h h h h h h h h h v l l
l l l l l l l l l l l l l l l l l l l l l l l l l l
l l l l l l l l l l l l l l l l l l l l l l l y M-x
r e p o r t - <tab> <return>

Recent messages:
Undo branch point!
Commands: d, s, x, u; f, o, 1, 2, m, v; ~, %; q to quit; ? for help. [5 times]
Mark set [7 times]
Commands: d, s, x, u; f, o, 1, 2, m, v; ~, %; q to quit; ? for help.
Mark set
Commands: d, s, x, u; f, o, 1, 2, m, v; ~, %; q to quit; ? for help. [5 times]
Mark set [2 times]
Commands: d, s, x, u; f, o, 1, 2, m, v; ~, %; q to quit; ? for help. [2 times]
Mark set
Commands: d, s, x, u; f, o, 1, 2, m, v; ~, %; q to quit; ? for help. [2 times]

Load-path shadows:
/redacted/user/boreilly/sw/cedet/lisp/speedbar/loaddefs hides /redacted/user/boreilly/sw/cedet/lisp/eieio/loaddefs
/redacted/user/boreilly/sw/cedet/lisp/speedbar/loaddefs hides /redacted/user/boreilly/sw/cedet/lisp/cedet/loaddefs
/redacted/user/boreilly/sw/cedet/lisp/speedbar/loaddefs hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/loaddefs
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio-speedbar hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio-speedbar
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio-opt hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio-opt
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio-datadebug hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio-datadebug
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio-custom hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio-custom
/redacted/user/boreilly/sw/cedet/lisp/eieio/eieio-base hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/eieio-base
/redacted/user/boreilly/sw/cedet/lisp/eieio/chart hides /redacted/user/boreilly/sw/emacs-24.3/rhel5-install/share/emacs/24.3/lisp/emacs-lisp/chart

Features:
(shadow sort mail-extr emacsbug message format-spec rfc822 mml mml-sec
mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils
mailheader sendmail rfc2047 rfc2045 ietf-drums mail-utils jka-compr
vc-hg ede/emacs semantic/bovine/el semantic/bovine/make
semantic/bovine/make-by make-mode diff-mode easy-mmode shell pcomplete
thingatpt semantic/analyze/complete semantic/db-typecache semantic/edit
ede/maven2 ede/lein2 ede/ant ede/java-root ede/jvm-base ede/linux
ede/make ede/dired dired ffap url-parse auth-source gnus-util mm-util
mail-prsvr password-cache url-vars find-file semantic/tag-write
ede/locate semantic/m3 semantic/tag-file semantic/db-file
semantic/adebug eieio-datadebug data-debug cedet-files semantic/bovine/c
semantic/decorate/include semantic/decorate/mode hideif
semantic/bovine/c-by semantic/bovine cc-langs cc-mode cc-fonts cc-guess
cc-menus cc-cmds cc-styles cc-align cc-engine cc-vars cc-defs my-config
semantic/lex-spp etags whitespace cus-start cus-load my-proj
ede/cpp-root hippie-exp comint ansi-color eassist derived cedet-m3
semantic/mru-bookmark semantic/db-mode semantic/idle semantic/bovine/gcc
semantic/dep semantic/ia semantic/analyze/refs semantic/senator
semantic/db-find semantic/db-ref semantic/decorate working fame pulse
cedet-devel-load warnings eieio-opt help-mode find-func srecode/map
srecode semantic/canned-configs semantic/ia-sb semantic/analyze
semantic/sort semantic/scope semantic/analyze/fcn semantic/db
semantic/ctxt semantic/format semantic/tag-ls semantic/find
semantic/util-modes semantic/util semantic semantic/tag semantic/lex
semantic/fw mode-local cedet-compat inversion ede/speedbar ede/files ede
ede/base ede/auto ede/source eieio-base eieio-speedbar speedbar sb-image
ezimage dframe easymenu eieio-custom wid-edit cedet eieio byte-opt
bytecomp byte-compile cconv eieio-core cedet-remove-builtin cl-macs gv
evil evil-integration evil-maps evil-commands evil-types evil-search
evil-ex evil-macros evil-repeat evil-states evil-core evil-common
windmove rect evil-digraphs evil-vars ring edmacro kmacro goto-chg
undo-tree diff rainbow-delimiters my-util advice help-fns advice-preload
electric paren delsel autorevert cl cl-lib time-date tooltip ediff-hook
vc-hooks lisp-float-type mwheel x-win x-dnd tool-bar dnd fontset image
regexp-opt fringe tabulated-list newcomment lisp-mode register page
menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock font-lock
syntax facemenu font-core frame cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese hebrew greek
romanian slovak czech european ethiopic indian cyrillic chinese
case-table epa-hook jka-cmpr-hook help simple abbrev minibuffer loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote make-network-process dbusbind dynamic-setting
system-font-setting font-render-setting move-toolbar gtk x-toolkit x
multi-tty emacs)