On 10 June 2015 at 17:13, Jonathan S. Shapiro <s...@eros-os.org> wrote:
> On Sun, Jun 7, 2015 at 9:00 AM, Keean Schupke <ke...@fry-it.com> wrote:
>
>> On 7 June 2015 at 16:32, Jonathan S. Shapiro <s...@eros-os.org> wrote:
>>
>>>
>
>> Backtracking seems to be one of those things that's harder to do without
>>> GC.
>>>
>>
>> The way to implement backtracking is with a vector of unique pointers, so
>> that popping the vector de-constructs the heap objects.
>>
>
> Umm. Actually, that sounds pretty expensive. The problem isn't popping the
> vector. The problem is the unnecessary constructions you're going to do
> every time you *grow* the vector. You want a vector of pointers, not a
> vector of objects. Though even that's a problem, because the parse stack
> elements don't have homogeneous type.
>
>
> shap
>
What unnecessary constructions? It is also polymorphic, a unique pointer
can point to any subclass just like a plain pointer. Hopefully this will
make it clearer:
vector<unique_ptr<ast>> region;
Note this allows you to use plain pointers (ast_node*) as the links and in
functions manipulating the tree, which is much faster than shared pointers.
The observation is that we only allocate onto the end of the region, and
when we undo we undo everything from the end to the choice-point.
// allocation looks like this:
type_atom* new_type_atom(string const& value) {
type_atom *const t = new type_atom(value);
region.emplace_back(t);
return t;
}
// getting a checkpoint / choice-point:
int checkpoint() {
return region.size();
}
// backtracking:
void backtrack(int p) {
region.resize(p);
}
So you save a choice-point, freely allocate nodes, and then either forget
the choice point, or backtrack.
Keean.
_______________________________________________
bitc-dev mailing list
bitc-dev@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
