| 1 |
TODO list for agedu |
| 2 |
=================== |
| 3 |
|
| 4 |
- flexibility in the HTML report output mode: expose the internal |
| 5 |
mechanism for configuring the output filenames, and allow the |
| 6 |
user to request individual files with hyperlinks as if the other |
| 7 |
files existed. (In particular, functionality of this kind would |
| 8 |
enable other modes of use like the built-in --cgi mode, without |
| 9 |
me having to anticipate them in detail.) |
| 10 |
|
| 11 |
- non-ASCII character set support |
| 12 |
+ could usefully apply to --title and also to file names |
| 13 |
+ how do we determine the input charset? Via locale, presumably. |
| 14 |
+ how do we do translation? Importing my charset library is one |
| 15 |
heavyweight option; alternatively, does the native C locale |
| 16 |
mechanism provide enough functionality to do the job by itself? |
| 17 |
+ in HTML, we would need to decide on an _output_ character set, |
| 18 |
specify it in a <meta http-equiv> tag, and translate to it from |
| 19 |
the input locale |
| 20 |
- one option is to make the output charset the same as the |
| 21 |
input one, in which case all we need is to identify its name |
| 22 |
for the <meta> tag |
| 23 |
- the other option is to make the output charset UTF-8 always |
| 24 |
and translate to that from everything else |
| 25 |
- in the web server and CGI modes, it would probably be nicer |
| 26 |
to move that <meta> tag into a proper HTTP header |
| 27 |
+ even in text mode we would want to parse the filenames in some |
| 28 |
fashion, due to the unhelpful corner case of Shift-JIS Windows |
| 29 |
(in which backslashes in the input string must be classified as |
| 30 |
path separators or the second byte of a two-byte character) |
| 31 |
- that's really painful, since it will impact string processing |
| 32 |
of filenames throughout the code |
| 33 |
- so perhaps a better approach would be to do locale processing |
| 34 |
of filenames at _scan_ time, and normalise to UTF-8 in both |
| 35 |
the index and dump files? |
| 36 |
+ involves incrementing the version of the dump-file format |
| 37 |
+ then paths given on the command line are translated |
| 38 |
quickly to UTF-8 before comparing them against index paths |
| 39 |
+ and now the HTML output side becomes easy, though the text |
| 40 |
output involves translating back again |
| 41 |
+ but what if the filenames aren't intended to be |
| 42 |
interpreted in any particular character set (old-style |
| 43 |
Unix semantics) or in a consistent one? |
| 44 |
|
| 45 |
- we could still be using more of the information coming from |
| 46 |
autoconf. Our config.h is defining a whole bunch of HAVE_FOOs for |
| 47 |
particular functions (e.g. HAVE_INET_NTOA, HAVE_MEMCHR, |
| 48 |
HAVE_FNMATCH). We could usefully supply alternatives for some of |
| 49 |
these functions (e.g. cannibalise the PuTTY wildcard matcher for |
| 50 |
use in the absence of fnmatch, switch to vanilla truncate() in |
| 51 |
the absence of ftruncate); where we don't have alternative code, |
| 52 |
it would perhaps be polite to throw an error at configure time |
| 53 |
rather than allowing the subsequent build to fail. |
| 54 |
+ however, I don't see anything here that looks very |
| 55 |
controversial; IIRC it's all in POSIX, for one thing. So more |
| 56 |
likely this should simply wait until somebody complains. |
| 57 |
|
| 58 |
- run-time configuration in the HTTP server |
| 59 |
* I think this probably works by having a configuration form, or |
| 60 |
a link pointing to one, somewhere on the report page. If you |
| 61 |
want to reconfigure anything, you fill in and submit the form; |
| 62 |
the web server receives HTTP GET with parameters and a |
| 63 |
referer, adjusts its internal configuration, and returns an |
| 64 |
HTTP redirect back to the referring page - which it then |
| 65 |
re-renders in accordance with the change. |
| 66 |
* All the same options should have their starting states |
| 67 |
configurable on the command line too. |
| 68 |
|
| 69 |
- curses-ish equivalent of the web output |
| 70 |
+ try using xterm 256-colour mode. Can (n)curses handle that? If |
| 71 |
not, try doing it manually. |
| 72 |
+ I think my current best idea is to bypass ncurses and go |
| 73 |
straight to terminfo: generate lines of attribute-interleaved |
| 74 |
text and display them, so we only really need the sequences |
| 75 |
"go here and display stuff", "scroll up", "scroll down". |
| 76 |
+ Infrastructure work before doing any of this would be to split |
| 77 |
html.c into two: one part to prepare an abstract data |
| 78 |
structure describing an HTML-like report (in particular, all |
| 79 |
the index lookups, percentage calculation, vector arithmetic |
| 80 |
and line sorting), and another part to generate the literal |
| 81 |
HTML. Then the former can be reused to produce very similar |
| 82 |
reports in coloured plain text. |
| 83 |
|
| 84 |
- abstracting away all the Unix calls so as to enable a full |
| 85 |
Windows port. We can already do the difficult bit on Windows |
| 86 |
(scanning the filesystem and retrieving atime-analogues). |
| 87 |
Everything else is just coding - albeit quite a _lot_ of coding, |
| 88 |
since the Unix assumptions are woven quite tightly into the |
| 89 |
current code. |
| 90 |
+ If nothing else, it's unclear what the user interface properly |
| 91 |
ought to be in a Windows port of agedu. A command-line job |
| 92 |
exactly like the Unix version might be useful to some people, |
| 93 |
but would certainly be strange and confusing to others. |
| 94 |
|
| 95 |
- replacing the index data structure with a layered range tree. |
| 96 |
+ The basic idea of the data structure: |
| 97 |
* store a search tree ordered by atime, in which every node |
| 98 |
stores an array of pairs (pathname index, cumulative size) |
| 99 |
describing the data in that node's subtree, ordered by the |
| 100 |
pathname index. |
| 101 |
* Also, alongside each element in a node's array is the index |
| 102 |
of the corresponding location in the sort order in the array |
| 103 |
at each child node. |
| 104 |
+ To search the tree for a given (path index, atime) query point: |
| 105 |
* Start by doing a log-time search for the path index in the |
| 106 |
array at the root node. |
| 107 |
* Now, every time you descend to a child node, you can use the |
| 108 |
crosslinks between the arrays to find the corresponding |
| 109 |
search position in the new node's array, in constant time. |
| 110 |
* So your overall search still takes log time, and from every |
| 111 |
node you can read off the total size of stuff in that subtree |
| 112 |
less than the query path index, which is enough to find the |
| 113 |
total size of stuff in the desired quadrant. |
| 114 |
+ This also enables a 3-sided query (i.e. specifying both start |
| 115 |
and end pathname index) in a single operation: just start by |
| 116 |
finding _both_ your pathname index endpoints in the root node's |
| 117 |
array, and then as you descend the tree you can read off the |
| 118 |
total size of stuff in each subtree _between_ those two |
| 119 |
endpoints, by subtracting the two cumulative sizes. |
| 120 |
* For the existing kind of query, this is only a minor |
| 121 |
optimisation, and doesn't affect the asymptotic performance |
| 122 |
of the query. |
| 123 |
* But the advantage is that it also lets you do an inverse |
| 124 |
lookup, of the form 'Given a pathname interval (subdirectory) |
| 125 |
and a target *size* X, find an atime T such that the amount |
| 126 |
of data in that subdir older than T is X.' In the current |
| 127 |
agedu data structure that takes log^2 time, because you have |
| 128 |
to do a log-time query for each step of a binary search over |
| 129 |
candidate atimes; but if you do a 3-sided search in this |
| 130 |
range tree system, you can use the subtree sizes instead of |
| 131 |
the tree sort order to decide which direction to go as you |
| 132 |
descend the tree, just like querying an ordinary annotated |
| 133 |
tree. |
| 134 |
* I think this inverse lookup could be helpful for speeding up |
| 135 |
the HTML report generation. The normal query answers the |
| 136 |
question 'Where should the boundary be between these two |
| 137 |
colour values?', and agedu runs that query once per output |
| 138 |
colour. But the inverse query answers 'What colour should |
| 139 |
_this pixel_ in the output bar be?', so for very small bars |
| 140 |
(of which there will be a lot), inverse queries would surely |
| 141 |
get the needed information faster. |
| 142 |
- Also, I quite like the idea of a hybrid strategy: |
| 143 |
+ for a bar with fewer pixels than colours, determine the |
| 144 |
colour of its middle pixel by an inverse lookup, then |
| 145 |
recurse into each half |
| 146 |
+ but if there are more pixels than colours, determine |
| 147 |
the location of the middle colour by a forward lookup, |
| 148 |
and recurse similarly |
| 149 |
+ and at each level of the recursion, pick one of those |
| 150 |
strategies as appropriate. |
| 151 |
+ Without having actually implemented it in practice, my guess is |
| 152 |
that this structure as described above is comparable in both |
| 153 |
space and time to the current one. It's still N log N space in |
| 154 |
principle; you still get to optimise to some degree by |
| 155 |
disregarding uninteresting differences between pathname indices |
| 156 |
(in this case, by compressing the arrays at each node, rather |
| 157 |
than by discarding intermediate states of the evolving tree); |
| 158 |
and it still takes log time to answer the existing kind of |
| 159 |
query, namely 'what is the total size of stuff in this subdir |
| 160 |
older than this atime?'. |
| 161 |
+ There's also a way to compress the index to a smaller size, at |
| 162 |
the cost of query time, by replacing the array at each tree node |
| 163 |
with a bit-vector that just says which child each logical array |
| 164 |
element came from, and storing a cumulative element count and |
| 165 |
cumulative size per _word_ of the bit-vector instead of a |
| 166 |
cumulative size for every element. This means that at every step |
| 167 |
down the tree you can only compute the cumulative size |
| 168 |
approximately from the data actually stored at that tree node, |
| 169 |
and to fix up the errors you have to look at the two partial |
| 170 |
words at each end of your search and chase each individual |
| 171 |
element down the tree to the bottom to find its exact size. Done |
| 172 |
naively, this gives you O(log^3 n) lookup time (at each of the |
| 173 |
log n steps down the tree, there are log n extra points you have |
| 174 |
to sort out, each of which needs another log n pass to the |
| 175 |
bottom of the tree); you can improve on that by storing extra |
| 176 |
indices (also bit-packed) that allow you to jump multiple levels |
| 177 |
down the tree, permitting an assortment of tradeoffs that let |
| 178 |
you _almost_ get rid of a log factor - you can have O(n) space |
| 179 |
and O(n log^{2+e} n) for e as small as you want (paying for a |
| 180 |
smaller e with a larger constant factor), or conversely |
| 181 |
O(n^{1+e}) space and exactly O(n log^2 n) query time, or the |
| 182 |
in-between compromise of O(n log log n) space and O(n log^2 n |
| 183 |
log log n) query time. |
| 184 |
+ source: "A Functional Approach to Data Structures and Its Use |
| 185 |
in Multidimensional Searching", B. Chazelle, SIAM J. Comput. |
| 186 |
17 (1988), 427-462 |
| 187 |
+ and I _think_ it should in principle be possible to vary the |
| 188 |
frequency of cumulative counts/sizes so as to trade off space |
| 189 |
and time smoothly between that compressed representation and |
| 190 |
the full layered range tree. |
| 191 |
|
| 192 |
- A user requested what's essentially a VFS layer: given multiple |
| 193 |
index files and a map of how they fit into an overall namespace, |
| 194 |
we should be able to construct the right answers for any query |
| 195 |
about the resulting aggregated hierarchy by doing at most |
| 196 |
O(number of indexes * normal number of queries) work. |
| 197 |
|
| 198 |
- Support for filtering the scan by ownership and permissions. The |
| 199 |
index data structure can't handle this, so we can't build a |
| 200 |
single index file admitting multiple subset views; but a user |
| 201 |
suggested that the scan phase could record information about |
| 202 |
ownership and permissions in the dump file, and then the indexing |
| 203 |
phase could filter down to a particular sub-view - which would at |
| 204 |
least allow the construction of various subset indices from one |
| 205 |
dump file, without having to redo the full disk scan which is the |
| 206 |
most time-consuming part of all. |