Opened 7 years ago

Closed 7 years ago

#2052 closed task (fixed)

dns::LabelSequence::compare()

Reported by: jinmei Owned by: muks
Priority: medium Milestone: Sprint-20120703
Component: libdns++ Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket:
Estimated Difficulty: 4 Add Hours to Ticket: 0
Total Hours: 1.51 Internal?: no

Description

In memory-efficient version of in-memory data source, it will be quite
likely to store names in the form of a sequence of a label (i.e.,
the portion of the entire name corresponding to a specific RBTree
node). So, it's quite likely we'll use dns::LabelSequence? (with some
extensions) to manipulate them.

This task is one such extension: introducing a "compare" method to
LabelSequence?. It's a natural extension of Name::compare(), and
it also returns NameComparisonResult?. But in the case of
LabelSequence? there's one new possible result: there's no hierarchical
relationship between the two label (such as between "www" (which is
not an absolute name) and "example.org."). So we also need to extend
NameRelation? introducing "NONE" to represent this relationship.
Name::compare() can never return this relation but
LabelSequence::compare() can.

Subtickets

Change History (11)

comment:1 Changed 7 years ago by shane

  • Estimated Difficulty changed from 0 to 4
  • Milestone changed from Next-Sprint-Proposed to Sprint-20120703

comment:2 Changed 7 years ago by muks

  • Owner changed from UnAssigned to muks
  • Status changed from new to assigned

Picking bug

comment:3 Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned
  • Status changed from assigned to reviewing

Up for review.

comment:4 Changed 7 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:5 follow-ups: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

First, I'd like to ask ‒ there's no relation between absolute and non-absolute name. But what about two non-absolute ones? Comparing "www" to "www" will return NONE. Is it what we want?

Also, this comment is not true (in the documentation of partial_compare):

/// This method never throws an exception.

because of this:

if ((first_label > labelcount_) ||
    (first_label_other > other.labelcount_)) {
    isc_throw(BadValue, "Bad first label indices were passed");
}

And, finally, I wanted to point out that we planned to extend the LabelSequence? so it would be possible to be built on top of raw data instead of the Name object. I think we'll be using these in the new in-memory implementation. But then, this will not work. Would it be possible to modify the Name and the LabelSequence? so that the partial_match code works both for the Name and for the internal data structures of LabelSequence?, so the LabelSequence::compare would not use the Name object there?

comment:6 in reply to: ↑ 5 Changed 7 years ago by jinmei

Replying to vorner:

First, I'd like to ask ‒ there's no relation between absolute and non-absolute name. But what about two non-absolute ones? Comparing "www" to "www" will return NONE. Is it what we want?

I've not looked into the code, but, not, that's not what we (I) want.
comparing "abc" (non absolute) and another "abc" (also non absolute)
should result in "EQUAL". If the implementation doesn't work that
way, it's not what this ticket intended.

comment:7 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

Replying to vorner:

First, I'd like to ask ‒ there's no relation between absolute and non-absolute name. But what about two non-absolute ones? Comparing "www" to "www" will return NONE. Is it what we want?

It seems this is not we want after discussion with Jinmei on jabber. I've added several more unit tests and updated the code to compare non-absolute label sequences properly.

Also, this comment is not true (in the documentation of partial_compare):

/// This method never throws an exception.

because of this:

if ((first_label > labelcount_) ||
    (first_label_other > other.labelcount_)) {
    isc_throw(BadValue, "Bad first label indices were passed");
}

Fixed. :)

And, finally, I wanted to point out that we planned to extend the LabelSequence? so it would be possible to be built on top of raw data instead of the Name object. I think we'll be using these in the new in-memory implementation. But then, this will not work. Would it be possible to modify the Name and the LabelSequence? so that the partial_match code works both for the Name and for the internal data structures of LabelSequence?, so the LabelSequence::compare would not use the Name object there?

There is no current internal data structure of LabelSequence? specific to it (it uses Name). This is why Name's compare() was modified to partial_compare() and reused. I think suggested changes are best done after LabelSequence? is itself modified as part of the larger changes. The changes required at that point would be straightforward.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to muks:

Hi vorner

Replying to vorner:

First, I'd like to ask ‒ there's no relation between absolute and non-absolute name. But what about two non-absolute ones? Comparing "www" to "www" will return NONE. Is it what we want?

The changes look OK.

And, finally, I wanted to point out that we planned to extend the LabelSequence? so it would be possible to be built on top of raw data instead of the Name object. I think we'll be using these in the new in-memory implementation. But then, this will not work. Would it be possible to modify the Name and the LabelSequence? so that the partial_match code works both for the Name and for the internal data structures of LabelSequence?, so the LabelSequence::compare would not use the Name object there?

There is no current internal data structure of LabelSequence? specific to it (it uses Name). This is why Name's compare() was modified to partial_compare() and reused. I think suggested changes are best done after LabelSequence? is itself modified as part of the larger changes. The changes required at that point would be straightforward.

Well, the rest of LabelSequence uses the data by accessing the two arrays, they don't call methods of Name directly. So I wanted to point out it would be better done this way too. But you're right this can wait for the changes to the LabelSequence

Anyway, I noticed one more thing. The tests don't seem to test any case with SUBDOMAIN or SUPERDOMAIN. Neither I noticed a test checking the order from getOrder() method. Could these be added?

Thank you.

comment:9 in reply to: ↑ 8 Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

Replying to vorner:

Anyway, I noticed one more thing. The tests don't seem to test any case with SUBDOMAIN or SUPERDOMAIN. Neither I noticed a test checking the order from getOrder() method. Could these be added?

SUBDOMAIN and SUPERDOMAIN checks exist already. You may have missed them due to the number of other checks around them. I've added getOrder() checks for all the added tests.

comment:10 Changed 7 years ago by vorner

  • Owner changed from vorner to muks
  • Total Hours changed from 0 to 1.51

Hello

I might have overlooked the tests, yes. It looks OK now. Please merge.

Thank you

comment:11 Changed 7 years ago by muks

  • Resolution set to fixed
  • Status changed from reviewing to closed

Merged to master in commit 1170780af08a0de33e882da5409776fe0e7f2a11:

* dbef0e2 [2052] Rename partial_compare() to just compare()
* 6b32945 [2052] Add getOrder() checks for all compare tests
* 87e091a [2052] Return order=0 when name comparison result is NONE
* c09a49c [2052] Fix code for comparisons of non-absolute label sequences
* 491a0e2 [2052] Fix documentation of partial_compare() for exceptions it can throw
* 02f0aa6 [2052] Add more unittests for the behavior we expect
* 57c61f2 [2052] Add implementation and unit tests for dns::LabelSequence::compare()

Resolving as fixed. Thank you for the reviews vorner.

Note: See TracTickets for help on using tickets.