\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#466: Revised Implementation of the Text Widget}
\date{March 10, 2017}
\author{François Vogel, Gregor Cramer}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#466}&\textbf{Revised Implementation of the Text Widget}\\\hline
Author&

François Vogel \tipmail{fvogelnew1}{free.fr}
\par
Gregor Cramer \tipmail{remarcg}{gmx.net}
\\
Created&Friday, \(\text{10}^{\text{th}}\) March 2017\\
Type&Project\\
Tcl Version&\(8.7\)\\
State&Draft\\
Vote&Pending\\
Version&\tipversion$Revision: 1.11 $\\
Keywords&Tk, text widget\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes the replacement of the current implementation of the text widget (the ``legacy'' text widget) by a revised implementation offering a large number of advantages.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

The Tk text widget has become increasingly complex as long as incremental improvements and features have been added from time to time. In that process, some known long-standing issues have become very difficult to tackle, for instance the long line problem regarding lack of performance.

Gregor Cramer, in the process of using the text widget in one of his applications, has analyzed the issues the current text widget is suffering from, and has come up with a new implementation having the following main advantages:
\begin{itemize}
\item{}
Big performance improvement
\item{}
Better implementation of some existing features
\item{}
A large number of new features
\item{}
Numerous bug fixes
\item{}
Very few incompatibilities with the legacy text widget
\end{itemize}

\section{Proposal}

The proposal is to replace the legacy code with the new implementation.

