-*-org-*-

BUGS

domain comparability

whether domain is arithmetic is currently used for deciding whether it’s meaningful to compare a constant of this domain to constants of other domains. But e.g. address and offset aren’t comparable, but they are safe for arithmetic. Similarly line and column–shouldn’t be compared with one another, but are safe for arithmetics. This is unlike named constants, which are not safe for arithmetic.

libzwerg C API

vocabulary versioning

Vocabularies need the same care as the C API when it comes to stability. Each vocabulary should actually come as a suite of versions that one can use, with one of them chosen as default (typically the latest one). Incompatible changes (e.g. introduction of a word that could clash with an existing variable, change of behavior, removal) would prompt version number bump, and one could request the old version explicitly.

5

Specify all vocabularies in external libraries, use libzwerg API. The current overload interface looks about right for what is necessary: yield once, maybe and many, and predicates, all keyed to a stack profile.

Then “argv” can be in a vocabulary of its own, brought in by dwgrep, and primed with the arguments to actually yield.

The problem with this is how to handle dependencies between vocabularies. E.g Dwarf vocabulary depends on core vocabulary’s constant type (for all the builtin constants). How would one express this? Dp the vocabularies that can be built upon need to have a stable C API as well? (Well, they would be just libraries…).

static analysis tools

overload pegging

We could use overload prototype declarations to mention return value type as well. Then we could determine what overload will be chosen for each overloaded word, and dispatch it directly.

stack effect analysis

By the same token, we could statically determine that a certain program is invalid, because it underruns stack. For variadic input argument operators (such as integrate, which is either ?T_DIE ->? ?T_DIE or ?T_DIE ?T_CLOSURE ->? ?()) we are possibly out of luck and have to fall back on runtime checking.
- It might even make sense to turn off stack effect checking when we can prove that the program never underruns.
  We could also selectively turn off stack profile tracking for programs where we can statically determine all effects. But that will be rare, any attribute access is a wild card.
- At least stack shuffling operators need to be built in, so that we know that we don’t lose type information after dup’ing. (Without having to have something awfully generic like dup :: A => A A).
- Variable binding somewhat complicates things, though we can probably simply annotate the deduced type in the scope. Since variables are never redefined, this shouldn’t be a big problem.
- Closures are of course difficult. No idea how to handle those.

strength reduction, of sorts

The idea is that instead of (Dw winfo (offset == 0x123)), we would emit (Dw 0x123 dwarf_offdie), without dwarf_offdie actually being a word. (This would also check that there is such DIE in the first place.) winfo would expose a “reduction point”, and the translator would make use of that.
- winfo, unit, child: offset, ?root, maybe pos
- attribute: label
- address/T_DIE: other range ?overlap, maybe pos
- (r)elem/T_SEQ: pos
- (r)elem/T_LOCLIST_ELEM: pos, maybe offset
- value/T_LOCLIST_OP: pos
This functionality would depend on overload pegging, so that you know which overload to ask for abbreviations. But some of it could be doable in runtime as well, and might still very much pay off.

removal of cloning for subexpression evaluation

If we can prove that the expression in a ?(), let, or [] doesn’t touch existing stack slots at all, we can avoid cloning altogether. E.g. the following rewrite:
```
let B := A child ?TAG_formal_parameter;
A child ?TAG_formal_parameter ->B;
    
```
In some other cases, it might be advantageous to just duplicate top element and drop in later. E.g.:
```
let A := entry ?TAG_subprogram;
dup entry ?TAG_subprogram ->A;
    
```
This would be likely especially advantageous if the “dup” just copies a shared pointer reference instead of cloning.

Or this:

entry ?([@AT_location] relem (pos == 0) label
        (?DW_OP_implicit_value, ?DW_OP_stack_value))

… which can be rewritten as:

entry [@AT_location] relem (pos == 0) label
      (?DW_OP_implicit_value, ?DW_OP_stack_value) drop

Simply converting unique_ptr’s in stacks to shared_ptr’s is not advantageous. Even if we remove all the cloning (which is problematic, because of occasional set_pos calls), it’s still slower than the original due to having to deal with all the reference counts.
- thread unsafe shared_ptr might be better
- can we avoid the reference counting altogether?

Dictionaries

