4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
30 * Copyright 2004 Giovanni Bajo
31 * All Rights Reserved.
34 * \brief Line editing support with history
36 * Rationale for basic implementation choices:
38 * \li The history is implemented storing consecutive ASCIIZ strings within an array of memory. When
39 * the history is full, the first (oldest) line is cancelled and the whole buffer is memmoved to
40 * overwrite it and make room. while this is is obviously not the fastest algorithm (which would
41 * require the use of a circular buffer) it is surely good enough for this module, which does not
42 * aim at fast performances (line editing does not require to be blazingly fast).
44 * \li The first character in the history is always \c \\0, and it is used as a guard. By 'wasting' it
45 * in this way, the code actually gets much simpler in that we remove many checks when moving
46 * backward (\c i>0 and similar).
48 * \li While editing, the current index points to the position of the buffer which contains the
49 * last character typed in (exactly like a stack pointer). This also allows to simplify calculations
50 * and to make easier using the last byte of history.
52 * \li While editing, the current line is always kept null-terminated. This is important because
53 * if the user press ENTER, we must have room to add a \c \\0 to terminate the line. If the line
54 * is as long as the whole history buffer, there would not be space for it. By always keeping the
55 * \c \\0 at the end, we properly ensure this without making index checks harder.
57 * \li When removing a line from the history (see \c pop_history()), instead of updating all the
58 * indices we have around, we move backward the pointer to the history we use. This way, we don't
59 * have to update anything. This means that we keep two pointers to the history: \c real_history
60 * always points to the physical start, while \c history is the adjusted pointer (that is
61 * dereference to read/write to it).
63 * \todo Use up/down to move through history The history line will be copied to the current line,
64 * making sure there is room for it.
68 * \author Giovanni Bajo <rasky@develer.com>
74 #include <cfg/compiler.h>
75 #include <cfg/debug.h>
81 /// Enable compilation of the unit test code
82 #define DEBUG_UNIT_TEST 0
84 /// Enable dump of the history after each line
85 #define DEBUG_DUMP_HISTORY 0
88 /** Special keys (escape sequences converted to a single code) */
90 SPECIAL_KEYS = 0x1000,
95 * UpArrow: 0x1B 0x5B 0X41
96 * DownArrow: 0x1B 0x5B 0X42
97 * RightArrow: 0x1B 0x5B 0x43
98 * LeftArrow: 0x1b 0x5B 0x44
99 * Beak(Pause): 0x1b 0x5B 0x50
110 * F1: 0x1b 0x5B 0x5B 0x41
111 * F2: 0x1b 0x5B 0x5B 0x42
112 * F3: 0x1b 0x5B 0x5B 0x43
113 * F4: 0x1b 0x5B 0x5B 0x44
114 * F5: 0x1b 0x5B 0x5B 0x45
115 * Ins: 0x1b 0x5B 0x32 0x7E
116 * Home: 0x1b 0x5B 0x31 0x7E
117 * PgUp: 0x1b 0x5B 0x35 0x7E
118 * Del: 0x1b 0x5B 0x33 0x7E
119 * End: 0x1b 0x5B 0x34 0x7E
120 * PgDn: 0x1b 0x5B 0x36 0x7E
122 KEY_F1, KEY_F2, KEY_F3, KEY_F4, KEY_F5,
123 KEY_INS, KEY_HOME, KEY_PGUP, KEY_DEL, KEY_END, KEY_PGDN,
128 * F6: 0x1b 0x5B 0x31 0x37 0x7E
129 * F7: 0x1b 0x5B 0x31 0x38 0x7E
130 * F8: 0x1b 0x5B 0x31 0x39 0x7E
131 * F9: 0x1b 0x5B 0x32 0x30 0x7E
132 * F10: 0x1b 0x5B 0x32 0x31 0x7E
133 * F11: 0x1b 0x5B 0x32 0x33 0x7E
134 * F12: 0x1b 0x5B 0x32 0x34 0x7E
136 KEY_F6, KEY_F7, KEY_F8, KEY_F9,
137 KEY_F10, KEY_F11, KEY_F12,
140 /** Check if \a c is a separator between words.
141 * \note Parameter \a c is evaluated multiple times
143 #define IS_WORD_SEPARATOR(c) ((c) == ' ' || (c) == '\0')
145 /// Write the string \a txt to the IO output (without any kind of termination)
146 INLINE void rl_puts(const struct RLContext* ctx, const char* txt)
152 ctx->put(*txt++, ctx->put_param);
155 /// Write character \a ch to the IO output.
156 INLINE void rl_putc(const struct RLContext* ctx, char ch)
159 ctx->put(ch, ctx->put_param);
162 /** Read a character from the IO into \a ch. This function also takes
163 * care of converting the ANSI escape sequences into one of the codes
164 * defined in \c RL_KEYS.
166 static bool rl_getc(const struct RLContext* ctx, int* ch)
168 int c = ctx->get(ctx->get_param);
173 ctx->clear(ctx->clear_param);
180 // Unknown ESC sequence. Ignore it and read
181 // return next character.
182 if (ctx->get(ctx->get_param) != 0x5B)
183 return rl_getc(ctx, ch);
186 * Home: 0x1b 0x5B 0x31 0x7E
187 * F6: 0x1b 0x5B 0x31 0x37 0x7E
188 * F7: 0x1b 0x5B 0x31 0x38 0x7E
189 * F8: 0x1b 0x5B 0x31 0x39 0x7E
190 * Ins: 0x1b 0x5B 0x32 0x7E
191 * F9: 0x1b 0x5B 0x32 0x30 0x7E
192 * F10: 0x1b 0x5B 0x32 0x31 0x7E
193 * F11: 0x1b 0x5B 0x32 0x33 0x7E
194 * F12: 0x1b 0x5B 0x32 0x34 0x7E
195 * Del: 0x1b 0x5B 0x33 0x7E
196 * End: 0x1b 0x5B 0x34 0x7E
197 * PgUp: 0x1b 0x5B 0x35 0x7E
198 * PgDn: 0x1b 0x5B 0x36 0x7E
201 c = ctx->get(ctx->get_param);
204 case 0x41: c = KEY_UP_ARROW; break;
205 case 0x42: c = KEY_DOWN_ARROW; break;
206 case 0x43: c = KEY_RIGHT_ARROW; break;
207 case 0x44: c = KEY_LEFT_ARROW; break;
208 case 0x50: c = KEY_PAUSE; break;
210 c = ctx->get(ctx->get_param);
213 case 0x41: c = KEY_F1; break;
214 case 0x42: c = KEY_F2; break;
215 case 0x43: c = KEY_F3; break;
216 case 0x44: c = KEY_F4; break;
217 case 0x45: c = KEY_F5; break;
218 default: return rl_getc(ctx, ch);
221 default: return rl_getc(ctx, ch);
229 INLINE void beep(struct RLContext* ctx)
234 static bool pop_history(struct RLContext* ctx, int total_len)
236 // Compute the length of the first command (including terminator).
237 int len = strlen(ctx->real_history+1)+1;
239 // (the first byte of the history should always be 0)
240 ASSERT(ctx->real_history[0] == '\0');
242 // If it is the only one in the history, do nothing
243 if (len == total_len)
246 // Overwrite the first command with the second one
247 memmove(ctx->real_history, ctx->real_history+len, HISTORY_SIZE-len);
249 // Move back the ctx->buffer pointer so that all the indices are still valid
255 /// Check if index \a i points to the begin of the history.
256 INLINE bool is_history_begin(struct RLContext* ctx, int i)
257 { return ctx->history + i == ctx->real_history; }
259 /// Check if index \a i points to the (exclusive) end of history
260 INLINE bool is_history_end(struct RLContext* ctx, int i)
261 { return ctx->history + i == ctx->real_history + HISTORY_SIZE; }
263 /// Check if index \a i points to the (exclusive) end of history, or somewhere past the end.
264 INLINE bool is_history_past_end(struct RLContext* ctx, int i)
265 { return ctx->history + i >= ctx->real_history + HISTORY_SIZE; }
267 /** Insert \a num_chars characters from \a ch into the history buffer at the
268 * position indicated by \a curpos. If needed, remove old history to make room.
269 * Returns true if everything was successful, false if there was no room to
270 * add the characters.
271 * \note \a num_chars can be 0, in which case we just make sure the line is
272 * correctly zero-terminated (ASCIIZ format).
274 static bool insert_chars(struct RLContext* ctx, size_t *curpos, const char* ch, int num_chars)
276 ASSERT(!is_history_past_end(ctx, *curpos));
278 while (is_history_past_end(ctx, *curpos+num_chars+1))
280 if (!pop_history(ctx, *curpos))
285 ctx->history[++(*curpos)] = *ch++;
287 ASSERT(!is_history_past_end(ctx, *curpos + 1));
288 ctx->history[*curpos+1] = '\0';
292 /// Insert a single character \a ch into the buffer (with the same semantic of \c insert_chars())
293 static bool insert_char(struct RLContext* ctx, size_t *curpos, char ch)
295 return insert_chars(ctx, curpos, &ch, 1);
298 #if DEBUG_DUMP_HISTORY
299 /// Dump the internal history of a context (used only for debug purposes)
300 static void dump_history(struct RLContext* ctx)
304 ASSERT(ctx->real_history[0] == '\0');
305 rl_puts(ctx, "History dump:");
306 rl_puts(ctx, "\r\n");
308 ctx->real_history + k != ctx->history + ctx->history_pos + 1;
309 k += strlen(&ctx->real_history[k]) + 1)
311 rl_puts(ctx, &ctx->real_history[k]);
312 rl_puts(ctx, "\r\n");
315 sprintf(buf, "%d\r\n", ctx->history_pos + (ctx->history - ctx->real_history));
318 #endif /* DEBUG_DUMP_HISTORY */
320 /// Complete the current word. Return false if no unambiguous completion was found
321 static bool complete_word(struct RLContext *ctx, size_t *curpos)
323 const char* completed_word;
326 // If the current character is a separator,
327 // there is nothing to complete
329 if (IS_WORD_SEPARATOR(ctx->history[wstart]))
335 // Find the separator before the current word
338 while (!IS_WORD_SEPARATOR(ctx->history[wstart]));
340 // Complete the word through the hook
341 completed_word = ctx->match(ctx->match_param, ctx->history + wstart + 1, *curpos - wstart);
345 // Move back the terminal cursor to the separator
346 while (*curpos != wstart)
352 // Insert the completed command
353 insert_chars(ctx, curpos, completed_word, strlen(completed_word));
354 rl_puts(ctx, completed_word);
355 insert_char(ctx, curpos, ' ');
361 void rl_refresh(struct RLContext* ctx)
363 rl_puts(ctx, "\r\n");
365 rl_puts(ctx, ctx->prompt);
366 rl_puts(ctx, ctx->history + ctx->history_pos + 1);
369 const char* rl_readline(struct RLContext* ctx)
371 size_t i = ctx->history_pos;
374 rl_puts(ctx, ctx->prompt);
376 insert_chars(ctx, &i, NULL, 0);
383 ASSERT(ctx->history - ctx->real_history + ctx->line_pos < HISTORY_SIZE);
385 if (!rl_getc(ctx, &c))
388 // Just ignore special keys for now
389 if (c > SPECIAL_KEYS)
394 // Ask the match hook if available
398 complete_word(ctx, &ctx->line_pos);
402 if (c == '\r' || c == '\n')
405 rl_puts(ctx, ctx->prompt);
408 insert_chars(ctx, &ctx->line_pos, NULL, 0);
409 rl_puts(ctx, "\r\n");
413 // Backspace cancels a character, or it is ignored if at
414 // the start of the line
417 if (ctx->history[ctx->line_pos] != '\0')
420 rl_puts(ctx, "\b \b");
425 // Add a character to the buffer, if possible
427 ASSERT2(ch == c, "a special key was not properly handled");
428 if (insert_chars(ctx, &ctx->line_pos, &ch, 1))
438 ctx->history_pos = ctx->line_pos + 1;
439 while (ctx->history[ctx->line_pos] != '\0')
442 // Do not store empty lines in the history
443 if (ctx->line_pos == ctx->history_pos - 1)
444 ctx->history_pos -= 1;
446 #if DEBUG_DUMP_HISTORY
450 // Since the current pointer now points to the separator, we need
451 // to return the first character
452 return &ctx->history[ctx->line_pos + 1];
458 /** Perform the unit test for the readline library */
461 #if HISTORY_SIZE != 32
462 #error This test needs HISTORY_SIZE to be set at 32
465 static struct RLContext test_ctx;
467 static char* test_getc_ptr;
468 static int test_getc(void* data)
470 return *test_getc_ptr++;
473 /** Perform a readline test. The function pipes the characters from \a input_buffer
474 * through the I/O to \c rl_readline(). After the whole string is sent, \c do_test()
475 * checks if the current history within the context match \a expected_history.
477 static bool do_test(char* input_buffer, char* expected_history)
479 rl_init_ctx(&test_ctx);
480 rl_sethook_get(&test_ctx, test_getc, NULL);
482 test_getc_ptr = input_buffer;
483 while (*test_getc_ptr)
484 rl_readline(&test_ctx);
486 if (memcmp(test_ctx.real_history, expected_history, HISTORY_SIZE) != 0)
488 ASSERT2(0, "history compare failed");
497 char* test1_in = "a\nb\nc\nd\ne\nf\ng\nh\ni\nj\nk\nl\nm\nn\no\np\nq\nr\ns\nt\nu\nv\nw\nx\ny\nz\n";
498 char test1_hist[HISTORY_SIZE] = "\0l\0m\0n\0o\0p\0q\0r\0s\0t\0u\0v\0w\0x\0y\0z";
500 if (!do_test(test1_in, test1_hist))
503 kprintf("rl_test successful\n");
506 #endif /* DEBUG_UNIT_TEST */