The author of the revised implementation has written a well documented website [\url{http://scidb.sourceforge.net/tk/revised-text-widget.html}] describing in details the issues with the legacy code, how he fixed these issues, and what features he has changed or improved.

It was not deemed feasible nor necessary to copy/paste/reformat all the information of the above website into the present TIP. Only the new features and incompatibilities are highlighted here, as opposed to detailed rationales about each change.

A version of the \textbf{text} man page, consistent with the changes and improvements proposed by the present TIP, can be seen at \url{http://scidb.sourceforge.net/tk/text.html} This version of the man page is colorized, with blue meaning ``changed'', and green meaning ``new'', so that it is easier to spot what's different from the legacy text widget.

\subsection{Performance Improvements}

Detailed performance comparison between legacy code and revised code can be found at [\url{http://scidb.sourceforge.net/tk/comparison.html}] but these are the key points:
\begin{description}
\item[* Long line problem, especially with many tags, is eliminated]
in general only O(N log N) in revised version, was a higher order polynomial time in legacy code.
\item[* Display is faster]
smoother scrolling, faster response time. [\url{http://scidb.sourceforge.net/tk/display.html}]
\item[* Undo/redo is much faster]
a completely new implementation has been worked out, directly working on the text segments. [\url{http://scidb.sourceforge.net/tk/undo.html}]
\end{description}

\subsection{New Features}

Detailed explanations and rationales for each of the items below can be found at [\url{http://scidb.sourceforge.net/tk/revised-text-widget.html}]
\begin{itemize}
\item{}
Undo/redo is handling tags (this was requesteed in Issue \#1561991 and Issue \#1027741, embedded images, embedded windows, and also marks if option \textit{-steadymarks} is enabled
\item{}
Additional widget state \textbf{readonly}
\item{}
Hyphenation and full-justification support
\begin{itemize}
\item{}
Support of hyphenation (Issue \#1096580 is fixed), with new helper functions \textbf{tk\_textinsert} and \textbf{tk\_textReplace}, and with new switches to \textit{pathName} \textbf{count}, \textit{pathName} \textbf{get}, and \textit{pathName} \textbf{search}
\item{}
Additional justification mode \textbf{full}
\item{}
Additional wrap mode \textbf{codepoint}, and new widget option \textbf{-useunibreak}. New subcommand \textit{pathName} \textbf{brks}
\item{}
Additional option \textbf{-lang} used to guide hyphenation engines.
\end{itemize}
\item{}
Additional subcommands:
\begin{itemize}
\item{}
\textit{pathName} \textbf{checksum}
\item{}
\textit{pathName} \textbf{clear}
\item{}
\textit{pathName} \textbf{edit altered}
\item{}
\textit{pathName} \textbf{edit info}
\item{}
\textit{pathName} \textbf{edit inspect}
\item{}
\textit{pathName} \textbf{edit irreversible}
\item{}
\textit{pathName} \textbf{edit recover}
\item{}
\textit{pathName} \textbf{inspect}
\item{}
\textit{pathName} \textbf{isclean}
\item{}
\textit{pathName} \textbf{isdead}
\item{}
\textit{pathName} \textbf{isempty}
\item{}
\textit{pathName} \textbf{lineno}
\item{}
\textit{pathName} \textbf{load}
\item{}
\textit{pathName} \textbf{mark compare}
\item{}
\textit{pathName} \textbf{mark exists}
\item{}
\textit{pathName} \textbf{mark generate}
\item{}
\textit{pathName} \textbf{tag clear}
\item{}
\textit{pathName} \textbf{tag findnext}
\item{}
\textit{pathName} \textbf{tag findprev}
\item{}
\textit{pathName} \textbf{tag getrange}
\item{}
\textit{pathName} \textbf{tag priority}
\item{}
\textit{pathName} \textbf{watch}
\end{itemize}
\item{}
Additional tag attributes:
\begin{itemize}
\item{}
\textbf{-eolcolor}
\item{}
\textbf{-hyphencolor}
\item{}
\textbf{-hyphenrules}
\item{}
\textbf{-inactivebackground}
\item{}
\textbf{-inactiveforeground}
\item{}
\textbf{-inactiveselectbackground}
\item{}
\textbf{-inactiveselectforeground}
\item{}
\textbf{-indentbackground}
\item{}
\textbf{-undo}
\end{itemize}
\item{}
Additional widget options:
\begin{itemize}
\item{}
\textbf{-endindex}
\item{}
\textbf{-eolchar}
\item{}
\textbf{-eolcolor}
\item{}
\textbf{-eotchar}
\item{}
\textbf{-eotcolor}
\item{}
\textbf{-hyphencolor}
\item{}
\textbf{-hyphenrules}
\item{}
\textbf{-hyphens}
\item{}
\textbf{-inactiveselectforeground}
\item{}
\textbf{-insertforeground}
\item{}
\textbf{-maxredo}
\item{}
\textbf{-maxundosize}
\item{}
\textbf{-responsiveness}
\item{}
\textbf{-showendofline}
\item{}
\textbf{-showendoftext}
\item{}
\textbf{-showinsertforeground}
\item{}
\textbf{-spacemode}
\item{}
\textbf{-startindex}
\item{}
\textbf{-steadymarks}
\item{}
\textbf{-synctime}
\item{}
\textbf{-tagging}
\end{itemize}
\item{}
Extensions to the syntax for indices:
\begin{itemize}
\item{}
new specifier \textbf{begin}
\item{}
new syntax \textit{tag}.\textbf{current.first}, \textit{tag}.\textbf{current.last}
\item{}
new syntax \textbf{@first,last}
\end{itemize}
\item{}
Additional features of existing subcommands:
\begin{itemize}
\item{}
Additional option \textbf{-marks} for \textit{pathName} \textbf{delete} command
\item{}
Additional optional parameter \textit{direction} for \textit{pathName} \textbf{mark set} sub-command
\item{}
New virtual event \textbf{\tiplangle{}\tiplangle{}Altered\tiprangle{}\tiprangle{}} to support new sub-command \textit{pathName} \textbf{edit altered}
\item{}
Extensions to commands \textit{pathName} \textbf{edit reset} and \textit{pathName} \textbf{edit separator}
\end{itemize}
\item{}
Extended command \textit{pathName} \textbf{tag names}
\item{}
Additional switch for \textit{pathName} \textbf{dump}
\item{}
Additional option \textbf{-extents} for \textit{pathName} \textbf{bbox} and \textit{pathName} \textbf{dlineinfo}
\item{}
Additional option \textbf{-discardspecial} for \textit{pathName} \textbf{mark names}, \textit{pathName} \textbf{mark next}, and \textit{pathName} \textbf{mark previous}.
\item{}
Additional optional parameter \textit{pattern} for \textit{pathName} \textbf{mark names}, \textit{pathName} \textbf{mark next}, and \textit{pathName} \textbf{mark previous}.
\item{}
New helper commands:
\begin{itemize}
\item{}
\textbf{tk\_mergeRange}
\item{}
\textbf{tk\_textInsert}
\item{}
\textbf{tk\_textReplace}
\item{}
\textbf{tk\_textRebindMouseWheel}
\end{itemize}
\item{}
Additional option \textbf{-owner} for embedded window
\item{}
Additional option \textbf{-tags} for embedded images and embedded windows
\end{itemize}

\subsection{Bug Fixes}
\begin{itemize}
\item{}
Bug fixed in TkTextGetIndex
\item{}
Bug fixed in TkTextGetIndexFromObj
\item{}
Bug fixed in DeleteIndexRange (note that this bugfix implies that deletion at the end of the text handles the last newline now differently --- slight incompatibility with the legacy text widget)
\item{}
Bug fixed in TkTextDeleteTag/TagBindEvent
\item{}
Problems fixed with \textbf{-startline}/\textbf{-endline}
\item{}
Problems fixed with tag event handling
\item{}
Several bug fixes with \textit{'undo}
\item{}
\textbf{Edit modified} confusing results fixed with new command \textbf{edit altered}
\item{}
Severe problems with command \textbf{sync} fixed
\item{}
Invalid changes in disabled widget are marked as deprecated
\item{}
Inaccurate wrapping algorithm fixed
\item{}
Bugs in display logic fixed
\item{}
Insert cursor is now fully visible in all conditions
\end{itemize}
\begin{description}
\item[* Trimming spaces]
Issue \#1082213 is invalid, the fix put in trunk (8.7) has been reverted (but there is now the new option \textbf{-spacemode} that can be set to \textbf{trim})
\end{description}
\begin{itemize}
\item{}
Issues with display of selections fixed
\item{}
\textbf{Update} is no longer wasting the processor time since superfluous update computations are not done anymore
\item{}
Bugs in context drawing support (OS X) fixed
\item{}
Bugs fixed in tkUnixRFont.c
\item{}
Several bug fixes related to handling/positioning of the insertion cursor
\end{itemize}

Details on each of these bugs can be found in the ``Bugs/Issues in Original Implementation'' section at \url{http://scidb.sourceforge.net/tk/revised-text-widget.html}

\subsection{Incompatibilities with Legacy Version}

Based on the author's website, the following incompatibilities are currently known:
\begin{itemize}
\item{}
\cite{tip449} (undo/redo to Return Range of Characters) was not adapted into the revised implementation, because Issue \#1217222 --- the basis for \cite{tip449} --- is now featured by:
\begin{enumerate}
\item{}
The new undo implementation, because also the tag associations will be restored, and
\setcounter{enumi}{1}
\item{}
The powerful \textbf{watch} command, which also provides the affected ranges (with constant runtime behavior).
\end{enumerate}

Moreover, the \textbf{tk\_mergeRange} function convenience function has been implemented in the revised version.
\item{}
The special selection tag \textbf{sel} can no longer be elided (would be useless anyway).
\item{}
Tag options (introduced in 8.6.6) -overstrikefg and -underlinefg were renamed to \textbf{-overstrikecolor} and \textbf{-underlinecolor}
\item{}
The new index syntax \textbf{@first,last} is incompatible with the legacy version but it is not expected that any existing application will break, certainly nobody is using such a form for the name of a mark or image
\item{}
The default value of 50 ms for the new \textbf{-responsiveness} option is incompatible to prior releases, but it shouldn't matter here, because nobody wants flickering, and nobody is using special tricks with a short mouse hovering while the widget is scrolling. Setting the responsiveness to zero restores the old behavior of the text widget.
\item{}
\tiplangle{}\tiplangle{}UndoStack\tiprangle{}\tiprangle{} is generated with any change on the undo stack, not only when the undo stack or the redo stack becomes empty or non-empty
\item{}
\textbf{-startline}/\textbf{-endline} behavior was subtly changed in some corner cases
\item{}
In revised implementation ``+N chars'' and ``-N chars'' refer to characters, and no longer to indices (which was the case in legacy code for backwards compatibility reasons).
\end{itemize}

\subsection{Deprecated Commands and Options}
\begin{itemize}
\item{}
Tag options (introduced in 8.6.6) \textbf{-overstrikefg} and \textbf{-underlinefg} were renamed to -overstrikecolor and -underlinecolor
\item{}
edit \textbf{undodepth}\tipbar{}\textbf{redodepth}\tipbar{}\textbf{canundo}\tipbar{}\textbf{canredo} are replaced by more general \textbf{edit info}
\item{}
Widget options \textbf{-startline}/\textbf{-endline}' are replaced by -startindex/-endindex
\end{itemize}

\subsection{Drawbacks}
\begin{itemize}
\item{}
The increase in memory usage is not very high (but a bit high), and despite this, in many cases, especially if many tags are used, and/or undo is enabled, the revised version is even decreasing the memory usage.
\end{itemize}

Detailed memory comparison between legacy code and revised code can be found at \url{http://scidb.sourceforge.net/tk/comparison.html}

\subsection{Known Issues in the Revised Implementation}

Based on the author's website, currently only these issues are known: 
\begin{itemize}
\item{}
The code for the implementation has increased by more than 100\%, and about 70\% of the old code has been changed. The revised implementation needs more testing, the text widget is very complex, and bugs are expected. And a few additions are not yet well tested.
\item{}
Function \textbf{tk\_textCopy} is copying hidden (elided) text. This seems to be unexpected, but it's the behavior of the original implementation. Probably this is a bug and should be corrected.
\item{}
Adding/deleting tags covering a large range of text is still quite time consuming.
\item{}
The display line with the insert cursor is redrawn each time the cursor blinks, which causes a steady stream of graphics traffic. It would be desirable if the cursor update will be performed with a specialized and efficient redraw function.
\item{}
If option \textbf{-spacemode} is set to trim, then \textbf{get -displaychars} should probably return trimmed spaces. Currently this command is not trimming spaces, so the result may not coincide with the visible text.
\item{}
The \textbf{search -regexp} sub-command is still not yet fully implemented, see Tk documentation.
\item{}
The revised widget still ignores modifying commands if state is not normal; this behavior is unreasonable, but conforms to the original version.
\item{}
Currently the special index specifier \textbf{begin} has the lowest precedence, although it should have the same precedence as the special index special \textbf{end} (see section INDICES). In a future release this should be corrected. The current behavior is a workaround, avoiding that existing applications will break with the introduction of \textbf{begin}.
\item{}
The implementation still contains some TODO's of minor issues. 
\end{itemize}

Also, the following should be noted:
\begin{itemize}
\item{}
With the revised version there are failing tests on all platforms, they need to be fixed (by fixing the expected result in the test, or by fixing the text widget code).
\item{}
More tests should be written to exercise the new or changed features.
\item{}
The OS X case should be more tested on a real Mac, because it's the only platform using context drawing.
\end{itemize}

\subsection{Miscellaneous}
\begin{itemize}
\item{}
No function signature pertaining to a public interface was changed. Also public data structures haven't been touched.
\item{}
All recent new features brought in trunk in the legacy version have their counterpart in the revised version, have been improved in performance and have no known drawbacks. Minor incompatibilities are however identified here and there.
\end{itemize}

\section{Target Release}

Given the amount of changes, also because of our usual precautions regarding backwards compatibility, and despite the very high quality of the code and the fact it passes (almost all) the previously existing test suite, it is deemed reasonable to target Tcl/Tk 8.7 (or 9.0), but neither the 8.6 nor the 8.5 streams of releases, which will continue to implement the legacy text widget code.

Support of versions back to 8.5 is currently included in the revised code, but will be removed (because it's useless for use in trunk only) at the time the new code will get merged into trunk.

\section{Implementation}

Implementation of the revised text widget code has been placed in branch [\url{http://core.tcl.tk/tk/timeline?r=revised_text}] of the fossil repository.

This implementation compiles on Linux, Windows, and OS X. It respects the standards of Tk (C99 standard, and also the Tcl source code formatting described in \cite{tip247}).

The man page for the text widget has been contributed by jima and is included in the revised\_text branch.

The expected results of many tests were adjusted to take into account that the revised implementation is better optimizing, so some trace results of display line computation are different. Other adjustments were required because of bug fixes.

\section{Open Questions}
\begin{itemize}
\item{}
tkTextUndo.c implements a specialized undo/redo, not using the legacy tkUndo.c. Reasons for this are stated at the top of tkTextUndo.c. It is interesting to note that, in the revised\_text branch, tkUndo.c is not even compiled anymore, except on Linux (for no apparent reason). This is dead code waiting for use case by a widget. At least, compilation on Linux should be removed, but couldn't we even rename tkTextUndo.c to tkUndo.c and forget about the old implementation? tkTextUndo.c is also a shareable implementation (in the spirit of \cite{tip104}).
\item{}
Actual removal of deprecated features or keep them (some are marked as deprecated, but actually still supported)?
\end{itemize}

\section{Copyright}

This document has been placed in the public domain.

The author of the revised text widget code has explicitly placed his code of the text widget under the same license as Tcl.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\begin{thebibliography}{TIP \#3}
\addcontentsline{toc}{section}{References}
\bibitem[TIP \#104]{tip104}
Ludwig Callewaert,
Larry W. Virden.,
\emph{Generalization of the Tk Undo Subsystem},
on-line at \url{http://purl.org/tcl/tip/104.html}
\bibitem[TIP \#247]{tip247}
John K. Ousterhout,
Donal K. Fellows,
\emph{Tcl/Tk Engineering Manual},
on-line at \url{http://purl.org/tcl/tip/247.html}
\bibitem[TIP \#449]{tip449}
François Vogel,
\emph{[text] undo/redo to Return Range of Characters},
on-line at \url{http://purl.org/tcl/tip/449.html}
\end{thebibliography}
\end{document}