Maybe have a key-value value type? And a => operator for constructing this? The dictionary would then be:
```
[7 => 5, 8 => "foo"]
    
```
There would be words, key and value, which access parts of the pair. Lookup would be done like:
```
[dictionary] elem (key == 7) value	# gimme 7's value
    
```
Querying:
```
[dictionary] (elem key == 7)		# do we have key 7?
    
```
Getting list of all keys:
```
[dictionary] [|D| D elem key]
    
```
Add 1 to key X:
```
[dictionary] [|D| D elem (key => value (==X) 1 add || )]
    
```
Add A=>B unless A already present:
```
[dictionary] (|D| if (D elem key == A) then D else [D elem, A=>B])
    
```
Wow, that’s a mouthful.

Um, what does this do?
```
[(1, 2, 3) => ("a", "b", "c")]
    
```
I think it should be this:
```
[1 => "a", 1 => "b", 1 => "c", 2 => "a", ...]
    
```
… which actually shows that list of key-val pairs is no dictionary, or actually that it’s a multi-set sort of thing.

@AT_MIPS_linkage_name — translated to @AT_linkage_name automatically

XXX @AT_stmt_list

@AT_stmt_list yields a number of nodes of type line_table_entry. The following words (which are thin wrappers around similarly named libdw functions) are applicable to individual line table entries:

address
@lineop_index
@lineno (or @AT_decl_line ???)
@linecol (or @AT_decl_column ???)
@linebeginstatement, ?linebeginstatement, !linebeginstatement
@lineendsequence, ?lineendsequence, !lineendsequence
@lineblock, ?lineblock, !lineblock
@lineprologueend, ?lineprologueend, !lineprologueend
@lineepiloguebegin, ?lineepiloguebegin, !lineepiloguebegin
@lineisa
@linediscriminator

The operators that return a boolean constant come also in assertion variant so that it’s easy to filter interesting line table entries.

XXX That’s however not entirely consistent with how DW_FORM_flag* attributes behave. For those, ?AT_* always means, is this attribute present, and never, is the value true. Needs some more thinking to consolidate this. Maybe we could abandon the @op’s for these and just expose ?op’s. When ?x is present, it implies that @op is true.

XXX .debug_frame, .eh_frame

do we need an overarching “theory” for both of these?
also, there’s fair amount of tables around here (symbol tables, line tables, …). Does it make sense to understand them as first-class citizen of some sort? Currently we understand there are values, every value has some properties, and some values have attributes.

XXX multithreading

processing Dwarf has the potential for a lot of concurrency. If locks end up serializing, we might actually open the Dwarf in each thread anew, and see if that helps.

expose exception frames

expose macros

one example query: who includes a given file?

expose .debug_line

note missing DW_LNE_*, DW_LNS_*. These can’t quite have distinct domains, as they need to be comparable. Better wait with implementing these until we get to line tables, so that it’s better understood how these will need to be used.

raw attributes

@AT_* should keep its current meaning of
```
attribute ?AT_* cooked value
    
```
That seems more useful.
Raw access would have to be requested explicitly:
```
attribute ?AT_* raw value
    
```

floats

These are currently represented as blocks. libdw doesn’t give us any support decoding these, and it seems to be not entirely trivial–endian issues, different encodings, and such.
E.g. on x86_64, __float128 type claims to be 10 bytes, but the block is 16 bytes long. long double claims to be 10 bytes as well, the block is 16 bytes as well, but aligned so that only the first ten bytes are used.

Seems like a fair can of worms. Is it worth it?

proper decoding of DW_ATE_UTF

Decode as UTF-8? Or do we need a wchar_t string? Also, C++ should have conversion facets for 16-bit and 32-bit character types, but that’s not implemented in GCC yet.

statistics?

akin to systemtap? locstat would certainly use them.
but that might be overkill. Maybe we just need reasonable dictionaries or something.

location expression evaluation

could we use the program stack for this?

address ranges vs. addresses, overloaded ?eq

address::T_DIE yields T_ASET, but address::T_ATTR yields T_CONST. Both should probably yield T_ASET, and T_ASET should be comparable to T_CONST.

if/while condition in plain context

