| 1 |
<html> |
| 2 |
<head> |
| 3 |
<title>netrik hacker's manual: text search</title> |
| 4 |
</head> |
| 5 |
<body> |
| 6 |
|
| 7 |
<h1 align="center">netrik hacker's manual<br />>========================<</h1> |
| 8 |
|
| 9 |
<p> |
| 10 |
[This file contains a description of the text search functionality. See |
| 11 |
hacking.txt or <a href="hacking.html">hacking.html</a> for an overview |
| 12 |
of the manual.] |
| 13 |
</p> |
| 14 |
|
| 15 |
<a name="framework" id="framework"> |
| 16 |
|
| 17 |
<h2>Framework</h2> |
| 18 |
|
| 19 |
<p> |
| 20 |
Though by far not as complicated as link handling, the text search |
| 21 |
functionality is also somewhat distributed: The serach command is given in the |
| 22 |
pager (<a href="hacking-pager.html#display">display()</a>, see |
| 23 |
hacking-pager.*), and after the search the new position is also activated here. |
| 24 |
The search itself however is done in main(). (There is no real reason for this, |
| 25 |
except that reading the search string has to be done in scroll mode, as well es |
| 26 |
displaying a warning/error if search is wrapped or nothing found.) |
| 27 |
</p> |
| 28 |
|
| 29 |
<p> |
| 30 |
When the search command key ('/') was entered in the pager, display() quits |
| 31 |
with RET_SEARCH. Additionally, "search.type" (see |
| 32 |
<a href="#struct">Search Struct</a> below) is set to |
| 33 |
SEARCH_FORWARD. |
| 34 |
</p> |
| 35 |
|
| 36 |
<p> |
| 37 |
In <a href="hacking.html#main">main()</a> (see hacking.*), when |
| 38 |
RET_SEARCH is encountered, first the search string is read from the user with |
| 39 |
readline("/"). If '^D' was typed, the search is immediately aborted. If nothing |
| 40 |
was typed in (just <return>), we reuse the previous search string; otherwise we |
| 41 |
store the new one. |
| 42 |
</p> |
| 43 |
|
| 44 |
<p> |
| 45 |
Having this, the actual search is performed. This is described under |
| 46 |
<a href="#search">Search</a> below. |
| 47 |
</p> |
| 48 |
|
| 49 |
<p> |
| 50 |
The result of the search operation is a new cursor position. The main loop |
| 51 |
iteration is ended now, and the pager gets restarted in the next iteration. The |
| 52 |
display() then knows to jump to the new position by "search.type" being set. |
| 53 |
</p> |
| 54 |
|
| 55 |
</a> <!-- framework --> |
| 56 |
|
| 57 |
<a name="struct" id="struct"> |
| 58 |
|
| 59 |
<h2>Search Struct</h2> |
| 60 |
|
| 61 |
<p> |
| 62 |
For passing information between the search code in the pager and in main(), as |
| 63 |
well as between multiple searches, a global "search" struct is defined in |
| 64 |
search.c. |
| 65 |
</p> |
| 66 |
|
| 67 |
<p> |
| 68 |
This struct is of type "struct Search" and presently contains the following data: |
| 69 |
<ul> <li> |
| 70 |
"string" is the current/last search string requested. It is stored so it can |
| 71 |
be reused when the user request search again (typing <return> immediately at |
| 72 |
the search prompt, see <a href="#framework">Framework</a> above. |
| 73 |
</li><li> |
| 74 |
"type" has a dual function: In the pager it is set so the search function in |
| 75 |
main() will know what kind of search to perform: forward, backward, next... |
| 76 |
(This is presently a no-op, as there is only one search type available...) |
| 77 |
When returning to a pager the presence of this flag means there was a search |
| 78 |
and the cursor needs to be set to the new position. Again, see |
| 79 |
<a href="#framework">Framework</a> for details. |
| 80 |
</li></ul> |
| 81 |
</p> |
| 82 |
|
| 83 |
</a> <!-- struct --> |
| 84 |
|
| 85 |
<a name="search" id="search"> |
| 86 |
|
| 87 |
<h2>Search</h2> |
| 88 |
|
| 89 |
<p> |
| 90 |
The search itself is done in several steps. First we need to determine where on |
| 91 |
the page the cursor stands to know where to search from, i.e. find out in which |
| 92 |
text item, and the exact position inside this item's text string. |
| 93 |
</p> |
| 94 |
|
| 95 |
<p> |
| 96 |
This part is fairly complicated, as there are several possibilities; it's |
| 97 |
actually the most complicated part of all. The most basic possibility is that |
| 98 |
the cursor stands inmidst some text line. For this to find out, we have to |
| 99 |
check all text items present in the cursor line (using the |
| 100 |
<a href="hacking-layout.html#pageMap">page_map[]</a>, which is described |
| 101 |
under <a href="hacking-layout.html#createMap">create_map()</a> in |
| 102 |
hacking-layout.*). For each of those items we look up the beginning and end of |
| 103 |
the text line visible in the scanned page line using the helper functions from |
| 104 |
<a href="hacking-layout.html#itemsC">items.c</a> (see |
| 105 |
hacking-layout.*). Note that |
| 106 |
<a href="hacking-layout.html#lineStartEnd">line_start() and |
| 107 |
line_end()</a> return the position of the line inside the text string, |
| 108 |
while <a href="hacking-layout.html#linePos">line_pos()</a> gives |
| 109 |
the page position of the line start. |
| 110 |
</p> |
| 111 |
|
| 112 |
<p> |
| 113 |
Now if the cursor actually stands inside the line (the offset of the cursor |
| 114 |
position ralatively to the beginning of the line is >=0 and smaller than the |
| 115 |
line width), we simply store the string position of the cursor, which is the |
| 116 |
string position of the line start plus the offset. |
| 117 |
</p> |
| 118 |
|
| 119 |
<p><pre> |
| 120 |
page: |
| 121 |
|
| 122 |
First paragraph |
| 123 |
with centered text. <-- cursor_y |
| 124 |
| ^ |
| 125 |
|<------->| |
| 126 |
line_pos() offset cursor_x |
| 127 |
|
| 128 |
string: "First paragraph with centered text." |
| 129 |
| ^ |
| 130 |
|<------->| |
| 131 |
line_start() offset start_pos |
| 132 |
</pre></p> |
| 133 |
|
| 134 |
<p> |
| 135 |
The cursor may also stand before the beginning of the line. In this case we |
| 136 |
want to search from the beginning of the line. This is achieved by just |
| 137 |
assuming the cursor *does* stand at the beginning of the line (setting "offset" |
| 138 |
to 0). |
| 139 |
</p> |
| 140 |
|
| 141 |
<p><pre> |
| 142 |
First paragraph |
| 143 |
with centered text. <-- |
| 144 |
^ | |
| 145 |
|<->| |
| 146 |
offset<0 |
| 147 |
</pre></p> |
| 148 |
|
| 149 |
<p> |
| 150 |
A third case is that the cursor stands behind the end of the text line, but |
| 151 |
still inside the text block (i.e. this is not the last line). Here, the search |
| 152 |
starts with the beginning of the next line. (Which is equal to the end of this |
| 153 |
one.) |
| 154 |
</p> |
| 155 |
|
| 156 |
<p><pre> |
| 157 |
line_start() line_end() |
| 158 |
v v |
| 159 |
First paragraph <-- |
| 160 |
with centered text. |
| 161 |
| ^ |
| 162 |
|<--------------->| |
| 163 |
offset >= line_end()-line_start() |
| 164 |
</pre></p> |
| 165 |
|
| 166 |
<p> |
| 167 |
Another procedure is necessary if the cursor doesn't stand inside a text item |
| 168 |
at all (the above search has no result). In this case we have to search from |
| 169 |
the beginning of the next text item. For this, we simply scan all text items in |
| 170 |
the page and take the first one that starts after "cursor_y". (Alternatively we |
| 171 |
could scan the page linewise starting with the next line... This would be way |
| 172 |
more efficient, but may cause problems when tables and similar things are |
| 173 |
implemented. We will revise this at some point.) |
| 174 |
</p> |
| 175 |
|
| 176 |
<p><pre> |
| 177 |
First paragraph <-- item->y_start <= cursor_y |
| 178 |
with centered text. |
| 179 |
<-- cursor_y |
| 180 |
Second paragraph. <-- item->y_start > cursor_y <== start_item |
| 181 |
^ |
| 182 |
start_pos=0 |
| 183 |
</pre></p> |
| 184 |
|
| 185 |
<p> |
| 186 |
Now the real search can start. It is done item by item, till the page end. In |
| 187 |
each text item, we search for the search string inside the item's text string |
| 188 |
with strstr(). For the first item, we start with "start_pos" as offset, so only |
| 189 |
the string part after the cursor position is searched; for all following items, |
| 190 |
"start_pos" is set to 0. |
| 191 |
</p> |
| 192 |
|
| 193 |
<p> |
| 194 |
As soon as strstr() returns the first match, the matching item and the position |
| 195 |
inside the string are memorized, and the search is terminated. |
| 196 |
</p> |
| 197 |
|
| 198 |
<p> |
| 199 |
If nothing was found, the search is wrapped: In a second step, all items |
| 200 |
beginning with the first one on the page and ending with the start item are |
| 201 |
scanned. (Note that the start item is searched again, this time starting at the |
| 202 |
beginning of the string. The part after "start_pos" is searched a second time, |
| 203 |
but this shouldn't matter.) |
| 204 |
</p> |
| 205 |
|
| 206 |
<p> |
| 207 |
There is an exception if the search started at the page end ("start_item" is |
| 208 |
NULL): We can't scan up to the start item inclusive in this case, of course; |
| 209 |
instead, we simply scan to the page end. (No special handling of this case is |
| 210 |
necessary in the first pass, as that one just scans to the page end, thus will |
| 211 |
simply terminate immediately.) |
| 212 |
</p> |
| 213 |
|
| 214 |
<p> |
| 215 |
Finally the match position needs to be transformed back to page coordinates |
| 216 |
again. This is much simpler than the other way round: We just need to find out |
| 217 |
in which line of the text item the match position is located, and can calculate |
| 218 |
y and x coordinates from the line number and the line position then. |
| 219 |
</p> |
| 220 |
|
| 221 |
<p><pre> |
| 222 |
line_end(0) line_end(1) |
| 223 |
v v |
| 224 |
string: "First paragraph with centered text." |
| 225 |
| ^ |
| 226 |
|<----------->| |
| 227 |
line_start(1) offset match_pos |
| 228 |
|
| 229 |
page: |
| 230 |
|
| 231 |
First paragraph |
| 232 |
with centered text. <-- cursor_y=line_end(1) |
| 233 |
| ^ |
| 234 |
|<----------->| |
| 235 |
line_pos(1) offset cursor_x |
| 236 |
</pre></p> |
| 237 |
|
| 238 |
</a> <!-- search --> |
| 239 |
|
| 240 |
</body> |
| 241 |
</html> |