One can always force sub-expression evaluation by explicitly placing the condition into a ?() block. This would however need a complementary word “until” so that it’s possible to express a negative recurrent condition.
Hmm, actually while X do Y makes no sense in plain context. When while finally stops iterating, it produces… nothing! until is the only iteration tool that makes sense.
until … do … makes no sense either, from the linguistic perspective, as it would imply that the result of until feeds into the do block.

how about:

(!(address) parent)* address
until address do parent

entry merge* !(merge)
entry while merge do ()

(!AT_xyz integrate)* ?AT_xyz	# find closest DIE with DW_AT_xyz
while !AT_xyz do integrate

(!AT_xyz integrate)* attribute ?AT_xyz	# dwarf_attr_integrate
until (attribute ?AT_xyz) do integrate

(!AT_xyz integrate)* @AT_xyz	# value of integrated DW_AT_xyz
until @AT_xyz do integrate

let seq := {|B| (1 add (< B))* };
let seq := {|B| while (< B) do (1 add) };

... ?(@AT_type ((?TAG_const_type, ?TAG_...) @AT_type)* ...
... do @AT_type while (?TAG_const_type, ?TAG_...) ...

child*
while child take ()

Should while/until be plain context, which is useful, then if/unless should be as well. Then perhaps let should be as well. Looking through let uses, that would be no expressivity loss.

Possibly allow other keywords besides “do”. “max” and “sum” come to mind. “take” would produce every visited node (like what * does). Could these somehow just be ordinary words? Note that we don’t need “collect”, one can instead use “take” inside a capture.

[take ... while ...] 0 {@AT_* add} fold	# sum of selected nodes
[until ... take ...] {@AT_* max} fold1	# max of selected nodes

take B while C
loop:
  B yield
  (C || break)

do B while C
loop:
  B
  (C || (yield, break))

while C take B
loop:
  (C || break)
  B yield

while C do B
loop:
  (C || (yield, break))
  B

take B until C
loop:
  B yield
  (C break || )

do B until C
loop:
  B
  (C (yield, break) || )

until C take B
loop:
  (C break || )
  B yield

until C do B
loop:
  (C (yield, break) || )
  B

weird ideas

more general iteration

X* would be syntactic sugar for (X ^). The ^ would reapply the whole expression that it’s part of. One could use it pretty much arbitrarily, e.g. (X ^ Y), (^ X), possibly even (X ^ Y ^ Z). It’s unclear whether this is really useful, though achieving this by other means would be tedious to write. But really, are there other uses apart from checking that, say, DW_MACRO_GNU_start_file and DW_MACRO_GNU_end_file are balanced?
Details of operation are unclear as well.
We could also use a greedy star (or greedy variant of the above thing). X& would be like X* !(X).

undocumented functionality

•“{” (“|” ID₁ ID₂ … “|”)? EXPR₁ “}” — blocks

{EXPR₁} – A block syntax. A value representing an expression EXPR₁ is pushed to TOS. The enclosed expression can later be evaluated using an operator “apply”. Application causes EXPR₁ to be evaluated in plain context. Thus:
```
{add} 1 2 rot apply	# Leaves 3 on stack.
{1 add} 2 swap apply	# Likewise.
    
```
{|ID₁ ID₂ …| EXPR₁} – A variant of block syntaxt with an identifier block. When applied, pops TOS and binds it to the rightmost identifier, and then proceeds doing the same with other identifiers in right to left direction.
```
{|A B| A B add A B sub mul} 3 1 rot apply	# 8
    
```
When a block is applied, this introduces a new activation record (dynamic scope) inside the current scope. Any let forms bind symbols in this new scope. Upon creation, block literals copy values of referenced variables into their scope, so they work as closures:
```
let adder := {|x| {|y| x y add}};
3 adder 2 swap apply	# 5
    
```
```
let map := {|L f| [L elem f]};
[1, 2, 3] {1 add} map	# [2, 3, 4]
    
```
Because blocks copy surrounding context instead of referencing it, all referenced bindings need to be defined at the point of block creation. That precludes a simple way of writing recursive functions:
```
# This doesn't work:
let fact := {|N| if (N < 2) then 1 else (N 1 sub fact N mul)};
    
```
Here “fact” is referenced inside the block, but at that point, it has not yet been defined, and such expression is thus erroneous. It is possible to express recursion, even mutual recursion:
```
let f1 := {|N f1 f2|
   if (N < 100) then (
       N sub 1
       {f1} {f2} f2 apply	# recurse to f2
   ) else (N)
};
    
```
:
```
let f2 := {|N f1 f2|
    if (N > 0) then (N mul: 2) else (N)
    {f1} {f2} f1 apply		# recurse to f1
};
    
```
:
```
5 {{f1}} {{f2}} f1	# 194
    
```
… but that is of course ridiculous. The hope is that recursion is rarely useful in a language like this, which is meant for querying, not writing algorithms. Should there be serious need for this sort of thing, this functionality would be introduced.
Example: stack shuffling operators. (N.B.: this example uses underscores to distinguish from the corresponding built-in words. Redefining built-ins is not allowed.)
```
let drop_ := {|a|};
let dup_ := {|a| a a};
let swap_ := {|a b| b a};
let rot_ := {|a b c| b c a};
let over_ := {|a b| a b a};
    
```

Infix operator overriding

Infix operators are just reads, it would be straightforward to allow overriding them:

let ==~ = {?((|A B| ((A == B) || (A =~ B))))};
let !=~ = {!((|A B| ((A == B) || (A =~ B))))};

The current codebase allows a limited form of this with the following let form:

let "===" := {something};

But extending IdListOpt to allow both words and operators would be simple, and then all binding forms would allow this.

Stack profile-sensitive bindings

let elem/T_XYZ = {...};
let foo/T_XYZ = 1; # push value depending on TOS type :)

Since symbol versioning should be built around overloads, and builtins themselves should be derived off that (at least I guess), allowing users to redefine particular overloads seems logical. Old syntax would stay around meaning that the profile selector is composed of 0 TOS slots.

(“while” | “until”) EXPR₀ “do” EXPR₁ | “do” EXPR₁ (“while” | “until”) EXPR₀

The “while..do” loop checks whether EXPR₀ yields anything. If yes, it evaluates EXPR₁ and repeats; otherwise it doesn’t do anything.
“do..while” works similarly, but it first evaluates EXPR₁ and then tests whether EXPR₀ yields anything.

“until” loops work similarly, but test a reverse condition.
EXPR₀ is evaluated in sub-expression context.
EXPR₁ shall have neutral stack effect.

•“\dbg” — debug print

Doesn’t alter the stack in any way, but as a side effect prints some information about the computation in whose context it appeared.

•colon infix syntax

When a word is followed by a colon, the following statement is executed before that word. That can be used for writing the operators, where it makes sense, in infix form. For example:
```
10 add: 1	# equivalent to (10 1 add)
[10 range] sort: {a | if (a mod: 2 == 0) then 0 else 1}
    
```

•stack slices: “[EXPR₀]

Evaluated as [|X₀ X₁ …| X₀ X₁ … EXPR₀] With as many X’s as there are backticks.
Another equivalent form: [EXPR₀] (|X₀ X₁ … K| K) I.e. keep TOS, drop N below.
The point of this is to avoid having to write [|A| A expr], and instead write simply `[expr]. The former is somewhat annoying to write, but it’s not clear it’s worth it to extend syntax because of it.
Also not clear there’s any value in having more than one backtick. Let’s see how this fares, it can be always simplified.

WORDS

·T_SEQ

at :: ?T_SEQ ?T_CONST -> ?()

One can access a particular element by enumerating the array with elem or relem, and then do assertions on pos:

[some seq] elem (pos == 0)	# [0]
[some seq] relem (pos == 0)	# [-1]
[some seq] elem (pos != 0)	# [1:]
[some seq] elem (pos >= 3 && pos < 6)	# [3:6]
[some seq] relem (pos > 0)	# [:-1]

There’s now a convenient notation for this:

[some seq] elem ?0	# elem (pos == 0)
[some seq] relem ?0	# relem (pos == 0)

Might be perhaps worth it to have this as well:

[some seq] @0		# elem (pos == 0)

We could also have: – slice :: ?T_SEQ ?T_CONST ?T_CONST -> ?() – slice :: ?T_SEQ ?T_CONST -> ?()

[some seq] 1 slice	# elem (pos != 0)
[some seq] 3 6 slice	# elem (pos >= 3 && pos <= 5)
[some seq] 0 -1 slice	# relem (pos > 0)

We would need both versions because there’s no placeholder like None in Python, where [1:] means [1:None] and None is treated like one past last element. 0 can’t be used in that capacity, as then it wouldn’t be clear whether (0 0 slice) needs to yield nothing or everything.

fold :: ?T_SEQ ?() ?T_CLOSURE ->* ?()

This takes care of all sorts of summing and joining list elements. E.g. “join” is:
```
[the sequence] "" {"%s" add} fold
    
```
“sum” is:
```
[the sequence] 0 {add} fold
    
```

rfold :: ?T_SEQ ?() ?T_CLOSURE ->* ?()

Like fold, but works in reverse.

fold1 :: ?T_SEQ ?T_CLOSURE ->* ?()

let fold1 := {|L C| L (L elem (pos == 0)) {C} fold};

I.e. takes initial value from the sequence. Produces nothing if the sequence is empty.

rfold1 :: ?T_SEQ ?T_CLOSURE ->* ?()

Like fold1, but in reverse order.

Command line arguments

It might be useful to have a pair of arguments –a[ and ], which would collect several arguments into an array. Consider “dwgrep –a[ *.out ] -e ‘…’”. It would be interesting if the current invocation of dwgrep were a syntax sugar for something more advanced, say –a( *.out ). Maybe -a( ) would then pass in strings? And –a[ ] an array of objects and -a[ ] array of strings? (Leaving aside that “-a[” is seen as two arguments by argparse).

Goal	Syntax
one string	-a abc
several strings	-( abc def -)
array of strings	-[ abd def -]
one value	–a 123
several values	–( 123 ‘“foo”’ –)
list of values	–[ 123 ‘“foo”’ –]
one Dwarf	–a ‘“a.out” dwopen’
several Dwarfs	–( ‘“a.out” dwopen’ ‘“b.out” dwopen’ –)
array of Dwarfs	–[ ‘“a.out” dwopen’ ‘“b.out” dwopen’ –]

If we allow closing element to have an optional value with dwgrep expression to apply at the result:

Goal	Syntax
one string	-a abc
several strings	-[ abc def -]=elem (or just -(, -))
array of strings	-[ abd def -]
one value	–a 123
several values	–( 123 ‘“foo”’ -)
list of values	–[ 123 ‘“foo”’ -]
one Dwarf	–a ‘“a.out” dwopen’
several Dwarfs	-( a.out b.out -)=dwopen
array of Dwarfs	-[ a.out b.out -]=dwopen

All of these forms however require that argument parsing is reimplemented by hand (though maybe libc’s argp context might be bent inside argument-handling switch to allow this). And it’s unfamiliar. What tools usually do is they pass in list of strings and those are interpreted as file names and opened. What sucks about this system is that one can’t simply say “dwgrep -f foo.zw *.out” and have foo.zw see a list of files to open and process.

It’s also tempting to have something like -a key=value, with key becoming a variable in outermost stack. But there’s no good way to provide a default. Dictionaries would be a natural fit for this:

dwgrep -e 'let Offset := argv (key == "offset") value ;
           let Pred := argv (key == "pred") value ;
           entry die (offset == Offset) foo bar Pred' \
       -a offset=0x123 \
       -a pred='{!root}'

But actually, if the dictionary solution to be adopted is the one with list of associations, then we can simply do non-keyword arguments, and when people want to use the associations, they can, exactly as above:

dwgrep -e '... argv (key == "offset") ...' \
       -a '"offset" => 0x123' \
       -a '"pred" => {!root}'

Of course, even without this, one can do e.g.:

dwgrep -d '(|X| let Offset := X elem (elem ?0 == "offset") elem ?1; \
            ...)' \
       -a '[("offset", 0x123'), ("pred", {!root})]'

·T_CONST

int32_t, uint32_t, int64_t, uint64_t :: ?T_CONST -> ?T_CONST

The idea behind uint32_t et.al. is that a two-complement representation of a given constant is taken, if necessary, it’s sign-extended, and then a 32-bit or 64-bit slice of that is taken, and that is reinterpreted as either a signed or unsigned value:

-1 hex			# gives -0x1
-1 uint32_t hex		# gives 0xffffffff
-1 uint64_t hex		# gives 0xffffffffffffffff
0xffffffff int32_t	# gives -1
0xffffffffff int32_t	# gives -1 as well
0xffffffff int64_t	# gives 0xffffffff

Maybe what we want instead is “32 uint”, “64 int” etc., such that bit length is configurable.

intptr_t, uintptr_t :: ?T_CONST -> ?T_CONST

{,u}intptr_t then expands to either of {,u}int{64,32}_t depending on address size of CU. XXX how to get to that size? What should, say, “17 uintptr_t” do? There’s no CU in sight…

·T_STR

match :: ?T_STR ?T_STR ->* ?T_STR

This should work like ?match, but would produce match objects with individual groups.

"abcd" r"(\w)(\w)" ...
... match			# two matches
... match low			# 0 and 2
... match high			# 2 and 4
... match value		# "ab" and "cd"
... match (pos==0) elem	# match for "a" and match for "b"
... match (pos==0) elem value	# "a" and "b"

demangle :: ?T_STR -> ?T_STR

·T_CU

next :: ?T_CU ->? T_CU

prev :: ?T_CU ->? T_CU

·T_DIE

•@AT_decl_file

Value of this attribute is represented as actual string including path.

(XXX we ignore mtime and size. Those aren’t stored anyway, but maybe it would be useful to have them so that one can do this sort of querying in the first place–do we have any files where this is stored? Or after it gets to be stored in general, where this is not stored?)

?LANG_* :: ?T_DIE

Holds if (@AT_language == DW_LANG_*).

?ATE_* :: ?T_DIE

Holds if @AT_encoding == DW_ATE_*.

·T_ATTR

?LANG_* :: ?T_ATTR

Holds if (?AT_language value == DW_LANG_*).

?ATE_* :: ?T_ATTR

Holds if (?AT_encoding value == DW_ATE_*)

T_MACRO_UNIT ???

A value representing .debug_macro and .debug_macinfo units. Might be useful for DW_MACRO_GNU_transparent_include opcode, and for DW_AT_macro_info and DW_AT_GNU_macros attributes, which would hold this as a value.

entry :: ?T_MACRO_UNIT ->* ?T_MACRO_ENTRY

offset :: ?T_MACRO_UNIT ->* ?T_CONST

XXX :: something to get the prototype table???

T_MACRO_ENTRY

A value used for representing both .debug_macro and .debug_macinfo entries. Domain of entry label disambiguates which is which.

label :: ?T_MACRO_ENTRY -> ?T_CONST

Opcode of this macro entry.

attribute :: ?T_MACRO_ENTRY ->* ?T_MACRO_ATTRIBUTE

Yields value(s) associated with this opcode.
XXX could we somehow query a form?

merge :: ?T_MACRO_ENTRY ->* ?T_MACRO_ENTRY

let merge := { ?DW_MACRO_GNU_transparent_include value };

Should be used as with DIE’s, depending on what exactly is needed either (merge*) or (merge* !(merge)).

@0, @1, … or something???

Should this resemble DIE’s or T_LOCLIST_OP’s? Shouldn’t T_LOCLIST_OP’s actually resemble DIE’s as well? @X as a shorthand for (value (pos == X)) seems fairly natural. (Why not elem (pos == X)?)
If X is a name instead of a number, it means:
```
(attribute (label == X))
    
```

T_MACRO_ATTRIBUTE ???

Note that label is explicitly not applicable

value

form

Examples

check_die_line_info:

let A := entry (?TAG_subprogram, ?TAG_inlined_subroutine, ?TAG_entry_point,
               ?TAG_lexical_block, ?TAG_label, ?TAG_with_stmt,
               ?TAG_try_block, ?TAG_catch_block);
let B := A (@AT_entry_pc, address);
let C := A root address;
?(B C !overlaps || B C overlap != B)
"Address range %( B %) referenced from %( A %)"\
" not fully covered by line table."

CU A imports two PU’s B and C, and both import the same third PU

let imports := {root child ?TAG_imported_unit @AT_import};

:

let U := entry ?root ;
let A := U child ?TAG_imported_unit @AT_import ;
let B := U child ?TAG_imported_unit @AT_import (> A) ;
A imports B imports (== swap)
"PU %(offset%) is imported by PU's %(A offset%) and %(B offset%), "\
"which are both imported by %(U offset%)."

Files

TODO

Latest commit

History